100 Doors Problem, a Simple Solution
Introduction
This weekend, I spent time honing my Python skills, and started a course called “Algorithmic Thinking with Python: Foundations” with Robin Andrews on LinkedIn Learning. I’ve taken algorithms courses in the past, but never one where I was given a challenge to solve before the instructor went through any content. Luckily for me, he started with an easy one, the 100 Doors problem.
I know that countless people before me have solved this problem, and countless more will solve it after me. I just wanted to share my experience with it because of the giddy delight I felt after solving it and seeing the pattern it revealed, simple as it is.
What is the 100 Doors problem?
We start with a hallway that has 100 doors, all of which are closed at the start. We will make 100 passes down the hallway in total. On the first pass, we will open every door, toggling its state from closed to open. On the second pass, we will only toggle the state of every other door (i.e. 2, 4, 6,…). On the third pass, we will toggle the state of every third door (i.e. 3, 6, 9,…). This will continue until the 100th pass, where only the 100th door is toggled.
After all of this, we should end up with a very specific pattern of open and closed doors.
So which doors will be open? I challenge you to try to solve this one using any method you want before moving on to the solution. If you came up with a different solution or have some insight into the pattern that is revealed, let me know in the comments!
How I solved this problem
First, let’s look at the entire solution:
Since I’m exploring implementing algorithms in Python, I approached this problem from a programming perspective, rather than a math-based perspective. Hopefully soon I will begin to be able to solve algorithmic problems through the application of mathematics, but for now, I began by thinking about how to represent the state of doors in code.
# initial state of the doors
num_doors = 100
doors = [False] * num_doorsLuckily for me, the instructor gave us the starting place, though I would have done the same. We will represent our hallway of doors with a list, a mutable sequence of Boolean values to represent whether the doors are opened or closed ( True or False, respectively). It was at this point I paused the video, since the rest was just tips and I wanted to try my hand at solving it myself. For ease of testing, I created the num_doors variable since we will be using it in several places.
From there, I wondered what the first iteration might look like. Since I knew that we would be toggling every door, I used a for loop to iterate over the sequence. I realized quickly that I would need to track which door I was on with an index, which is why I used the range() function that Python provides. I toyed with using Python’s enumerate() function, but decided that splitting the index and value of the element apart was not needed in this case.
# first pass over doors
for i in range(0, num_doors):
doors[i] = not doors[i]This left me with a list of True values, and I spent a few minutes just trying to figure out what the second, third, fourth, and so on iterations would look like. It became apparent that the use of nested for loops would become necessary to completing this algorithm, since I would need to iterate over all of the doors 100 times, while keeping track of which iteration I was on.
# the algorithm I used
for i in range(0, num_doors);
for j in range(i, num_doors, i+1):
doors[j] = not doors[j]Basically, the outer loop iterates over the list of doors 100 times, with a range from 0 to 100. As a reminder, the Python range() function excludes the upper boundary of the range, and all lists are zero-indexed by default.
This outer loop is the same one that was already written.
The inner loop is where the interesting part of the algorithm lies. Here, the elements that are toggled are decided by changing the range that the for loop will use. In every iteration, the starting point is equal to the index of the outer loop, to simulate the “every nth” door condition.
For example, on iteration 3, the starting index is 2 since the list is zero-indexed. This would be akin to starting at the 3rd door.
Next, the end point of the loop is always the end of the list in this algorithm.
Finally, the piece that makes this algorithm work is the step of the inner loop, because this finishes the implementation of the “every nth” condition for each iteration.
If we are on iteration 3, starting at the third door, we have to continue by only toggling every 3rd door. This is accomplished by setting the step to i+1 . The reason we have to use i+1 is because the list is zero-indexed, but our basic step is 1.
Think about it like this: if our step was equal to i directly, how would we step 0 times on iteration 0? We need to step at least 1 time to make the loop work, and so we add 1 to i to solve this problem.
And finally, we simply toggle each door with doors[j] = not doors[j] for each element in that new range in order to produce the answer. This is Python’s syntax for flipping the bit, and will vary across programming languages.
The Solution
If you’ve either solved the problem yourself, or ran my code from the Gist linked above, you probably already have the solution. Since I wanted an easy way to see what happened, I made use of Python’s built-in string formatting to review the final state of the doors list.
# quick printout of open doors
print("\nFinal State of doors:\n")
for index,door in enumerate(doors):
if door: # evaluates door as a Boolean value
print(f'{index+1}: Open; Square: {int(sqrt(index+1))}')Alright, there’s more there than just seeing which doors are opened. I made good use of the enumerate() function built-in to Python in order to number my doors. Then, I simply checked each doors to see if it was open ( True ), and printed out the door’s number (offset by 1 to be human-readable), its state, and the square root of the human-readable door number.
Before I dive into why I included the square root of that door number, let me just say that this is the solution. For 100 doors, the following doors will be open:
1: Open; Square: 1
4: Open; Square: 2
9: Open; Square: 3
16: Open; Square: 4
25: Open; Square: 5
36: Open; Square: 6
49: Open; Square: 7
64: Open; Square: 8
81: Open; Square: 9
100: Open; Square: 10If you solve this manually (I don’t recommend this), you’ll find this configuration after your 100th pass.
A pattern revealed?
If you’re like me, you probably looked at the door numbers that remained open and saw a pattern: it was a list of the perfect squares from 1 to 100, inclusive. To confirm this, I went ahead and found the square root of each door number, which is shown in my quick and dirty printout above.
I did quite a bit of searching online to see if anyone had developed a proper mathematical analysis of why this was the case. Instead, I mostly found “optimized” code which solves this problem in one pass by simply opening the doors that were perfect squares of {1…10}.
I can’t do a true mathematical analysis because I don’t know how (yet), but I suspect that the following is true for any number of doors.
- The solution set for this problem will be
{1,4,9,...,n}, wherenis the number of doors. Ifnis not a perfect square, the highest door number will be the highest perfect square in the set. - Given
ndoors, the number of perfect squares between1andnequals the number of open doors after thenthiteration. - Given
ndoors, the numbers of the doors that are open will be the squares of the set{1...floor(√n)}, wherefloor()is a function that rounds down to the nearest integer in casenis not a perfect square.
For example, 10 doors reveals that doors 1, 4, and 9 remain open because they are the only perfect squares in the set.
For 100 doors, the open doors are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. We could predict that there would be 10 doors open because√100 = 10.
So, for 10,000 doors, how many doors will be open? Well,√10,000 = 100.
This pattern holds, though trickier numbers like 42,501 doors may yield results that I, as a human, can’t work out in my head. I know there must be a formula out there that succinctly solves this problem, but as I said, I currently lack the analysis skills necessary to create such.
Next Steps
In order to get the most out of this solution, and to think about its practical applications, the most obvious next step is the optimization of the algorithm. While a nested for loop isn’t that bad for a small set of data, its time complexity is O(n²), which of course is horrific if you have 1,000,000 elements in a set. Basically, if we have 1,000,000 doors, our worst case scenario involves one trillion iterations. For flipping a bit one trillion times, not that bad, but the second you add any more complex operations in that inner loop, things start slowing down.
I would imagine that here, optimization begins with a proper mathematical analysis. I think that, given time, I could probably optimize this programmatically, but it would be a slower process if I didn’t quite understand the constraints of the underlying formula.
Hopefully, Part Two will come with optimized run time and a thorough understanding of the mathematical basis for this solution.
What’s the significance of this?
The most important finding from this is that I had a good deal of fun working on this problem. Overall, I solved the problem in about ten minutes, and then proceeded to spend two hours trying to find a good mathematical analysis of the pattern I found and writing this post.
I have to admit, I haven’t actually thought about the practical application of this algorithm. This will hopefully come in part two!
I hope that you found this exercise as interesting as I did! If you have a different solution, or know how to do a complex mathematical analysis of this problem, please let me know in the comments!
