Classic Algorithms: Solving the 100 Doors Riddle
Tags: functional, picolisp, lisp
Published: 2021-11-24 09:12:37

Today we will talk about the [100 Doors](https://rosettacode.org/wiki/100_doors) task of the Rosetta Code project. This one uses a lot of control flow elements and the ``set``-function we discussed [yesterday](https://picolisp-blog.hashnode.dev/picolisp-explored-the-set-function).

If you are new to PicoLisp, it might be helpful to read the article on [Control Flow functions](https://picolisp-blog.hashnode.dev/60-picolisp-functions-you-should-know-part-4-control-flow)
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](https://picolisp-blog.hashnode.dev/picolisp-explored-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](http://software-lab.de/doc/index.html):

> (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](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/rosetta/100_doors-straightforward.l).


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

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

3. **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 prints ``1 4 9 16 25 36 49 64 81 100``.

----------------------------


Finished! 

The final script can be downloaded [here](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/rosetta/100_doors-smart.l).

----------------------------

### Sources

- Cover pic: Photo by <a href="https://unsplash.com/@thevisualiza?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Dil</a> on <a href="https://unsplash.com/s/photos/doors?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>  
- http://www.rosettacode.org/wiki/100_doors#PicoLisp  
- https://software-lab.de/doc/index.html