Statistics

Problem Statement for "RobotCollision"

Problem Statement

You work in the field of Robotics and you are doing some black-box testing. Two robots, Robbie and Speedy, are randomly placed in a rectangular room, which is divided into xSize * ySize cells. Each robot receives a few movement commands that are executed one by one, at the same time, by both the robots.

A move is represented by an uppercase letter, which is one of the following:
- 'U': the robot moves from the coordinates (x, y) to the coordinates (x - 1, y). This command is ignored when x = 0.
- 'D': the robot moves from the coordinates (x, y) to the coordinates (x + 1, y). This command is ignored when x = xSize - 1.
- 'L': the robot moves from the coordinates (x, y) to the coordinates (x, y - 1). This command is ignored when y = 0.
- 'R': the robot moves from the coordinates (x, y) to the coordinates (x, y + 1). This command is ignored when y = ySize - 1.

Two robots may collide if they start one of their turns from the same cell, end one of their turns in the same cell, or exchange positions at one of their turns. You will be given an int xSize and an int ySize denoting the dimensions of the rectangular room, a String commandsRobbie denoting the movement commands given to Robbie and a String commandsSpeedy denoting the movement commands given to Speedy. Your task is to return the probability that the two robots will collide, taking into acount every possible start position for both of the robots. The probability for each robot to start in any specific cell is the same for all cells.

Definition

Class:
RobotCollision
Method:
probability
Parameters:
int, int, String, String
Returns:
double
Method signature:
double probability(int xSize, int ySize, String commandsRobbie, String commandsSpeedy)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • xSize will be between 1 and 100, inclusive.
  • ySize will be between 1 and 100, inclusive.
  • commandsRobbie and commandsSpeedy will each contain between 0 and 10 characters, inclusive.
  • Each character in commandsRobbie and commandsSpeedy is either 'U', 'D', 'L' or 'R'.
  • commandsRobbie and commandsSpeedy have the same length.

