Today we will talk about a very famous recursive algorithm: The Towers of Hanoi riddle. We will show two ways to solve this, one using functional programming purely in PicoLisp, and one using logical programming with help of Pilog.
The Towers of Hanoi
The "Towers of Hanoi" riddle was introduced to the West by the French mathematician Edouard Lucas in 1883. This is the story (or one of many versions):
Once there was an Indian temple in Kashi Vishwanath containing a large room with three time-worn posts in it, surrounded by 64 golden disks. Acting out the command of an ancient prophecy, Brahmin priests have been moving these disks in accordance with the immutable rules of Brahma since that time. According to the legend, when the last move of the puzzle is completed, the world will end.
These are the "immutable rules of Brahma":
- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No disk may be placed on top of a disk that is smaller than it.
For example, this is how a solution for four disks may look like:
We will discuss a recursive functional and logical algorithm. Let's start with the functional one.
The functional approach
Let's define a function move which has four parameters:
N: the number of plates to be movedA: the starting poleB: the intermediate poleC: the final destination pole
The main idea of recursion is that a large problem can be split up into repetition of smaller problems that are easier to solve. First of all, a recursive function always needs an exit condition: the base case. In our case, the base case is that the number of plates need to be larger than 0, otherwise we cannot move anything:
(de move (N A B C)
(unless (=0 N)
...
Then we model the overall procedure as recursion of small, repetitive tasks:
First we move the tower on pole A to pole B, except for the lowest, largest plate.
We express it in PicoLisp by "moving" N-1 plates from A to B via C.
(de move (N A B C)
(unless (=0 N)
(move (dec N) A C B)
Then we move this last plate to C.
Now we only need to move one plate from A to B. Because we are not really moving anything physically (not even data), let's just add a line for our mental node:
(println 'Move 'disk 'from 'the A 'to 'the B 'pole)
In the last step, we move the whole remaining tower to C via A.
Now we have exactly plate on A and (N-1) plates on B. Now we do the same thing again, only switching B and C:
(de move (N A B C)
(unless (=0 N)
(move (dec N) A C B)
(println 'Move 'disk N 'from 'the A 'to 'the B 'pole)
(move (dec N) C B A) ) )
These steps are repeated for all sub-towers of each tower until the task is finished.
The wrapper function
Now that we defined the algorithm, let's define also the starting point for our function, assuming that we have three poles:
(de hanoi (N)
(move N 'left 'center 'right) )
where center is our target pole. Let's write everything to a file called hanoi-functional.l and run it in debug mode, so that we can interact with it in the REPL:
$ pil hanoi-functional.l +
: (hanoi 1)
Move disk 1 from the left to the center pole
The case (hanoi 1) is trivial: The recursive loops are never entered, and the plate is just moved like this. But for (hanoi 5), we already have 31 movements of plates (2^5 -1)!
The logical approach
From our Pilog course we know that logical languages are very well suited to solve recursive tasks.
The first thing we need again is the base case for N=0, where we can just stop the recursion. We can just stop the recursion here using the cut-operator T. We don't care for the pole variables, so lets just replace them by the anonymous variable @.
(be move (0 @ @ @) T)
Then we define the case for N>1. Here we do care for the pole variables, so let's call them @A, @B and @C analogous to the functional implementation.
(be move (@N @A @B @C)
We will implement exactly the same steps: First we need to call the move predicate with N-1 plates. We can do this by calling an a PicoLisp function that decreases N, and store the return value in the variable @M.
(be move (@N @A @B @C)
(^ @M (dec @N))
(move @M @A @C @B)
Then again, we "move" the last remaining plate from one pole from @A to @B by printing a line. We use the PicoLisp prinl function. Since we don't need to store the value anywhere, we just put it into @.
(^ @ (println 'Move 'disk @N 'from 'the @A 'to 'the @B 'pole))
And lastly, we move the rest of the tower.
(move @M @C @B @A) )
Again, we define the wrapper predicate hanoi/1:
(be hanoi (@N)
(move @N left center right) )
Now we can call it in debug mode in the REPL and play with it (note: you need a pil21-installation for this, older versions of PicoLisp are not compatible).
: (? (hanoi 3))
Move disk 1 from the left to the center pole
Move disk 2 from the left to the right pole
Move disk 1 from the center to the right pole
Move disk 3 from the left to the center pole
Move disk 1 from the right to the left pole
Move disk 2 from the right to the center pole
Move disk 1 from the left to the center pole
-> T
Fun fact: If the monks would have been real and they moved one plate per second, they needed approximately 585 billion years to finish. So it seems there is still some time until the world will end.
You can find the finished program files here.
Sources
https://en.wikipedia.org/wiki/Tower_of_Hanoi
http://rosettacode.org/wiki/Towers_of_Hanoi#PicoLisp
