Earlier today I set you the following puzzle, a classic interview question for software engineers. It seems really to have caught your imaginations: so far the original article has had almost 500 below-the-line comments. Many are lateral takes on 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 furious posts about what makes a spoiler, and some are celebrations of your favourite software engineers.
Enough already, here is the puzzle again, together 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 do not know how long it is. Along the tunnel’s walls, placed uniformly and at regular intervals, are switches that can be toggled between two positions: up or down. Apart from that there are no other objects in the tunnel, and when you walk along it you can deduce nothing about the rate of curvature of the circular path. You do have a pencil and paper and a reading light, however, so you can jot numbers down.
How do you count the number of switches in the tunnel?
Clarification: you are not allowed to drop any of your clothing or possessions on the floor.
Solution
If the path is circular, the tunnel maps 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 have completed a cycle, since every stretch 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 flipping all switches to “down” until all of them are “down”, and then start flipping them “up” and counting until you get back to one that is flipped “up”. This would work if you could be sure that all of them are “down”. However, you can never be sure you have got back to the beginning. For all you know the circle is very large – you could have flipped 1000 switches to “down” and have then walked past another 1000 “down” switches. It might look like you have done two loops, but maybe the tunnel has 2001 switches.
The first “aha” moment is to realise that you cannot solve this puzzle if all you are doing is moving forward. You must backtrack.
One strategy is this: Toggle your starting switch to “up” and then go along counting and making sure the switches are “down”, but the moment you hit a switch that is “up”, you need to backtrack and ensure that you haven’t looped back around to the start. To do so, toggle the recently encountered “up” switch to “down”, and go back to the start. You have been keeping count, so you know how far back to go to get back to the starting switch. If it is still “up”, you haven’t gone in a circle, and now you can start the same process again. If it is “down”, however, then the starting switch must be the switch you just toggled, and you can be confident that you have gone in a circle. Once you have got to this stage, you have counted all the switches.
Thanks to Brian Rabern, Reader in Philosophy at the University of Edinburgh, for suggesting this puzzle, which he uses in his class “Puzzles and Paradoxes.”
He says that were he to pose the question as a coding problem, it would read 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 toggle the Boolean variable of the current object to True or False, and move to the next or previous object in the list. No references, markings, or alterations beyond changing the Boolean value are allowed. Additionally, you are permitted 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 set as a puzzle for the lay reader!
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
I’ve been setting a puzzle here on alternate Mondays since 2015. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
