Classic Algorithms: Solving the 100 Doors Riddle

Today we will talk about the 100 Doors task of the Rosetta Code project. This one uses a lot of control flow elements and the set-function we discussed yesterday.

If you are new to PicoLisp, it might be helpful to read the article on Control Flow functions
first.

---

The Task

There are 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, visit every door and toggle the door (if the door is closed, open it; if it is open, close it). The second time, only visit every 2nd door (door #2, #4, #6, ...), and toggle it. The third time, visit every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.

Answer the question: What state are the doors in after the last pass? Which are open, which are closed?

There is a straightforward and a "smart" implementation. Let's start with the straightforward one.

---

Defining the doors

If we implement it in a straightforward way, we need to take our "door" route 100 times. Each door has two possible states, "open" or "closed". We can translate this to NIL and T. For each door we interact with, we swap the status from T to NIL and vice versa.

First, let's define a list called "Doors" that has 100 elements, each initialized with NIL. This can be done using the function need:

: (setq Doors (need 100))
-> (NIL NIL NIL NIL NIL ...... NIL NIL NIL)

---

Toggling the first door

Let's first try to change the status of one door. Toggling between NIL and T is a simple negation, we can do it with the not function. Like this:

(set Doors (not (car Doors)))

(car Doors) returns the value of the first item in the list, which can be either NIL or T. After reversing it with not, we set it again to the first item of Doors.

You might be tempted to write something like (set (car Doors) ...) to get the first element, but this is wrong because set already addresses the first item. If this sounds confusing for you, check out this post about the set function.

---

Toggling every third door

Now we now how to change one door. But how to change all doors that are, for example, dividable by 3?

If we did it "on foot", our algorithm would be something like:

1. Walk three doors
2. Toggle the door that is in front of us
3. Repeat

After toggling a door, it would be nice if only those doors remained in the list that we haven't already "done" yet. It means, we want to shorten our list by removing items from the beginning. This is exactly what the function nth is doing:

: (setq L (1 2 3 4 5))
-> (1 2 3 4 5)
: (nth L 3)
-> (3 4 5)
: (cdr (nth L 3))
-> (4 5)

Translating our "foot" algorithm to PicoLisp:

• (nth Doors 3) --> "walk three doors"
• (set Doors (not (car Doors))) --> "toggle the door in front of us"
• ?? --> "repeat"

We want to repeat this step until we have walked down the whole Doors list. But how can we check that? We could put a counter that tells us when we have reached 100. But what if we need to walk down 200 doors tomorrow?

Luckily, there is a more flexible alternative - a variation of the for loop designed for these kind of cases. Let's read the documentation:

(for (sym 'any1 'any2 [. prg])) -> any

In the third form, the value of sym is saved, and sym is bound to any1. [...] While the condition any2 evaluates to non-NIL, the body is repeatedly executed and, if prg is given, sym is re-bound to the result of its evaluation.

Sounds complicated, so let's try it step by step.

---

In simple words, we want to "walk 3 doors", do our job, and continue walking until there are no doors left. Everytime we walk 3 doors, our Doors-List should get shorter.

So, first let's "bound sym to any", like the documentation tells us. We use a symbol D and bind it to the Doors. Since the first two doors are not interesting for us, we can already start at the third door:

:  (for (D (nth Doors 3)  ...

As the next step, we have a non-NIL condition (any2). For this we can use our list of remaining doors, D. If there are no more doors, D is NIL and the loop stops.

:  (for (D (nth Doors 3) D  ...

So all we need is to define how D should look like after each step, and the answer is simple: We walked three doors, so it should be the current D list minus three doors, right? This is equivalent to ( cdr (nth D 3)).

So, this is our full for loop including the toggling step:

(for (D (nth Doors 3)  D  (cdr (nth D 3)))
   (set D (not (car D))) ) 

It looks complicated, but what it does is basically: "walk 3 doors, toggle, repeat".

---

Toggling all doors

The rest is easy! Obviously we don't want to toggle only every third door. In fact, we want to repeat this for all numbers from 1 to 100. We will use a for loop again, but this time a more simple one. Let's call the iteration parameter I and we get our final program:

(let Doors (need 100)
   (for I 100
      (for (D (nth Doors I)  D  (cdr (nth D I)))
         (set D (not (car D))) ) )
   (println Doors) ) 

Result:

(T NIL NIL T NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T)

That's it! The final script can be downloaded here.

---

The smart way

We did find a solution, but unfortunately not a very smart one. Why not? Because we could save a lot of walking if we just sat down and think about it once more.

Let's look at the print-out of our program. We see that the following doors are T while all others are NIL: Door 1, 4, 9, 16, 25, ..., 100.

Well? Right: All open doors are square numbers.

So actually all we need to do is open the square numbered doors, and that's it. No need to open-close-open-close the rest of it.

---

Is this magic?

But why are only the square numbered doors open? Let's think about it systematically.

1. A door is open if it has been visited an uneven number of times.

For example, if it is only visited once, it was opened and never closed again. If it is visited two times, it was opened once and closed once. And so on.

1. The number of times a door is visited is equivalent to its number of divisors.

For example, the first door is only visited once (in the first round). The 6th door is visited in the first, second, third and sixth round (6=1*2*3). The 17th door is visited in the first and in the 17th round.

1. Only square numbers have an uneven number of divisors.

   This is a little less obvious but yet true. Any number z can be expressed by x*y. For a prime number, this is 1*z. A prime numbered door is visited exactly two times, therefore it is closed.

   How about non-prime numbers? In this case, there are solutions for x*y where both numbers are not equal to z. For example 21 = 21*1 = 3*7. Door 21 is visited in round 1, 3, 7 and 21.

   However, if z is a square number, then we don't get two different x*y, but only x*x. We need to walk there "only once".

---

Smart version of our script

Obviously the code for this one is more easy. We only need to iterate from 1 to 10 (which is the root of 100), and set all square numbers to T.

(let Doors (need 100)
   (for I (sqrt 100)
      (set (nth Doors (* I I)) T) )
   (println Doors) )

That's it!

---

Make it pretty

Finally, let's put a little more effort in formatting, because our NIL NIL NIL NIL-output is really not fun to read. We should iterate over the list and print out only the open door numbers.

For iteration we will use another handy variation of the for loop - this time we use one that takes two parameters: one counter for the index of the list element and another one for the list item. From the docs:

``(for sym2 . sym) 'lst ['any]) -> any

(...) If sym2 is given, it is treated as a counter variable, first bound to 1 and then incremented for each execution of the body.

Let's pick N as counter variable and D as list iterator:

`
(for (N . D) Doors
`
For each item, we check if D is non-NIL. This can be done with a simple when. The non-NIL list postions should be put into a new list. This is done using the make (...) link functions.

`
(make
(for (N . D) Doors
(when D (link N)) ) )
`
Now this returns the list, but we should also bound it to a variable L to make it printable from our script:

`
(let L
(make
(for (N . D) Doors
(when D (link N)) ) )
(println L) ) )


which prints1 4 9 16 25 36 49 64 81 100`.

---

Finished!

The final script can be downloaded here.

---

Sources

• Cover pic: Photo by Dil on Unsplash
• http://www.rosettacode.org/wiki/100_doors#PicoLisp
• https://software-lab.de/doc/index.html