100-doors puzzle

Question

Here is a very simple solution to the 100 doors challenge

You are in a hotel with 100 doors. Initially every door is closed. On the first round, you change the state of every door (if it is open, close it. If it is closed, open it). On the second round, you change the state of every second door. On the third round, every third door etc... Find the state of all 100 hundred doors after n rounds

"""Check which doors are open and which are closed after n rounds"""
def check_doors_round(n):
    """Check which door is open after n rounds"""
    doors = [False] * 100
    for step in range(n):
        for (index, door) in enumerate(doors):
            if (index+1) % (step+1) == 0:
                doors[index] = not door
    print(doors)

if __name__ == "__main__":
    check_doors_round(100)

Answer 1

• It would be better if you merged (index+1) % (step+1) == 0 into the preceding for loop.

  Whilst it's easy to understand what it means, it's even easier to understand what range(start, stop, step) means.

• You should return doors and print outside the function.

• I'd prefer to be able to specify how many doors to use. This can be a default argument.

def check_doors_round(n, doors_=100):
    doors = [False] * doors_
    for step in range(n):
        for index in range(step, doors_, step + 1):
            doors[index] = not doors[index]
    return doors


if __name__ == "__main__":
    print(check_doors_round(100))

Answer 2

Mathematical observation

Let's consider the i-th door after n rounds and see when its state changes.

This boils down to considering the divisors of i smaller than n. In particular, we could try to handle them by pair (p, q) such than i = p * q. Without limitation, we can assume p <= q.

• If 0 < p < q < n ("usual situation"), the door will change its state at step p and q => these divisors cancel each other
• If 0 < p = q < n ("perfect square root"), the door will change its state once => the door state changes
• If 0 < n < p <= q ("both are too big"), the door will not be changed
• If 0 < p < n <= q ("one is too big"), the door will change its state once => the door state changes

The last cases are a bit tedious to consider but using the first 2 cases, we can see than once n gets big enough, we'll have only 2 different situations:

• i is a perfect square: all pairs of divisors cancel each other except for one: the door ends up open

• i is not a perfect square: all pairs of divisors cancel each other: the door ends up closed.

Changing details in your code, this can become very obvious:

def check_doors_round(n):
    """Check which door is open after n rounds"""
    doors = [False] * 100
    for step in range(n):
        for (index, door) in enumerate(doors):
            if (index+1) % (step+1) == 0:
                doors[index] = not door
    return doors

def pretty_print_doors(doors):
    print([i+1 for i, d in enumerate(doors) if d])

if __name__ == "__main__":
    pretty_print_doors(check_doors_round(100))

Which return [1, 4, 9, 16, 25, 36, 49, 64, 81, 100].

Thus, we can rewrite the function:

import math

def check_doors_round(n):
    """Check which door is open after n rounds"""
    doors = [False] * 100
    for i in range(int(math.sqrt(100))):
        doors[i*i -1] = True
    return doors

This still needs to be generalised for various values of n...

Answer 3

One thing I would add would be to describe what your inputs should be, and to check if they are indeed the correct input type. For small scripts it's not that pressing, but in my experience it can make debugging much easier in the future.

I've also copied @Peilonrayz suggestion because I agree with it.

def check_doors_round(n, number_doors=100):
    """
    Check which doors are open and which are closed after n rounds

    :param int n: number of rounds
    :param int number_doors: number of doors to check
    :return: list of doors, with states of open (True) or closed (False)
    """

    if not isinstance(n, int):
        raise TypeError (f"n Should be an integer, not {type(n)}")
    if n < 0:
        raise ValueError ("n Should be larger than 0.")
    if not isinstance(number_doors, int):
        raise TypeError (f"number_doors Should be an integer, not {type(number_doors)}")
    if number_doors < 0:
        raise ValueError ("number_doors Should be larger than 0.")

    doors = [False] * number_doors
    for step in range(n):
        for (index, door) in enumerate(doors):
            if (index+1) % (step+1) == 0:
                doors[index] = not door
    return doors

if __name__ == "__main__":
    print(check_doors_round(100))

Answer 4

Apart from the remarks already given about returning instead of printing, and an argument for the number of doors, this code looks good.

Instead of looping over the list, you can also use slicing:

def check_doors_round_splice(n, num_doors=100):
    """Check which door is open after n rounds"""
    doors = [False] * num_doors
    for step in range(min(n, num_doors)):
        my_slice = slice(step, None, step + 1)
        doors[my_slice] = [not door for door in doors[my_slice]]
    return doors

Timing

This is a lot faster:

%timeit check_doors_round(100)

1.01 ms ± 40.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit check_doors_round_splice(100)

66 µs ± 4.65 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)