14
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Does it mean n < 100? \$\endgroup\$ – IEatBagels Jun 14 at 18:40
  • \$\begingroup\$ Sorry. I don't understand the question \$\endgroup\$ – EML Jun 14 at 18:41
  • \$\begingroup\$ If "Find the state of all 100 hundred doors after n rounds" and there're 100 doors, it means that n cannot be bigger than 100? Or there are n doors, and n rounds? \$\endgroup\$ – IEatBagels Jun 14 at 18:44
  • \$\begingroup\$ I see. Good point. Yes. For n<=100 \$\endgroup\$ – EML Jun 14 at 18:45
14
\$\begingroup\$
  • 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))
\$\endgroup\$
  • \$\begingroup\$ True. The step argument in the for loop is more elegant. Thanks. \$\endgroup\$ – EML Jun 13 at 11:25
  • 4
    \$\begingroup\$ To make the function marginally nicer to use, the parameter should probably by doors and the local variable doors_, or the parameter could be num_doors or the like. \$\endgroup\$ – jirassimok Jun 13 at 14:48
  • \$\begingroup\$ @jirassimok That could be an improvement, but since it's a positional and keyword argument I don't think many will use check_door_round(1, doors_=2) over check_door_round(1, 2), :) \$\endgroup\$ – Peilonrayz Jun 13 at 14:54
12
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ I like the pretty_print_doors function. Certainly makes the output easier to read. I was keen to keep the function completely generalisable for any value of n, however small. Thanks though for your insight \$\endgroup\$ – EML Jun 13 at 13:22
  • 1
    \$\begingroup\$ Bugs in your rewrite: you loop starting at 0, and set doors[i*i-1], or doors[-1] (the last door), to True. And the argument n is unused. \$\endgroup\$ – AJNeufeld Jun 13 at 13:56
  • \$\begingroup\$ @AJNeufeld The argument n is unused because I've covered the case where "n gets big enough" and I plan to let OP perform the adaptation for other values of n based on the insight provided. As for the other point, good catch. I'll need to update my answer asap (but the idea is worth more than the actual code using it) \$\endgroup\$ – SylvainD Jun 13 at 15:50
4
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Thanks for this. Is it better to raise exception when dealing with type errors then? I usually just print a message to the terminal? \$\endgroup\$ – EML Jun 14 at 9:10
  • 2
    \$\begingroup\$ If you raise an exception, you can let the caller decide how to handle it. Also if you use any code somewhere the user can not see the terminal, printing to the terminal is not really useful. I would use a less generic Exception like TypeError or ValueError \$\endgroup\$ – Maarten Fabré Jun 14 at 9:16
  • \$\begingroup\$ @MaartenFabré thank you, I've updated it! \$\endgroup\$ – Nathan Jun 14 at 9:39
4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ That's a really smart idea! Thanks \$\endgroup\$ – EML Jun 14 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.