#| 

The Towers Of Hanoi for Common LISP

For fun, look here for the brilliant crazy nerd-person (my hero)  writing Towers of Hanoi: 

http://www.kernelthread.com/projects/hanoi/

His projects inlcude Towers of Hanoi for car-audio MP3-player and an x86 bootable Hanoi operating system!

You can search Google on "Towers of Hanoi" for lots of colorful explanations of the problem.

Everything on a line after a ; is a comment.


|#

#| Assignment:

Algorithm:

  To move the tower from A to C
  Move a 1-smaller tower from A to B
  Move the bottom disk to C
  Move the 1-disk-smaller tower on top of it.

All of the LISP code to solve the Towers Of Hanoi problem for N disks is given below, but with three
missing pieces of information in six places.  Replace the missing information represented by ?x, ?y, ?z, ?p,
?q and ?r with the arguments <b>from, to</b> and <b> spare</b>. That is, for example, you might replace the
string "?x" with the string "from", and so on. Hint: In fact you DO replace "?x" with the string "from" (without the quotes!).

Hint: Start developing by testing (Hanoi 1) and (Hanoi 2).

|#

#| <-- Remove the comment designator here and at the bottom of the Hanoi function as well
(defun hanoi-1(n from to spare)  ; The hanoi-1 function n, from, to, spare are all arguments. 
  (cond
    ((> n 0) ; RERCURSIVE case is when your job is to move a tower of more than zero disks.
     (hanoi-1 (- n 1) ?x ?y ?z)  ; Move a 1-disk-smaller tower where you are NOT going.
     (format t "Move disk from ~s ==> ~s~&" from to) ; Move the bottom disk where you ARE going.
     (hanoi-1 (- n 1) ?p ?q ?r) ;; Move the smaller tower back on top of it.
     )
    )   ; The BASE case is implied (n = 0) here, where you do nothing.
  )

;;; Assume you are starting on tower A and going to tower C
(defun hanoi (n)                  ; The hanoi fuction
  (format t "~%Moving ~s disk~p from tower A to tower C:~%" n n) ; ~p forms plural s
  (hanoi-1 n 'A 'C 'B)
  )
|#  ; <--This is the end of the multi-line comment. Remove this whole line too.


#|
Your output from the two functions above should like the following:

CL-USER(66): (hanoi 1)

Moving 1 disk from tower A to tower C:
Move disk from A ==> C
NIL

CL-USER(67): (hanoi 2)

Moving 2 disks from tower A to tower C:
Move disk from A ==> B
Move disk from A ==> C
Move disk from B ==> C
NIL

CL-USER(68): (hanoi 3)

Moving 3 disks from tower A to tower C:
Move disk from A ==> C
Move disk from A ==> B
Move disk from C ==> B
Move disk from A ==> C
Move disk from B ==> A
Move disk from B ==> C
Move disk from A ==> C
NIL

CL-USER(69): (hanoi 4)

Moving 4 disks from tower A to tower C:
Move disk from A ==> B
Move disk from A ==> C
Move disk from B ==> C
Move disk from A ==> B
Move disk from C ==> A
Move disk from C ==> B
Move disk from A ==> B
Move disk from A ==> C
Move disk from B ==> C
Move disk from B ==> A
Move disk from C ==> A
Move disk from B ==> C
Move disk from A ==> B
Move disk from A ==> C
Move disk from B ==> C
NIL
CL-USER(70): 

|#