Statistics

Problem Statement for "RobotTesting"

Problem Statement

A robot is placed randomly on a cell in a NxN square grid. The robot has a program consisting of several commands, where each command is either 'U' (move up), 'D' (move down), 'L' (move left), or 'R' (move right). The commands are executed in order, and the program is cyclical (i.e., after the last command is executed, it will start over from the first command). The robot stops moving only if it has left the grid or if it has executed 50,000 commands.

You will be given an int N and a String program. Return the expected number of commands that will be executed before the robot stops. You can assume that all the cells in the grid are equally likely to be the starting cell.

Definition

Class:
RobotTesting
Method:
estimateCommands
Parameters:
int, String
Returns:
double
Method signature:
double estimateCommands(int N, String program)
(be sure your method is public)

Notes

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

Constraints

  • N will be between 1 and 1000, inclusive.
  • program will contain between 1 and 50 characters, inclusive.
  • Each character in program will be either 'U', 'D', 'L' or 'R'.

Examples

  1. 2

    "L"

    Returns: 1.5

    If the robot starts in the left column, it will leave the grid after the first command. Otherwise, it will leave the grid after the second command. These two scenarios are equally likely, so the answer is 1.5.

  2. 2

    "LURD"

    Returns: 12501.0

    If the robot starts in the bottom right corner, it will execute 50,000 commands.

  3. 4

    "LDLDLDRRR"

    Returns: 3.375

  4. 29

    "RRULDD"

    Returns: 53.236623067776456

  5. 697

    "LLLLLDRRRRR"

    Returns: 3806.5179340028694

  6. 66

    "DLRDUDLULDDDUURLDLRULLURLUUD"

    Returns: 213.15197428833793

  7. 51

    "RLDDULRLRURRLRURUDR"

    Returns: 103.481353325644

  8. 73

    "LRURULRLDDDRLDLRDDURLURR"

    Returns: 266.6605366860574

  9. 88

    "DDLULL"

    Returns: 78.43556301652892

  10. 73

    "UURUDUUDUDUURLRLRLRULLLDLDDUUDLDUDLDLULDLLDDRRULUR"

    Returns: 237.47119534621882

  11. 42

    "DULLLRD"

    Returns: 58.85997732426304

  12. 79

    "DUULUUDLURRULLLDRUDDURRRDU"

    Returns: 275.6015061688832

  13. 25

    "ULLDLDUUR"

    Returns: 40.6224

  14. 88

    "DRUDUD"

    Returns: 174.5056818181818

  15. 65

    "RRLRRUDURLDULDRRURLUUUDLUURDR"

    Returns: 133.96686390532545

  16. 954

    "UDUULLLRRLLLDDLRLLLUDRRRLLRRLLDRLLLLRUU"

    Returns: 2217.1923183418376

  17. 307

    "UDLLDDRLDLLRRRDRDRULULURDRL"

    Returns: 1332.9329541958004

  18. 930

    "LUULLDLDUDDUUUUDLLLDRDUDDDU"

    Returns: 1962.5497028558214

  19. 930

    "LDULRDRRRDRDRLULDULRLD"

    Returns: 3010.663949589548

  20. 670

    "DUUUULULURLLUDRLUUUURRULDRLUDLLLR"

    Returns: 1037.169213633326

  21. 1000

    "DLDDUDRUUDRLDULDURRDLDDLUURDLDRDLRL"

    Returns: 2747.376861

  22. 327

    "LRDDDLURUDDDDLLULRURDDDDDDLLR"

    Returns: 486.80405689756753

  23. 226

    "UDDDLRRDULDRLUUDDRLDDLDRRDLLULD"

    Returns: 446.67125460098674

  24. 879

    "UURUDLDURRURRDULRDDLULDDULDLURULDUDRLLULR"

    Returns: 7433.544766586293

  25. 420

    "DRULLLRUDLRDUDU"

    Returns: 3103.766150793651

  26. 921

    "DDRRLUDDLULULDRUDRRUUUDDUDD"

    Returns: 5131.5840922568

  27. 391

    "RRL"

    Returns: 584.0051150895141

  28. 164

    "DRULDDDDRUDULDUDRDUDLLUDRLLURU"

    Returns: 701.4128866745984

  29. 35

    "LDUUUURDRULLRURDDLDRRRULURURLLLRLRDDDRURLR"

    Returns: 127.75836734693878

  30. 185

    "UURDLLRLLRLRD"

    Returns: 1166.4306793279766

  31. 2

    "LULRULUDULURLUUD"

    Returns: 1.75

  32. 995

    "LDURULRU"

    Returns: 1986.5040185853893

  33. 912

    "DDRLUDLRUUUURDULRDDRULRUDRDRUDRRDRDLDUDLUD"

    Returns: 3042.526143861573

  34. 987

    "DURULUDULRRULL"

    Returns: 2041.5096199940667

  35. 629

    "LDURLULUDUR"

    Returns: 1436.0963727217352

  36. 683

    "DDDDLDULURURU"

    Returns: 4374.342035932252

  37. 762

    "LRDDUUUDRDLRRDRDRD"

    Returns: 1141.3815556520003

  38. 837

    "ULRDUDLUULULUURRDRLL"

    Returns: 1739.0753830100962

  39. 156

    "DRDLLDRRLUUDRRDLDLUDDULUDUDUDRDRUR"

    Returns: 535.9019559500329

  40. 777

    "DDLUDRDDRUDRDRLRLURLDUDRDDLUDLLDRLDURULLD"

    Returns: 1892.720907890792

  41. 40

    "DDRRLURRDDRRRDUR"

    Returns: 39.419375

  42. 232

    "RULRRLRRUDRLDLULLULLLLLRUUDULDDUURRLURLUUULLURDRDR"

    Returns: 684.5865598989297

  43. 67

    "UUDDDULLLDRLRURLLDRLLDDLLLULLDDRUD"

    Returns: 115.36466919135665

  44. 3

    "DRLRDLURLRRRDRRDULLURLRDDRLRRUDDDLLLUR"

    Returns: 4.444444444444445

  45. 36

    "URUU"

    Returns: 21.88888888888889

  46. 868

    "RUDUDURLDRLDRUULLDLRDUDRDULUUULLRRRDDULDDRLRLLLRUR"

    Returns: 49540.37930833104

  47. 998

    "UUULDDULRRRURURLDRLRRURULLLRLUULDRDDDDDUULRLRLLDDD"

    Returns: 49301.256425677006

  48. 491

    "ULLDRUDDRLDDLRLRRRLDLUDLURRURRUDULURUDRLUDLDLUDULR"

    Returns: 48987.1460629415

  49. 791

    "LURDRUDLRLUUDUUURLDRDLURDULUDRLRDLLURLRDLDLLDDURRR"

    Returns: 49432.92975014425

  50. 780

    "ULRLUUDUURUULRRLLUDLDDDRDDRLRDLDLRDRUURLRLLDLUURDR"

    Returns: 49233.20014464168

  51. 459

    "LDUUURDULRUULLDLULDDURLRDDRDDRLURRLDDLURLRULRRUDRL"

    Returns: 48809.22748135807

  52. 363

    "RLRDRDUULDDRLDDDRRDRLDLLLLRRUUUULURRDDRUULLULURLDU"

    Returns: 48360.84063778279

  53. 432

    "URUDRLDDRDLURDDLLLLUULRRRDRLDUURLLDULLRUDRUUDDRLUR"

    Returns: 48849.5269633059

  54. 448

    "DURULLRDRRDRRLDDUUUDLURDULURLRDDLLRRLLUULULLDUDDRR"

    Returns: 48780.16229870855

  55. 213

    "RUDLDRUULLLRURLDLLLDRRLDRRDURUDULLUDRDLUDRURUDLDUR"

    Returns: 47909.855716458376

  56. 464

    "RLURLLULDUDRDLUULLURRDRDDURRUULUDRRDLUURLRDLDDLLDR"

    Returns: 48928.29982907254

  57. 194

    "DLDRLRLDRLDRLUUDLUDRRRDULLRUUDDUDDURUULURRLRRLLLUD"

    Returns: 47456.903682644275

  58. 115

    "RURLDRLUUDLLDDRUURLDRDRULRRUDUUDURLDLLURLDDLLDULRR"

    Returns: 46156.28234404537

  59. 590

    "RLULRLLUUDDDURRRULDRLLRRLDUUDRUDRLDDLDLLRUUDLRURUD"

    Returns: 49240.39514507326

  60. 100

    "LRUUDRRDLLRDLUDRRDUUDRULLRUUDLRRRLRLDUDRLUDULLDDLU"

    Returns: 45601.025700000006

  61. 269

    "RULDLRRLRLRRUDRDRRLDRDDLDDLULDUDULLDRUULUUUDRULLUR"

    Returns: 47613.40326971711

  62. 138

    "LRDLRLUURDULURLRRDLLUULRRLRUDLUUURDDRRLDRDULDDLDUD"

    Returns: 46089.54673387944

  63. 303

    "RUDDRLLLUURURULDDRRDLRURURRUUULDLUDLLRDDDLLUDLRRDL"

    Returns: 48040.000152490495

  64. 722

    "ULULLRRRLLLRRDRUDLDRDDUULULLUURRRDLUUDDLLRDRUDUDDR"

    Returns: 49378.63026104773

  65. 178

    "UDLDLLDLRLUURURUDRLLUDRRDDRUDDLLURRUULLRDRDDRLLUUR"

    Returns: 47503.9954551193

  66. 1000

    "LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRD"

    Returns: 24499.9765

  67. 1000

    "LR"

    Returns: 49950.001

  68. 1000

    "UD"

    Returns: 49950.001

  69. 999

    "UDLR"

    Returns: 49899.9540010481

  70. 997

    "ULRD"

    Returns: 49899.75240566232

  71. 1000

    "LLLLLLLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 16079.5706

  72. 2

    "LRR"

    Returns: 2.0

  73. 4

    "LRRUDDD"

    Returns: 4.5625

  74. 3

    "LRR"

    Returns: 3.3333333333333335

  75. 3

    "UDDLLL"

    Returns: 3.0

  76. 1000

    "LLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRD"

    Returns: 16090.989800000001

  77. 1000

    "LLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRD"

    Returns: 23936.212

  78. 1000

    "LDLDLDLDLDRDRDRDRDRDRURURURURULULULULULU"

    Returns: 49005.25817

  79. 1000

    "LLLLLLLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRRRRRRRD"

    Returns: 12212.5

  80. 1000

    "LRU"

    Returns: 1499.9995

  81. 999

    "LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRL"

    Returns: 24452.0

  82. 1000

    "LR"

    Returns: 49950.001

  83. 1000

    "LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR"

    Returns: 49950.001

  84. 998

    "LURDLDLDLLURUDURDDUDURUDUDDLLLRUDURDRDDDD"

    Returns: 3210.500032128385

  85. 1000

    "RDULRDULDRULDRULDRUULDRLURDULDRLUDRULDRULDRULDRLU"

    Returns: 24422.085469

  86. 1000

    "UDLRUDLRRRRRRUDDDLLL"

    Returns: 3312.881525

  87. 997

    "LLLRRRLLLRRRRLLLLRRRLRLRRLRLLRUUUDDDUDUUDUDDUDUDUD"

    Returns: 49649.66541651031

  88. 1000

    "LLLLLDRRRRR"

    Returns: 5473.0125

  89. 1000

    "LRRLUDDU"

    Returns: 49800.21597600001

  90. 1000

    "URDL"

    Returns: 49900.05299800001

  91. 1000

    "ULDR"

    Returns: 49900.05299800001

  92. 1000

    "LDRULDRULDRULDRULDRULDRULDRULDRULDRULDRULDRULDRU"

    Returns: 49900.05299800001

  93. 1000

    "LRUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDLRD"

    Returns: 21609.6697

  94. 1000

    "UD"

    Returns: 49950.001

  95. 1000

    "ULDRU"

    Returns: 2496.003499

  96. 1000

    "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: 500.5

  97. 1000

    "RRRRRRRRRRRRLLLLLLLLLLLLUUUUUUUUUUUUDDDDDDDDDDDDD"

    Returns: 23652.896800000002

  98. 1000

    "LD"

    Returns: 667.1665

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: