Python 100 Lockers Problem

The 100 Lockers Problem, also known as the "Students' Locker Game," is a fun programming challenge that combines coding with math. Imagine a row of lockers, initially all closed. As each student passes by, they toggle specific lockers open or closed. In this tutorial, you'll learn how to simulate this game in Python, building logic to identify which lockers remain open at the end.

Problem Description

In this scenario:

1. You have 100 lockers, all starting in a closed state.
2. A student walks down the row, toggling every locker (if it's closed, they open it; if it's open, they close it).
3. The next student toggles every second locker.
4. The third student toggles every third locker, and so on, until all 100 students have taken their turn.

After every student has toggled lockers according to their rule, we want to determine which lockers remain open.

Understanding the Solution

Each locker is toggled whenever a student whose number is a divisor of that locker number passes by. For example, locker 12 will be toggled by students 1, 2, 3, 4, 6, and 12.

A locker will end up open if it's toggled an odd number of times. Only square-numbered lockers (1, 4, 9, 16, etc.) have an odd number of divisors, which means only these lockers remain open at the end of the game.

Implementing the Locker Game in Python

Let's walk through implementing this solution in Python.

Initialize the Lockers

We start by creating a list of 100 lockers, all set to False (representing closed lockers).

# Initialize lockers (all closed)
lockers = [False] * 100  # False indicates a closed locker

Simulate Students Toggling Lockers

Each student toggles lockers according to their number. So, student 1 toggles every locker, student 2 toggles every second locker, and so on. We loop through each student and toggle lockers by setting each n-th locker to its opposite state (True for open, False for closed).

# Toggle lockers for each student
for student in range(1, 101):  # Students are numbered from 1 to 100
    for locker in range(student - 1, 100, student):  # Toggle every `student`-th locker
        lockers[locker] = not lockers[locker]  # Toggle locker state

Identify Which Lockers Remain Open

After all students have toggled the lockers, we can identify which lockers remain open by checking for True values in the lockers list.

# Collect all open lockers
open_lockers = [index + 1 for index, locker in enumerate(lockers) if locker]  # +1 to adjust to 1-based indexing
print("Open lockers:", open_lockers)

Full Code for the Locker Game

Here's the complete code for simulating this locker game:

# Initialize lockers (all closed)
lockers = [False] * 100  # False indicates a closed locker

# Toggle lockers for each student
for student in range(1, 101):  # Students are numbered from 1 to 100
    for locker in range(student - 1, 100, student):  # Toggle every `student`-th locker
        lockers[locker] = not lockers[locker]  # Toggle locker state

# Collect all open lockers
open_lockers = [index + 1 for index, locker in enumerate(lockers) if locker]
print("Open lockers:", open_lockers)

Output:

Running this code should give you the following result:

Open lockers: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

As predicted, only lockers with perfect square numbers remain open.

Explanation:

The reason only square-numbered lockers remain open is that these numbers have an odd count of divisors, which causes them to be toggled an odd number of times. All other lockers are toggled an even number of times, leaving them closed at the end.

Conclusion

The Students' Locker Game illustrates a great combination of coding and mathematics. By simulating this game, you've built a solution that uses loops, conditions, and list manipulation in Python, all while uncovering a neat mathematical property related to divisors and square numbers. This challenge not only builds coding skills but also deepens understanding of algorithmic problem-solving.