Finding a Restaurant in a Park


I got this problem from Rustan Leino, who got it from Michael Jackson, as a variation of a problem he got from Koen Claessen.

I solved it and wrote up my solution.


A park contains paths that intersect at various places. The intersections are all three-way intersections and, with one exception, they're indistinguishable from each other. The one exception is an intersection where there's a restaurant.

Once you enter an intersection, you can continue to the left or continue to the right, but you can't turn around to exit the intersection the way you just entered it. Fortunately, even with this restriction, 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're not allowed to modify the paths or intersections. (For example, you're not allowed to leave a note at an intersection saying you've been there.) However, you're allowed to do some bookkeeping on a pad of paper that you bring with you at all times. (In computer-science parlance, you're allowed some state.)

How can you be certain to find the restaurant? Note that it's not sufficient to use a probabilistic algorithm to find the restaurant with probability one; you must use an algorithm that's guaranteed to eventually reach the restaurant.

Solution     Reveal