Statistics

Problem Statement for "RandomWalks"

Problem Statement

Fix a coordinate system in the plane. We will now make a random walk according to the following rules: Start at the point (0,0). In each step randomly choose one of the four basic directions, and move by 1 in this direction. You are forbidden to walk along the same line segment twice (regardless of the direction). Should a random choice require you to do this, ignore it and make a new choice. The walk ends as soon as you reach the point (0,0) again.

To make our random choices, we will use a generator of pseudorandom numbers. Our generator will work as follows: Given is an int seed. Set x0=seed. Now, whenever you need to choose a new direction, follow these steps:

  • Compute a new value xi+1 = (xi * 25173 + 13849) modulo 65536.
  • Let d be the integer part of (xi+1/16384). In other words, d is given by the two most significant bits of xi+1.
  • The value d=0 corresponds to a move by (0,+1), denoted 'U'.
    The value d=1 corresponds to a move by (0,-1), denoted 'D'.
    The value d=2 corresponds to a move by (-1,0), denoted 'L'.
    The value d=3 corresponds to a move by (+1,0), denoted 'R'.

A random walk can be uniquely described by a string of letters 'U', 'D', 'L', and 'R'. The length of the walk is the number of steps made, or equivalently the number of letters in its representation. Write a method that will simulate the random walk and return its representation as a String.

If the length of the walk exceeds 40, return only the first 20 and the last 20 characters, separated by three dots. (See Example #2.)
If the length of the walk exceeds 200,000, return an empty string.

Definition

Class:
RandomWalks
Method:
generateWalk
Parameters:
int
Returns:
String
Method signature:
String generateWalk(int seed)
(be sure your method is public)

Notes

  • You can not get stuck during the random walk.
  • You are allowed to pass through a vertex twice, only using a previously used line segment is forbidden.

Constraints

  • seed will be between 1 and 65,535, inclusive.

Examples

  1. 9

    Returns: "LDRU"

    This random seed leads to a simple random path with only four steps. For reference, the generated random values are x1=43798, x2=28775, x3=63052, and x4=5461.

  2. 21

    Returns: "DLUR"

    Again a path with four steps, but this time we have to ignore the third generated direction 'R'.

  3. 124

    Returns: "RULUURDLLURULDLDLLLD...RURRUUURULDLDDDDRRRR"

    The generated path for this seed has length 42. Note that we still use three dots in the returned String, even though only two characters are left out.

  4. 3

    Returns: "DDRRURDDLURRDRRRRDDL...RDRULUURDLLLDDRDLLDD"

    This path has length 6082.

  5. 2

    Returns: ""

    This path doesn't return to (0,0) soon enough.

  6. 107

    Returns: "DRDLDDDRDDDRRURRRUUU...URDDDRDLLDDDLUUULLUL"

  7. 212

    Returns: "LLDLDLLDLUURRUUUURDDDDLDDRURRDRDLULUURRU"

  8. 258

    Returns: "DDRUUL"

  9. 14760

    Returns: "LURULUURDLLLULLDDDRR...DLLURUUULLLDRRDDLULD"

  10. 14761

    Returns: ""

  11. 25285

    Returns: "DLULDLDLLUULURDRRDLD...LLULLDRDLDLLLLLLLLDD"

  12. 31649

    Returns: "RDDLURRURRDRDRDRURUR...UURDRDDLUULLULLULLDD"

  13. 58053

    Returns: "RULURURUULLULDRDDRUR...UULUURDRURUUUUUUUURR"

  14. 64417

    Returns: "DRRULDDLDDRDRDRDLDLD...LLDRDRRULLUULUULUURR"

  15. 24

    Returns: ""

  16. 47000

    Returns: "DDDLULLUURRDLUURDR"

  17. 47013

    Returns: "DLUR"

  18. 47026

    Returns: "DRDRURULDLUUURRDDRRU...RRDRRUUULUULDRRDRDRR"

  19. 47039

    Returns: "DDRRRURDLDLLDDRRRDDR...LULUUUULURURDRURDRUR"

  20. 47052

    Returns: "DRDRUULDRRUURRRDRULUURDLLLURDDDLUULLLLDD"

  21. 47065

    Returns: "DDDRRDLUUUURDLLLDLULDLLLDRUURURRDRUR"

  22. 47078

    Returns: ""

  23. 47091

    Returns: ""

  24. 47104

    Returns: "DLDRDLULDLULLDLULLLL...URRRRULULULDRDLDDRDD"

  25. 47117

    Returns: "DLUR"

  26. 47130

    Returns: ""

  27. 47143

    Returns: "DDRURDDRDRULURRDLUULLULL"

  28. 47156

    Returns: "DLULLURRRD"

  29. 47169

    Returns: "DRRURRULLDLL"

  30. 47182

    Returns: "DDLLLDDDLLUURRRDRULU...RURULUUUULLDLULDRDDR"

  31. 47195

    Returns: "DRURURURULLDRUURDRUL...DRRRURDDDDDRDLULLDRD"

  32. 47208

    Returns: "DDDLLLULURUURDLLLULL...LURDDDRRDRUULULDDDRD"

  33. 47221

    Returns: ""

  34. 47234

    Returns: ""

  35. 47247

    Returns: "ULURRDLUULURURUURRDR...ULLLLDDDRUURUULDDLLU"

  36. 47260

    Returns: ""

  37. 47273

    Returns: "ULDR"

  38. 47286

    Returns: "URURRULLLULULDDRDDDR"

  39. 47299

    Returns: ""

  40. 47312

    Returns: ""

  41. 65532

    Returns: ""

  42. 65533

    Returns: ""

  43. 65534

    Returns: ""

  44. 65535

    Returns: "RRDLLLDDDDLLLULLLDDD...LURRUUULUURURDDRDDDD"

  45. 64123

    Returns: "DLULULDDDRULLDRDLDRR...LLDDDDDLDDDDRRULDDDL"

  46. 61342

    Returns: ""

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: