# Lost In Boston: How do I Get Home?

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

• Possible duplicate of puzzling.stackexchange.com/questions/22373 ? Nov 25, 2015 at 17:38
• 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? Nov 25, 2015 at 17:53
• 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}$
– AvZ
Nov 25, 2015 at 18:34
• @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.
– Deusovi
Nov 25, 2015 at 20:27
• @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. Nov 25, 2015 at 20:55

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.