2015-11-09 LabHanoi

posted Nov 9, 2015, 4:55 AM by Samuel Konstantinovich   [ updated Nov 12, 2015, 5:36 AM ]
Goal Write Hanoi!

In order to write hanoi you need the ability to run multiple statements in sequence. This is not how we generally think of a functional programming language which just gives a result to whatever arguments you put into the function. 

(begin
  s1
  s2
  ...
  sN)

Will execute statements s1 through sN in order 1 to N, and the result of the entire begin statement is the result of sN.
e.g.
(begin 2 3 4) evaluates to 4.

This is very useful if you want to use the display command.
(display x) will print the value of x to the bottom window in racket(or the terminal).

(define f (lambda (x)
    (begin
      (display x)
      (display " is next")
      (sqrt x)
    )))
When you call the program: (display prints in purple, returned values print in blue)
> (f 10)
10 is next
3.1622776601683795

This will first print the value of x and the words is next with a new line, then call the function and show the results.

(define f2 (lambda (x)
    (begin
      (display x)
      (display " is next\n")
      (sqrt x)
      (display "oops")
    )))
When you call this, the function does NOT have any value because (display _) will not return a value, and the begin statement will not return a value. 
> (f2 10)
10 is next
oops          

Back to hanoi:

Your goal is to display the sequence of moves. Hanoi has no "final answer" like most of our other functions. The goal is to print out all of the moves.

We want to have the ability to solve hanoi given a number of disks. 
(hanoi numberOfDisksToMove)

That does not give us enough information to keep track of everything, so we will also keep track of which towers we want to use as our starting point, ending point, and what we call the other tower.

Remember when you make a function you can call itself and switch around the parameters:
(define test (lambda (a b)
  (if (< b a)
      (test b a)
      (- b a))))

(hanoi  start temporary  destination  N)  

Lets say you wrote it and called it as follows:
(hanoi "A" "B" "C" 3) ; this tells the computer to move 3 disks from A to B using C as a temporary tower. 

If you called hanoi again, and specify a different number of disks, and change where you want to move things:
(hanoi temporary start destination (+ N 2))
It would reorder the labels as follows:
(hanoi "B" "A" "C" 5) 
This is how we tell it to move disks onto a different tower! We don't keep track of how many disks there are.

Output format:
(hanoi "Fish" "Beef" "Chicken" 1) would display:
Fish to Chicken

(hanoi "A" "B" "C" 2) would display:
A to B
A to C
B to C

(hanoi "A" "apple" "C" 2) would display:
A to apple
A to C
apple to C









Comments