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