Earlier today I posed the following puzzle to you, a classic interview question for software engineers. It seems to have really captured your imagination: so far the original article had nearly 500 below-the-line comments. Many are lateral approaches to the problem, often humorous. Many are meditations on the ambiguities involved when phrasing a technical question about data structures in a fantasy setting. Some are angry posts about what makes a spoiler, and some are celebrations of your favorite software engineers.
Enough done, here is the puzzle again, along with the solution.
The loopy labyrinth
You are trapped in a dark underground tunnel. You know it curves endlessly in a circular path, but you don’t know how long it is. Along the tunnel’s walls, placed uniformly and at regular intervals, are switches that can be switched between two positions: up or down. Other than that, there are no other objects in the tunnel, and if you walk along it you can’t infer anything about the rate of curvature of the circular path. However, you have a pencil and paper and a reading light, so you can write down numbers.
How do you count the number of switches in the tunnel?
Clarification: you may not drop any of your clothes or belongings on the floor.
Solution
If the road is circular, the tunnel traces out a circle, and so it must be finite in length. You will eventually end up right back where you started. The problem is how to work out when you’ve completed a cycle, since each piece of the tunnel is essentially indistinguishable from the next.
The things that can help you count the sections are the switches on the walls. One idea might be to walk along and turn all the switches to “off” until they are all “off”, then start turning them “up” and count until you get to one that is turned “up”. This will work if you can be sure that everyone is “down”. However, you can never be sure that you are back to the beginning. For all you know the circle is very large – you could have turned 1000 switches to “off” and then walked past another 1000 “off” switches. It may look like you did two loops, but maybe the tunnel has 2001 switches.
The first “aha” moment is realizing that you can’t solve this puzzle if all you do is move forward. You have to backtrack.
One strategy is this: Turn your start switch to “up” and then go count together and make sure the switches are “down”, but the moment you hit a switch that is “up” you need to backtrack and ensure that you have not looping back to the beginning. To do this, turn the recently encountered “up” switch to “off” and go back to the beginning. You kept count, so you know how far back to go back to the start switch. If it is still “up”, you have not gone in a circle, and now you can start the same process again. However, if it is “off”, the ignition switch should be the switch you just flipped, and you can be confident that you have gone in a circle. Once you get to this stage, you have counted all the switches.
Thanks to Brian RabernReader in Philosophy at the University of Edinburgh, for suggesting this puzzle, which he uses in his “Puzzles and Paradoxes” class.
He says that if he were to pose the question as a coding problem, it would go something like:
Consider a circular linked list containing objects, each with a Boolean variable. Your task is to determine the total number of objects in the circle. The catch is that you can only set the Boolean variable of the current object to True or False, and move to the next or previous object in the list. No references, marks or changes other than changing the Boolean value are allowed. In addition, you are allowed to count objects and remember the values of the boolean fields. The initial values of the boolean variables in the list are arbitrary. How would you efficiently count the number of objects in the circular linked list under these constraints?
You can see how ambiguities creep in when posed as a puzzle for the lay reader!
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
I’ve been doing a puzzle here on alternate Mondays since 2015. I’m always on the lookout for great puzzles. If you want to suggest one, email me.
