puzzle on parks A park contains paths that intersect at various places.  The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each other.  The one exception is an intersection where there is a restaurant.  The restaurant is reachable from everywhere in the park.  Your task is to find your way to the restaurant.
The park has strict littering regulations, so you are not allowed to modify the paths or intersections (for example, you are not allowed to leave a note an intersection saying you have been there).  However, you are allowed to do some bookkeeping on a pad of paper that you bring with you at all times (in the computer-science parlance, you are allowed some state).  How can you find the restaurant?
You may assume that once you enter an intersection, you can continue to the left, continue to the right, or return to where you just came from.
 A: Enumerate all finite strings over the alphabet $\{L,R\}$ (or at least an infinite subset that contains all fintite strings as prefixes).
For each string $a_1\cdots a_n$ perform the following move sequence: $a_1,\ldots,a_n,\text{turn around},\overline{a_n},\ldots, \overline{a_1},\text{turn around}$ (where $\overline R=L$ and $\overline L=R$). Each such group will take you back to your startng position. By assumption a path to the restaurant occurs as a prefix of one of tthe strings enumerated, hence sooner or later you run tinto the restaurant.
It is a nice exercise to do this with only memory for two integers plus one bit flag on your scratchpad:


*

*Let $a\leftarrow 1, b\leftarrow 1, f\leftarrow 0$

*If $f=0$, let $a\leftarrow a+1$.

*If we are at the restaurant, terminate. Otherwise follow the road to the next intersection

*If $a=1$, turn around, let $a\leftarrow b$, $b\leftarrow 1$, $f\leftarrow 1-f$ and go to step 2

*If $a$ is even, turn left, let $a\leftarrow a/2$, $b\leftarrow 2b+1$ and go to step 3.

*turn right, let $a\leftarrow (a-1)/2$, $b\leftarrow 2b$ and go to step 3.
A: Isn't this a graph traversal problem, where we will definitely get to a restaurant if we traverse every node in the graph using either Depth First Search or Breadth First Search. Implementing the above mentioned algorithms is not tough also in the above mentioned case since we have a pen and a paper where we can keep track of everything for e.g. in case of depth first traversal nodes which are yet to be visited are kept on a stack, similar we can do here also by marking roads which we did not take on the paper from a particular intersection and coming back to it once we reach an end of the park or analogously the depth of the graph. 
