I came across the following puzzle this morning:

A 10-story building has 10 rooms per floor, all facing forward. A single lamp illuminates each room. A switchboard in a rental office near the building has 100 switches to control the 100 lights. The lights start in the 'all off' state, but 100 people walk through the rental office and tamper with the switches. The first person toggles every 1st switch (thus turning all lights on). The second person toggles every 2nd switch (this turning half the lights off). The third person toggles every 3rd switch. The fourth person toggles every 4th switch. And so on for all 100 persons. Which lights are now on, and which are off?

Let's reason about the puzzle and see if we can grab some intuition before actually writing some code:

Let L be a list of 100 elements representing the following states:

Initially, L is a list of 100 zeros: L = [0,0,...0], i.e all the lights are off. Per the puzzle, every person will individually toggle the switches.

We can represent this with a for loop as follows:

for i in range(1, 101):

In our case, each one of them will toggle the j-th switch if j is a multiple of i. We can represent this operation using the XOR operator ()[PS] as follows:

Lj = Lj ^ (j % i == 0)

The XOR operator toggles the j-th light if j is a multiple of i.

We iterate through all the togglers w/ the following for-loop:

for j in range(i-1, 100, i): Lj = Lj ^ 1

At the end of this process, we'll get the following results:

Now, we can simply represent the state of each light using the parity of its number of toggles:

Lj = 1 if the number of toggles of the i-th light is odd
Lj = 0 if the number of toggles of the i-th light is even

Then we compute the parity of the number of toggles using the modulo operator (%) w/ 2 since there are only two states (on | off):

Lj = sum((j % i == 0) for j in range(1, 101)) % 2

The final state of the lights can be represented as a list of 100 elements L = [L1, L2, ..., L100], where the following is true:

Here's the code

Happy hacking!

#logic #puzzles #python