Lisp: Tower of Hanoi
Lisp: Towers of Hanoi
Contents |
Introduction
This code sample demonstrates the well-known Tower of Hanoi algorithm and shows how it works recursively.
The Tower of Hanoi is a mathematical problem that is often used as an example of how recursive algorithms work.
It is comprised of three vertical rods ("towers") and a number of discs of different sizes or weights which can slide onto any tower. At the start of the puzzle, the discs are stacked in a proper ascending order based on size (or weight) on the first (the source) tower, the largest disc being at the bottom of the stack with the disc directly above it being slightly lighter, and so on till the top where the lightest disc rests.
The objective of the puzzle is to move the entire stack of discs to another rod (the destination tower) such that:
- Only one disc may be moved between towers at a time;
- Each move consists of taking the upper disc from one of the towers and sliding it onto another tower, on top of the other disks that may already be present on that tower.
- No disc may be placed on top of another disc that is lighter than it.
With three discs the puzzle may be solved in seven moves, while with five discs may be solved in thirty one moves, and so on.
Prerequisites
- You need to have Lisp installed on your system. Please see topic on how to install Lisp on Windows.
Running the example code
- Open the GNU Common Lisp command line interpreter and directly type the code in the code sample below.
- The > at the beginning of the line indicates the interpreter prompt; the code has to be typed in after that.
- Type the code and simply press the enter key to see the output.
- In case of any typo you will get an error prompt; just type :q to exit.
Code
(defun main ()
(defvar *Tower-A* '(1 2 3 4 5))
(defvar *Tower-B* ())
(defvar *Tower-C* ())
(defvar *count* 0)
(let ((size (length *Tower-A*)))
(format t "Estimated moves: ~A~%" (- (expt 2 size) 1))
(format t "~%Before: ~%")
(print-towers)
(format t "~%")
(start-hanoi size 'A 'B 'C)
(format t "~%After: ~%")
(print-towers)
(format t "~%Total moves: ~A~%" *count*))
(getch))
(defun start-hanoi (n from to intr)
(if (> n 0)
(progn
(setf *count* (+ *count* 1))
(start-hanoi (- n 1) from intr to)
(transfer-disc from to)
(start-hanoi (- n 1) intr to from))))
(defun transfer-disc (src dest)
(if (equal src dest)
nil
(let ((disc nil))
(if (equal src 'A)
(setf disc (pop *Tower-A*)))
(if (equal src 'B)
(setf disc (pop *Tower-B*)))
(if (equal src 'C)
(setf disc (pop *Tower-C*)))
(if (equal dest 'A)
(push disc *Tower-A*))
(if (equal dest 'B)
(push disc *Tower-B*))
(if (equal dest 'C)
(push disc *Tower-C*))
(format t "Pushed value ~A from ~A to ~A~%" disc src dest)
(print-towers)
(format t "~%")
)))
(defun print-towers ()
(format t "Tower A: ~A~%" (if (= (length *Tower-A*) 0) "()" (reverse *Tower-A*)))
(format t "Tower B: ~A~%" (if (= (length *Tower-B*) 0) "()" (reverse *Tower-B*)))
(format t "Tower C: ~A~%" (if (= (length *Tower-C*) 0) "()" (reverse *Tower-C*))))
(defun getch ()
(format t "~%Press any char + Enter to exit... ")
(read))
Output
Estimated moves: 31
Before: Tower A: (5 4 3 2 1) Tower B: () Tower C: ()
Pushed value 1 from A to B Tower A: (5 4 3 2) Tower B: (1) Tower C: ()
Pushed value 2 from A to C Tower A: (5 4 3) Tower B: (1) Tower C: (2)
Pushed value 1 from B to C Tower A: (5 4 3) Tower B: () Tower C: (2 1)
Pushed value 3 from A to B Tower A: (5 4) Tower B: (3) Tower C: (2 1)
Pushed value 1 from C to A Tower A: (5 4 1) Tower B: (3) Tower C: (2)
Pushed value 2 from C to B Tower A: (5 4 1) Tower B: (3 2) Tower C: ()
Pushed value 1 from A to B Tower A: (5 4) Tower B: (3 2 1) Tower C: ()
Pushed value 4 from A to C Tower A: (5) Tower B: (3 2 1) Tower C: (4)
Pushed value 1 from B to C Tower A: (5) Tower B: (3 2) Tower C: (4 1)
Pushed value 2 from B to A Tower A: (5 2) Tower B: (3) Tower C: (4 1)
Pushed value 1 from C to A Tower A: (5 2 1) Tower B: (3) Tower C: (4)
Pushed value 3 from B to C Tower A: (5 2 1) Tower B: () Tower C: (4 3)
Pushed value 1 from A to B Tower A: (5 2) Tower B: (1) Tower C: (4 3)
Pushed value 2 from A to C Tower A: (5) Tower B: (1) Tower C: (4 3 2)
Pushed value 1 from B to C Tower A: (5) Tower B: () Tower C: (4 3 2 1)
Pushed value 5 from A to B Tower A: () Tower B: (5) Tower C: (4 3 2 1)
Pushed value 1 from C to A Tower A: (1) Tower B: (5) Tower C: (4 3 2)
Pushed value 2 from C to B Tower A: (1) Tower B: (5 2) Tower C: (4 3)
Pushed value 1 from A to B Tower A: () Tower B: (5 2 1) Tower C: (4 3)
Pushed value 3 from C to A Tower A: (3) Tower B: (5 2 1) Tower C: (4)
Pushed value 1 from B to C Tower A: (3) Tower B: (5 2) Tower C: (4 1)
Pushed value 2 from B to A Tower A: (3 2) Tower B: (5) Tower C: (4 1)
Pushed value 1 from C to A Tower A: (3 2 1) Tower B: (5) Tower C: (4)
Pushed value 4 from C to B Tower A: (3 2 1) Tower B: (5 4) Tower C: ()
Pushed value 1 from A to B Tower A: (3 2) Tower B: (5 4 1) Tower C: ()
Pushed value 2 from A to C Tower A: (3) Tower B: (5 4 1) Tower C: (2)
Pushed value 1 from B to C Tower A: (3) Tower B: (5 4) Tower C: (2 1)
Pushed value 3 from A to B Tower A: () Tower B: (5 4 3) Tower C: (2 1)
Pushed value 1 from C to A Tower A: (1) Tower B: (5 4 3) Tower C: (2)
Pushed value 2 from C to B Tower A: (1) Tower B: (5 4 3 2) Tower C: ()
Pushed value 1 from A to B Tower A: () Tower B: (5 4 3 2 1) Tower C: ()
After:
Tower A: ()
Tower B: (5 4 3 2 1)
Tower C: ()
Total moves: 31
Explanation
In the main function we define three "towers" (lines 2 through 4) which are nothing other than a list of symbols; the first list *Tower-A* has five "discs" on it, viz., the numeric values 1, 2, 3, 4, and 5; while *Tower-B* and *Tower-C* are empty. We also create a global variable *count* that is initialized to zero. We declare these variables using the defvar macro and thus they are available at the global level.
Before moving further, we will understand the print-towers and getch functions. print-towers (line 46) merely prints the three lists in reverse, since the first element is the "bottom" of the tower and printing it in its actual order may confuse the reader. So instead of printing the list as
1 2 3 4 5
we print it as
5 4 3 2 1
A simple list reversal to it, nothing more.
We use another function very often within the program and that is format. You can read about the format function in on printing to the console in Lisp.
The getch function (line 51) serves to hold the o/p screen for us. (It uses the read function for this.) This is invoked after the program run ends (line 15).
The two most important and relevant functions are start-hanoi and transfer-disc, which actually implement the algorithm.
We start the main function after declaring the global variables by saving the length of the source tower *Tower-A* in the local variable within main, viz., size (line 6). To this end we use the function length that specifies a list as a parameter and returns the number of elements in it. Prior to running the procedure, however, we print out the contents of all three towers.
Next we kick off the transfer process by calling the start-hanoi function and subsequently re-print out the contents of the towers.
Additional Notes
You may be wondering why we have named tower A as *Tower-A* (with asterisks around the name or informally "earmuffs") and not simply Tower-A. As in all languages, Lisp too has some basic conventions that are faithfully adhered to by all true blue Lisp programmers. One of these conventions is that all global variables should have asterisks around them.
See also
References
Further reading
- Ansi Common Lisp by Paul Graham
- Land of Lisp by Conrad Barski
- Lisp (3rd Edition) by Patrick Henry Winston
- Practical Common Lisp by Peter Seibel
- On Lisp by Paul Graham
- The Little Schemer - 4th Edition by Matthias Felleisen
- Structure and Interpretation of Computer Programs, Second Edition by Harold Abelson
External sources
- McCarthy, John (1979-02-12). "The implementation of Lisp". History of Lisp. Stanford University. Retrieved 2008-10-17.
- Steele, Jr., Guy L.; Richard P. Gabriel (1993). "The evolution of Lisp". The second ACM SIGPLAN conference on History of programming languages. New York, NY: ACM, ISBN 0-89791-570-4. pp. 231–270. ISBN 0-89791-570-4. Retrieved 2008-10-17.
- Veitch, Jim (1998). "A history and description of CLOS". In Salus, Peter H. Handbook of programming languages. Volume IV, Functional and logic programming languages (first ed.). Indianapolis, IN: Macmillan Technical Publishing. pp. 107–158. ISBN 1-57870-011-6
- Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. ISBN 0-262-01153-0.
- My Lisp Experiences and the Development of GNU Emacs, transcript of Richard Stallman's speech, 28 October 2002, at the International Lisp Conference
- Graham, Paul (2004). Hackers & Painters. Big Ideas from the Computer Age. O'Reilly. ISBN 0-596-00662-4.
- Berkeley, Edmund C.; Bobrow, Daniel G., eds. (March 1964). The Programming Language LISP: Its Operation and Applications. Cambridge, Massachusetts: MIT Press.
- Weissman, Clark (1967). LISP 1.5 Primer. Belmont, California: Dickenson Publishing Company Inc..
External links
Wikipedia article on Tower of Hanoi
Author link
Najeeb (talk)
Najeeb Shaikh on Google+
Discussions
Please do leave your comment. Thank you!
and
Nobody voted on this yet