Today, I presented you with a puzzle that is commonly asked during software engineer interviews. It has sparked a lot of interest, with nearly 500 comments below the original article. These comments offer unique perspectives on the problem, often with a humorous twist. Some take time to reflect on the complexities of phrasing a technical question about data structures in a fictional world. Others express frustration over what constitutes a spoiler, while some express admiration for their favorite software engineers.

Here is the puzzle and its solution once more.

The loopy labyrinth

You find yourself stuck in a dim underground passage that forms an endless circle. However, you are unsure of its total length. On the walls of the tunnel, there are switches evenly spaced and can be turned on or off. There are no other items in the tunnel, and as you walk, you cannot determine the speed of the circular path. Luckily, you have a pencil, paper, and a light source, allowing you to make notes along the way.

What is the method for calculating the total number of switches inside the tunnel?

Explanation: It is not permitted to discard any of your apparel or belongings on the ground.

Solution

If the route forms a circle, the tunnel follows a circular route and therefore has a limited length. In the end, you will return to your starting point. The challenge is determining when you have completed one full cycle, as each section of the tunnel is practically identical to the next.

One method for counting the sections is to use the switches on the walls. A strategy could be to walk along and flip all switches to the “down” position until all of them are “down”, then begin flipping them to “up” and counting until you reach a switch that is already “up”. This would only be effective if you were certain that all switches were initially “down”. However, there is no way to guarantee that you have returned to the starting point. It’s possible that the circle is very large, and you may have passed another set of 1000 “down” switches after flipping 1000 yourself. This could give the illusion of completing two loops, when in reality the tunnel may have 2001 switches.

The initial realization is that attempting to solve this puzzle by only moving forward will not work. Backtracking is necessary.

A possible strategy for this problem is as follows: Begin by setting your starting switch to the “up” position. Proceed to go through each switch and make sure it is in the “down” position, but if you encounter a switch that is in the “up” position, you must backtrack and check if you have looped back to the starting point. To do this, simply change the recently encountered “up” switch to the “down” position and return to the starting point. By keeping track of your count, you will know exactly how many switches you need to go back to reach the starting switch. If the starting switch is still in the “up” position, it means you have not gone in a circle and you can repeat the same process. However, if the starting switch is now in the “down” position, it confirms that you have gone in a circle. At this point, you will have gone through all the switches and counted them.

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 states that if he were to present the question as a coding challenge, it would be written as:

Given a circular linked list with objects that have a Boolean variable, find the total number of objects in the list. The only allowed operations are toggling the Boolean value of the current object and moving to the next or previous object. You cannot make any changes other than changing the Boolean value. However, you can keep track of the objects and their Boolean values. The initial values of the Boolean variables can be anything. How can you efficiently count the number of objects in the circular linked list while following these restrictions?

It is evident that uncertainties arise when presented as a riddle for someone without specialized knowledge.

I trust that you found today’s challenge enjoyable. I will return in a fortnight.

Since 2015, I have been posting a puzzle every other Monday. I am constantly searching for interesting puzzles. If you have a suggestion, please email me.

Source: theguardian.com