In this lesson we are going to look at a fun coding challenge in Python called “100 Doors”. It’s a great challenge for developing algorithmic thinking and Python programming skills.

Image courtesy of VectorJunky.com.

The Task

There are 100 doors in a row that are all initially closed.

You make 100 passes by the doors.

The first time through, you visit every door and toggle its state (if the door is closed, you open it; if it is open, you close it).

The second time, you only visit every 2nd door (door #2, #4, #6, …), and toggle it.

The third time, you visit every 3rd door (door #3, #6, #9, …).

Continue this pattern until you only visit the 100th door.

Which doors are open and which are closed after the last pass?

(From rosetta code)

In solving this task challenge, you will need to draw upon several aspects of your programming knowledge.

For example:

• Choosing suitable data types
• Using Boolean variables effectively
• Controlling iteration (e.g nested for loops)
• Algorithmic thinking skills

Solving the 100 Doors Coding Challenge

You may want to have a go at this challenge for yourself before reading on. I encourage you to do so, as even if you don’t succeed you will have a much clearer picture of the issues involved as you follow along with the rest of this lesson.

The first thing to consider is how will we represent the state of the doors. For beginner programmers this is not necessarily obvious.

The way I’ve implemented this is to use an array (list in Python) of Booleans, such that

• True means open
• False means closed

In solving any algorithmic problem, a really important initial step is to decide what form the data will be in.

Python allows us to create this list of Booleans with ease:

doors = [False] * 101 # So we can start at door 1. We will ignore index 0

With the above code, I have anticipated an issue with counting whereby Python counts list indices from 0 whereas the problem statement assumes the first door is numbered 1. This can cause cognitive friction, and there is more than one way to address the issue. My approach is to simply have an unused value at the start of the list, and to have 101 items in total rather than 100.

Next up we need to iterate over the doors list. Since we know the number of iterations needed in advance, we use a for loop.

for i in range(1, 101):  # 101 because of how range works
    doors[i] = not doors[i]  # Using `not` to invert the Boolean value

print(doors)

Notice how we toggled the state of each door in the above code. We accessed the doors list using i as the index, and used the logical not operator to invert the values.

OK so we have done one pass of the doors, but that’s just the start. We need to make 100 passes, with the skipping behaviour described in the problem definition.

There are two key components needed to achieve this. One is the use of nested for loops , which you can learn more about from the link.

A basic example of a nested for loop would be:

for x in range(1, 6):
    for y in range(1, 4):
        print("x:", x, "y", y)

Before running this code you should think carefully about what the output will be. Then go ahead and run it and see if you were right.

The other component is the use of a step value in our for loops.

For example, the following code

for i in range(1, 11, 2):
    print(i)

prints the values 1, 3, 5, 7, 9. It is the third argument to range which determines the step. Notice that 11 is not displayed because the upper bound for range is not inclusive.

Now we have the ingredients to solve the problem, there is just one final trick you will need to put them all together. This is to use the outer loop counter (i in this case) as a parameter in the range of the inner loop. I have put a comment explaining how this works in my solution below.

Solution for the 100 Doors Python Coding Challenge.

doors = [False] * 101  # so we can start at door 1. We will ignore index 0

for i in range(1, 101):
    # for the second pass, x = 2, so we start at door 2, for the 3rd pass we start at door 3 etc.
    for j in range(i, 101, i):
        doors[j] = not doors[j]  # using `not` to invert the Boolean value

# Print out just the positions of the open doors
for i in range(1, 101):
    if doors[i] is True:  # Or just if doors[i]:
        print(i)

When you run this code, you might notice that there is a distinct mathematical pattern to the output. This could be great avenue for further exploration…

In this lesson we have learned how to solve the 100 doors coding challenge in Python. I hope you found it interesting and helpful.

Happy Computing!

Sharing is caring!