ICS 171: Homework #2

We'll refer to following problem as the Tower of Hanoi problem and use it in the next few homeworks.

a. There are three pegs, labeled A, B, and C.
b. There are 3 disks on peg A. The top disk has a diameter of 1, the middle disk has a diameter of 2, and the bottom disk has a diameter of 3.
c. There are no disks on peg C.
d. You must move one disk at time and you can not place a larger disk on top of a smaller disk.

The problem is to get all of the disks on peg C.

A. (20 points) Find a representation for the states of this problem

B. (25 points) Describe in English all of the operators that might be applied to a state.

C. (5 points) Find any solution to the problem. A solution is a sequence of operator applications.

D. (30 points). Write a lisp function (defun can-move? (from to) ... ) that is given a list of pegs that are the source of the move (from) and a list that is the destination (to). It returns true if the top (i.e., first) peg on "from" may be move to "to", and NIL otherwise. Here are some test cases:

(can-move? '() '(1 2)) should return NIL because there are no disks on "from"
(can-move? '(1) '(2 3)) should return true
(can-move? '(1 3) '(2)) should return true
(can-move? '(3) '(1 2)) should return NIL
(can-move? '(3) '()) should return true

E. (20 Points) Write a function print-stats(x,y,z) that prints the mean with 4 characters and median value of x, y, and z and returns median.

(print-stats 3 1 7) Prints
Median: 3
Mean: 3.67 

Hand in a single file concatenating a dribble file testing your functions, a listing of the functions, and your answers to parts A, B and C.