Statistics

Problem Statement for "RockSkipping"

Problem Statement

You are skipping rocks on a lake. To skip a rock, you throw the rock horizontally with its flattest edge down and parallel to the lake, and spin it as it leaves your hand. The rock will skim the surface of the water, and leap back into the air for a distance, then skim again, repeating until it enters the water. The spin on the rock keeps it flat while it flies through the air, and its direction stays relatively constant. The pattern the rock takes as it skips along the lake is quite unusual, due to the imperfect surfaces of the rock and lake. The rock's skips (distances the rock jumps) are on average smaller as the rock gets further away, probably due to resistance against the water and air. However, sometimes the rock will go further than previous skips. Also, when the rock hits one of the many lily pads on the lake, it immediately sinks after sliding over the lily pad. Interestingly enough, the number of times the rock skips appears to be somewhat constant (unless it hits a lily pad).

Being the geeky computer scientist that you are, you devise a function determining the probablity that a rock being skipped will avoid all the lily pads. There are two inputs for your function, the lily pad pattern (pads) on the lake in the direction you are throwing, and the maximum distance (maxDist) that the rock will skip after striking the water for the first time.

pads will be input as a String. Each character in the String will represent a space of lake, '.' representing open water and 'X' representing a lily pad. Assume the lake continues infinitely off to the right of the pattern, repeating the pattern over and over again. So for instance, the pattern ".X.X.." corresponds to the lake .X.X...X.X...X.X.., which extends infinitely to the right. You throw your rock from the left side of the lake across to the right side, and aim it so the rock strikes the first space of lake (the first character in pads, which is always guaranteed to be open water). You should also assume that the rock's horizontal direction does not change (i.e. the rock's horizontal movement is always along the lily pad pattern).

maxDist will define how hard you throw the rock. You hypothesize that for the first skip, the maximum distance it could possibly jump is maxDist lake spaces. After each skip, the maximum distance is decreased by one, yielding a maximum distance of maxDist - N spaces for skip N (N starts at 0). The rock succumbs to the icy water when N equals maxDist or when the rock hits a lily pad. To account for the erratic skipping patterns, you hypothesize that the rock has an equal chance of skipping any integral distance between 1 and maxDist - N inclusive for skip N (to simplify the problem, assume the rock always lands in the middle of a space).

Your return value should be a probability from 0 to 100, which represents the percentage likelihood that the rock will not hit any lily pads.

Definition

Class:
RockSkipping
Method:
probability
Parameters:
String, int
Returns:
double
Method signature:
double probability(String pads, int maxDist)
(be sure your method is public)

Notes

  • Your return value must be within 1e-9 absolute or relative of the actual value.
  • Remember, the rock can only skip integral distances.

Constraints

  • pads will have between 1 and 50 characters, inclusive.
  • pads will consist only of the characters '.' and 'X'.
  • The first character in pads will be a '.'
  • maxDist will be between 2 and 100, inclusive.