Examples

  1. 1

    10

    "L"

    "R"

    Returns: 0.27

    In this example, Robbie goes one step left and Speedy goes one step right. Out of the 100 possible starting positions (10 for each robot), 27 of them will lead to collision. A collision happens in one of the following three ways: - Robbie and Speedy start at the same cell. In this case we have an instant collision. There are 10 such starting positions. - Robbie starts at Speedy's immediate right. In this case we have a frontal collision as the two robots approach each other. There are 9 such starting positions. - Robbie starts two steps to the right from Speedy. In this case the robots end up in the same cell after they make their moves, so again, we have a collision. There are 8 such starting positions.

  2. 2

    2

    "DRUL"

    "DRUL"

    Returns: 1.0

  3. 2

    2

    "DRUL"

    "RULD"

    Returns: 0.4375

  4. 10

    10

    "D"

    "D"

    Returns: 0.012

  5. 20

    50

    ""

    ""

    Returns: 0.0010

  6. 100

    100

    "U"

    "D"

    Returns: 2.97E-4

  7. 27

    33

    "DRRLUUDLRD"

    "RDLURULDRL"

    Returns: 0.006010976456169124

  8. 100

    100

    "RRRRRRRRRR"

    "LLLLLLLLLL"

    Returns: 0.00189

  9. 17

    20

    "LLRRDRRDUL"

    "RULRLLRUDD"

    Returns: 0.03207612456747405

  10. 48

    82

    "LURUULUDUD"

    "LLUDLLLUDR"

    Returns: 0.0023561046871901645

  11. 52

    66

    "DUDLRRRULU"

    "DDULRDRUDU"

    Returns: 0.0012183935916453398

  12. 42

    8

    "R"

    "R"

    Returns: 0.003720238095238095

  13. 92

    52

    "LUDRDUDDUD"

    "RRLRUDUURD"

    Returns: 0.0018227651955794678

  14. 16

    16

    "LULRLULDUD"

    "RRUDLLULDD"

    Returns: 0.029327392578125

  15. 98

    48

    "RUUUULDRDD"

    "UDURLDLRRL"

    Returns: 0.0015163404860243418

  16. 31

    78

    "RUUDLD"

    "LDLULR"

    Returns: 0.0032142786285105983

  17. 10

    83

    "DLDUDUDDRU"

    "LDDRLRLLUL"

    Returns: 0.008271156916823922

  18. 78

    24

    "LDLDLLULLL"

    "UDDULRDRRD"

    Returns: 0.006387142504930966

  19. 3

    74

    "UUUUUUDURU"

    "RRULUULLRR"

    Returns: 0.04938722506290074

  20. 99

    93

    "RRULLRLRDL"

    "DLRDLDLLUU"

    Returns: 0.0011619244706271758

  21. 28

    65

    "LDRDUDLDLU"

    "DRRLDDULUD"

    Returns: 0.0041465402729139

  22. 79

    40

    "LLRLLRUDDR"

    "UUDLDLULUD"

    Returns: 0.0028638239064252523

  23. 35

    99

    "DLUULLDLRL"

    "LUULDDLDUR"

    Returns: 0.0019096760222301347

  24. 29

    50

    "URRRUUDULU"

    "RURULDDRUL"

    Returns: 0.005792152199762188

  25. 6

    48

    "DRLUUURRUD"

    "DUDLULDRRL"

    Returns: 0.01902488425925926

  26. 5

    43

    "LDLDL"

    "DRRLU"

    Returns: 0.03344510546241211

  27. 90

    18

    "URULUUUDLU"

    "LDUUDULLUL"

    Returns: 0.004644871208657217

  28. 82

    28

    "DDLRR"

    "DRRLU"

    Returns: 0.0021909790090932266

  29. 22

    46

    "UDUURLRLLD"

    "DUULRDURRU"

    Returns: 0.009351224046618443

  30. 53

    23

    "LDDUDRULRD"

    "DDRRLLDLRD"

    Returns: 0.0059187286880342084

  31. 55

    23

    "DDLRRDDDRR"

    "UUURLLULRR"

    Returns: 0.008429439610054837

  32. 80

    72

    "LLDDDRLR"

    "URUDDDLL"

    Returns: 0.0015456814236111112

  33. 46

    14

    "DRRRULDUDU"

    "LRLLDRLRDR"

    Returns: 0.015320589483430423

  34. 77

    15

    "RUDUUUL"

    "LDDLLRL"

    Returns: 0.005972901557317141

  35. 84

    71

    "RLRDLULU"

    "LLLRDUDL"

    Returns: 0.0013276900391843572

  36. 73

    61

    "RUD"

    "DRR"

    Returns: 9.059867188852566E-4

  37. 72

    18

    "RDUULUURRL"

    "DLDDLLDLRU"

    Returns: 0.008693653787532389

  38. 54

    38

    "RDULRULULU"

    "DLDLRRLLRD"

    Returns: 0.00508893524693258

  39. 51

    57

    "DU"

    "DL"

    Returns: 6.947395401228948E-4

  40. 28

    86

    "DRRULDDRLR"

    "LDLURLDLLR"

    Returns: 0.003330192271608481

  41. 65

    8

    "DRR"

    "UUL"

    Returns: 0.01003698224852071

  42. 38

    64

    "RLDDRLDDRL"

    "DDUDURURRD"

    Returns: 0.004353953860803324

  43. 18

    75

    "URURRURRDR"

    "LRRRDLLURR"

    Returns: 0.006089986282578876

  44. 24

    4

    "DDRUDDRDUU"

    "RUDLRLDUDR"

    Returns: 0.0886501736111111

  45. 91

    36

    "LDDDURUUDL"

    "RRRRRDLRUU"

    Returns: 0.003129840584053038

  46. 99

    65

    "UDRR"

    "LDLR"

    Returns: 6.141868146530151E-4

  47. 62

    71

    "LRU"

    "RLL"

    Returns: 9.022787337381856E-4

  48. 19

    62

    "LRL"

    "DRD"

    Returns: 0.002531556175613468

  49. 91

    37

    "LLDLUDRDDL"

    "LDLDRDRDDL"

    Returns: 0.0010592157904305217

  50. 48

    1

    "UULLUL"

    "LLDRUL"

    Returns: 0.08072916666666667

  51. 60

    83

    "RLDULLLDDR"

    "UDRRRRURDR"

    Returns: 0.0019329930162416736

  52. 9

    38

    "RDRUDRDL"

    "RULLLURR"

    Returns: 0.024127081837146472

  53. 28

    91

    ""

    ""

    Returns: 3.924646781789639E-4

  54. 50

    61

    "DDRUDUDUUR"

    "DRURLRRDUD"

    Returns: 0.0023935501209352327

  55. 14

    94

    ""

    ""

    Returns: 7.598784194528875E-4

  56. 65

    87

    "URUDUDURRD"

    "DURDRLDRLL"

    Returns: 0.0017174382270879116

  57. 4

    79

    "DDUDUDURUL"

    "DUUDLDLRLU"

    Returns: 0.0196883512257651

  58. 19

    88

    "DURLDRLLLU"

    "LLRDDRLRLL"

    Returns: 0.004312873446120739

  59. 52

    34

    "LRULUUULUR"

    "RRRRURDURL"

    Returns: 0.0060844756454618044

  60. 41

    12

    "RRDDRLRUUL"

    "RLLRRRRLUD"

    Returns: 0.01716901315354617

  61. 96

    27

    "ULURRLDRDD"

    "DLDRURULDR"

    Returns: 0.003974569187242798

  62. 74

    7

    "DRDDUDUDDL"

    "ULULLDDDUU"

    Returns: 0.015578181601347624

  63. 31

    33

    "DRRLUDRUDD"

    "UULURDLDUD"

    Returns: 0.00836001677927702

  64. 86

    43

    "LLDLUDRLRU"

    "ULLLDLRDRR"

    Returns: 0.001832806296710455

  65. 97

    48

    "LULDDDDUDL"

    "URUDRRUULD"

    Returns: 0.0017780885027337892

  66. 65

    1

    "DDDLRLRDDU"

    "DUDDRDUDDL"

    Returns: 0.050414201183431956

  67. 56

    71

    "RLURLLUDDR"

    "RURLRULLUR"

    Returns: 0.0018293867834775252

  68. 3

    13

    "DLLDDULRDU"

    "ULRDURDRLL"

    Returns: 0.2064431295200526

  69. 98

    88

    "ULDRL"

    "UULLD"

    Returns: 6.980589398012536E-4

  70. 90

    41

    "URRUURDLLL"

    "LLRRRDUULR"

    Returns: 0.002791327913279133

  71. 75

    4

    "LLLRRUDDU"

    "RRRLUULUL"

    Returns: 0.021977777777777777

  72. 9

    37

    "DRDULRRRUD"

    "RDLLDULURU"

    Returns: 0.03397090784478172

  73. 88

    34

    "LDLLUUDRUD"

    "RURRLRUUDL"

    Returns: 0.0038851375504017844

  74. 17

    78

    "RRRLLUUUDL"

    "LLLRRLLUUR"

    Returns: 0.007706412417618167

  75. 1

    1

    "UDLDRRRU"

    "LLLLLLLL"

    Returns: 1.0

  76. 100

    100

    "DDDDDDDDDD"

    "RDDDDDDDDD"

    Returns: 2.989E-4

  77. 1

    2

    "L"

    "R"

    Returns: 0.75

  78. 1

    1

    ""

    ""

    Returns: 1.0

  79. 5

    5

    "UULLDDRRUL"

    "URDLURDLUR"

    Returns: 0.2992

  80. 100

    100

    "UUUUULLLLL"

    "DDDDDRRRRR"

    Returns: 0.0018955

  81. 50

    1

    "R"

    "D"

    Returns: 0.0396

  82. 50

    1

    "D"

    "R"

    Returns: 0.0396

  83. 2

    2

    "RL"

    "LR"

    Returns: 0.5

  84. 2

    2

    "UD"

    "DU"

    Returns: 0.5

  85. 2

    2

    "DD"

    "LR"

    Returns: 0.625

  86. 4

    3

    "LR"

    "UD"

    Returns: 0.2013888888888889

  87. 3

    3

    "UDUDLRLRDU"

    "UDUDLRLRUD"

    Returns: 0.5555555555555556

  88. 100

    100

    "LRLRLRLRLR"

    "LRLRLRLRLR"

    Returns: 1.02E-4

  89. 100

    100

    "UDRLUDRLUD"

    "RLUDULRDDD"

    Returns: 5.02E-4

  90. 100

    100

    "UUUUUUUUUU"

    "LLLLLLLLLL"

    Returns: 0.00109615

  91. 100

    100

    "DULRRLDUUD"

    "LRDLRRDURU"

    Returns: 7.9989E-4

  92. 100

    100

    "UUUUUDDDDD"

    "LLLLLRRRRR"

    Returns: 6.481E-4

  93. 100

    100

    "UUUUUUUUUU"

    "UUUUUUUUUU"

    Returns: 2.1E-4

  94. 100

    100

    "UUUUURRRRR"

    "UUUUURRRRR"

    Returns: 1.69E-4

  95. 47

    38

    "DURLLRUDUL"

    "LRLUDLDRUR"

    Returns: 0.00501505425425325

  96. 100

    100

    "UUUUUUUUUU"

    "DDDDDDDDDD"

    Returns: 0.00189

  97. 100

    100

    "LULULULULU"

    "RDLUDLRULD"

    Returns: 0.00107855

  98. 100

    100

    "DDDDDDDDDD"

    "RRRRRRRRRR"

    Returns: 0.00109615

  99. 100

    100

    "UDLRUDLRUD"

    "LRUDLRUDLR"

    Returns: 3.0398E-4

  100. 100

    100

    "LLLLLLLLLL"

    "RRRRRRRRRR"

    Returns: 0.00189

  101. 100

    100

    "UDLRUDLRUU"

    "DUUDLRUDLR"

    Returns: 5.0299E-4

  102. 100

    100

    "LLLLLDDDDD"

    "RRRRRUUUUU"

    Returns: 0.0018955

  103. 100

    100

    "UUUUUDDDDD"

    "UUUUUDDDDD"

    Returns: 1.3E-4

  104. 100

    100

    "RRRRDLLLLU"

    "UUUURDDDDL"

    Returns: 0.0010034

  105. 10

    10

    "DDD"

    "DDD"

    Returns: 0.022

  106. 100

    100

    "LLLLLLLLLL"

    "LLLLLLLLLL"

    Returns: 2.1E-4

  107. 3

    3

    "LRL"

    "RLR"

    Returns: 0.3333333333333333

  108. 100

    100

    "RRRRRRRRRR"

    "LLLLLLLLLL"

    Returns: 0.00189

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: