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.
|