RandomWalks

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 x₀=seed. Now, whenever you need to choose a new direction, follow these steps:

• Compute a new value x_i+1 = (x_i * 25173 + 13849) modulo 65536.
• Let d be the integer part of (x_i+1/16384). In other words, d is given by the two most significant bits of x_i+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.