Examples

  1. "."

    100

    Returns: 100.0

    No lily pads to hit, and therefore, a 0% chance of hitting them.

  2. "...X"

    2

    Returns: 50.0

    The rock's first destination is always the first space. It has a 50% chance of skipping to the second space, and a 50% chance of skipping to the third space. For the second skip, the maximum distance is 1, which means it has a 100% chance of moving ahead one space. The 50% chance that skipped to the second space now skips to the third space, and gracefully sinks. The 50% chance that skipped to the third space now skips to the fourth space and lands on the pad. Therefore, the rock has a 50% chance of surviving the pads.

  3. "........................X"

    50

    Returns: 11.60725450562586

    Even with the lily pads only covering 4% of the lake, about 88% of your rocks will eventually hit them.

  4. ".XXX"

    2

    Returns: 0.0

  5. ".XXXXXXXX............"

    100

    Returns: 2.2238319526041714E-22

  6. ".................................................X"

    100

    Returns: 12.468806209710456

  7. ".XXXX.XXXXXXXX.XXXXXXX.XXXXXX.XXXXX.XXXX.XXX.XX.X."

    100

    Returns: 1.7767779346052529E-71

  8. ".............................................X"

    9

    Returns: 99.99972442680777

  9. ".X...X..."

    39

    Returns: 0.0025670769630560513

  10. "...XX.....X.X.X.XX...X.X......XX........X.."

    81

    Returns: 9.054637332419204E-11

  11. "..XX..XX.X...X....X.XX.....X.XX...X...X"

    22

    Returns: 0.0013518497737741674

  12. "...........X.....X.....XX.."

    47

    Returns: 0.033741068149067195

  13. "..X..XXX"

    40

    Returns: 5.256969370279521E-12

  14. "...X......XXXX...XX.X..X...XX..."

    48

    Returns: 5.408479511004734E-8

  15. "..X...........X..XX.X"

    82

    Returns: 8.775600468363586E-9

  16. "..X.."

    99

    Returns: 1.1978720146654002E-8

  17. "....X...X....X..X..X.X.XXX..XX....X....X....X..."

    79

    Returns: 3.9264889512253644E-11

  18. ".X.."

    54

    Returns: 5.9815133740789975E-6

  19. ".X.X..X.X..X..X.XX.XX.XXXX..."

    22

    Returns: 4.5031054188698496E-6

  20. ".XXXX..X..X.....XX.X.X..X....X"

    60

    Returns: 7.611025001457206E-13

  21. ".X.X.X..X....X"

    11

    Returns: 0.25908890492223824

  22. ".X..XXX.....X.....X..X..X......X..X.."

    88

    Returns: 2.7926146794701252E-11

  23. ".XX..X....X..X.........X.X....X"

    97

    Returns: 9.401950020419752E-12

  24. "..X"

    66

    Returns: 6.224378501046996E-11

  25. "...X....."

    89

    Returns: 0.001923820483383841

  26. ".X............."

    41

    Returns: 4.8816736249265915

  27. "...."

    58

    Returns: 100.0

  28. ".....X..."

    38

    Returns: 0.8330836879326521

  29. "..X.........X..X...X.X.....X..X....X..X.XX."

    41

    Returns: 2.2363089847869097E-4

  30. "..XX....XXX.X..XX.XX..X.X....XXX........X....X."

    34

    Returns: 5.443438735931444E-6

  31. "."

    30

    Returns: 99.99999999999993

  32. ".X...X........X.X.....XX.XXXX...XX.X..X"

    72

    Returns: 2.680172485163696E-13

  33. "..XX...X.X....XX..X..X..X....X..X...X...."

    88

    Returns: 1.7483914206046326E-12

  34. "..X.X....X....X..X.X.X."

    17

    Returns: 0.07710324832143937

  35. ".XX..X...X.....X.X..XX....X...."

    100

    Returns: 3.6009254891763555E-14

  36. ".X.XX..X..X.X...XXX....XXX...X...X............."

    25

    Returns: 0.005761660905876298

  37. ".X.X..X.XX.X"

    20

    Returns: 4.693924387262402E-6

  38. ".XX.X.X....X.....X..XXX...XX...X....X...X..."

    31

    Returns: 2.1462438610287305E-4

  39. "..XX.X....XXXX.....X.....X..........X...."

    27

    Returns: 0.026176262517962977

  40. ".....X..."

    21

    Returns: 6.496903497690426

  41. ".X...XX..X.."

    26

    Returns: 7.091343055286317E-4

  42. "..X.X.X.X......XX.XX.X...........X..X.X.."

    22

    Returns: 0.016389625615091247

  43. ".XX...X.X..X..XX.X......XX............X.."

    23

    Returns: 0.03424952174008819

  44. "..X..X.XX..X.XXXX.XX...X...X.X......X........X."

    57

    Returns: 8.974053011613222E-10

  45. ".X....XX..........."

    62

    Returns: 0.0013684006627930753

  46. ".X.X.XX.X.X..X...X..XX."

    65

    Returns: 7.431232978113156E-16

  47. "..XX.....X"

    51

    Returns: 3.653775630395992E-7

  48. "..X........X...X........XX...X....X.XXX.."

    62

    Returns: 1.187051793350153E-6

  49. "...."

    14

    Returns: 99.99999999999999

  50. "."

    100

    Returns: 100.0

  51. ".................................................X"

    100

    Returns: 12.468806209710456

  52. ".................................................."

    100

    Returns: 100.0

  53. "........X.......X"

    100

    Returns: 2.460259452965898E-4

  54. "..............................X.................."

    100

    Returns: 11.952145910259919

  55. "......X..X...."

    100

    Returns: 1.244803813333236E-5

  56. ".X.X.XXX......X..X..X"

    10

    Returns: 0.2698688271604938

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: