I'm posting this from my phone again because I've gotten hopelessly lost in Boston, really want to go home, and desperately need the help of some clever people on the internet. Please help me - I'm really lost and I would like to, after some finite amount of driving, get back home and I don't know any better way to do that than to ask about my problem on a puzzling site.

I'm not very good at remembering things, so any approach based on recalling whether I've been at a location before isn't going to work. However, I'm really good at following directions, so what I'd really like is to be given a list of numbers. Each time I reach an intersection, I'll read the next number, count that many turns from the right, and follow that road - so at a standard* 4 way intersection, a $1$ will tell me to turn right, a $2$ to go straight, a $3$ to turn left and a $4$ to make a U-turn (and a $5$ brings me back to turning right and so on). I define an intersection as any moment at which I have an opportunity to turn (so if a street branches off from the one I'm on, that's a 3-way intersection).

From my extensive experience as a driver, I have observed the following: there are only finitely many intersections and that, at each, only finitely many roads meet. Also, I'm quite sure that it is possible to get back to my house from any point in the road network (Boston's not that bad**). Finally - and I'm quite proud of this - if I drive by my house (which is located by a road), I will definitely recognize it.

Can any of you suggest a sequence$^{***}$of instructions that will get me home?

(*Of course, Boston's road network is so messed up that there are approximately zero standard intersections. This doesn't affect the answer though.)

(**For the purposes of this question.)

(***Given that I do not know how many roads there are in this city, this sequence is necessarily infinite. Please do not try to write an entire infinite sequence in your answer - a mathematical construction is expected instead).

  • 2
    $\begingroup$ Possible duplicate of puzzling.stackexchange.com/questions/22373 ? $\endgroup$ Nov 25, 2015 at 17:38
  • $\begingroup$ are we to assume all intersections are standard? if not, define intersection - if I drive past an opportunity to turn right (where left is not an option), was that an intersection? If my next number is 1, should I have turned right at it? $\endgroup$ Nov 25, 2015 at 17:53
  • $\begingroup$ 1. Become cyborg 2. Hack CIA to acquire map 3. Apply Dijkstra's path finding algorithm 4. Teleport to home 5. Fool CIA because they think you are still in Boston 6. $ \operatorname{Profit} $ $\endgroup$
    – AvZ
    Nov 25, 2015 at 18:34
  • 3
    $\begingroup$ @GentlePurpleRain: It's not a dupe. The other one started with a specific sequence of turns and the knowledge that you passed a building, asking whether you would pass it again. In addition, it guaranteed that all intersections were 4-way. They're entirely different. $\endgroup$
    – Deusovi
    Nov 25, 2015 at 20:27
  • 2
    $\begingroup$ @GentlePurpleRain I did see that question before I posted this one, but there's nothing beyond superficial similarity (i.e. that they're both graph theory based); there, you are given a sequence and asked about the result. Here, there is an intended result, and you are asked for a sequence. The answers are totally different. $\endgroup$ Nov 25, 2015 at 20:55

1 Answer 1


For any number $n$, there are finitely many connected graphs with $n$ edges. So we can make lists of all the graphs with no edges, all the graphs with one edge, all the graphs with two edges, and so on. If we join these lists together, we can make an infinite list that is guaranteed to contain every finite graph.

Now, for each graph, there are finitely many ways to choose a starting point, ending point, and starting direction, so we can make a list of every possible starting situation.

Once we have this list, assume that we started in the first situation on the list, and try to get to the target based on that. If that doesn't work, we assume that we started in the second situation and figure out where we ended up. Then, we go to the target from there. If we still aren't done, we keep continuing down the list in the same way.

Because the list contains every possible starting situation, eventually we will reach the right one, at which point we will arrive at the target.

  • $\begingroup$ Might take a while, though. Better pack a lunch. $\endgroup$ Sep 15, 2016 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.