What is a Good First Programming Language?

While Googling, I came across the web article What is a Good First Programming Language, by Diwaker Gupta. In short, it depends on the audience. For first-graders, qBasic is probably a good choice, while for college freshmen, C is probably the best choice for a first programming language.

My first language was Apple II Basic, followed by 6502 micro-assembler, in college, late 1970s (actually, I learned Fortran first, on a mainframe PDP computer, with punch cards input and teletype printout; the programs were written ('developed') by hand with pen and paper, and transfered along with the data onto punch cards, which where read by a punch card reader; next, you needed to wait a few hours for your program to be executed and the results printed on a line printer, collected by an assistant, who put it in your print bin). Later on, I bought a Commodore 64, learned Basic, micro-assembler, hexcoding, macro-assembler, and Pascal. I did some C, C++, Java, JavaScript, Python and Lua, and now I'm learning Scheme. So I can claim that Scheme is certainly not my first language (and probably not my last as well).

How to Design Programs - 3.3 Finger Exercises on Composing Functions

Exercise 3.3.1.

The United States uses the English system of (length) measurements. The rest of the world uses the metric system. So, people who travel abroad and companies that trade with foreign partners often need to convert English measurements to metric ones and vice versa.

Here is a table that shows the six major units of length measurements of the English system:

English		metric
1 inch	=	2.54	cm
1 foot	=	12	in.
1 yard	=	3	ft.
1 rod	=	5(1/2)	yd.
1 furlong	=	40	rd.
1 mile	=	8	fl.

Develop the functions inches->cm, feet->inches, yards->feet, rods->yards, furlongs->rods, and miles->furlongs.

Then develop the functions feet->cm, yards->cm, rods->inches, and miles->feet.

Hint: Reuse functions as much as possible. Use variable definitions to specify constants.

Solution

;; inches->cm : number -> number
;; convert inches into cm
(define (inches->cm inches)
  (* inches INCH->CM))

;; feet->inches : number -> number
;; convert feet into inches
(define (feet->inches feet)
  (* feet FOOT->INCH))

;; yards->feet : number -> number
;; convert yards into feet
(define (yards->feet yards)
  (* yards YARD->FOOT))

;; rods->yards : number -> number
;; convert rods into yards
(define (rods->yards rods)
  (* rods ROD->YARD))

;; furlongs->rods : number -> number
;; convert furlongs into rods
(define (furlongs->rods furlongs)
  (* furlongs FURLONG->ROD))

;; miles->furlongs : number -> number
;; convert miles into furlongs
(define (miles->furlongs miles)
  (* miles MILE->FURLONG))

(define MILE->FURLONG 8)
(define FURLONG->ROD 40)
(define ROD->YARD 5.5)
(define YARD->FOOT 3)
(define FOOT->INCH 12)
(define INCH->CM 2.54)

;; feet->cm : number -> number
;; convert feet into cm
(define (feet->cm feet)
  (inches->cm
   (feet->inches feet)))

;; yards->cm : number -> number
;; convert yards into cm
(define (yards->cm yards)
  (feet->cm
   (yards->feet yards)))

;; rods->inches : number -> number
;; convert rods into inches
(define (rods->inches rods)
  (feet->inches
   (yards->feet
    (rods->yards rods))))

;; miles->feet : number -> number
;; convert miles into feet
(define (miles->feet miles)
  (yards->feet
   (rods->yards
    (furlongs->rods
     (miles->furlongs miles)))))

Exercise 3.3.2.

Develop the program volume-cylinder. It consumes the radius of a cylinder's base disk and its height; it computes the volume of the cylinder.

Solution

;; volume-cylinder : number number -> number
;; calculate volume of cylinder
;; example: (volume-cylinder 4 4) -> 201.06176
(define (volume-cylinder radius height)
  (*
   (area-circle radius)
   height))

;; area-circle : number -> number
;; calculate area of circle
;; example: (area-circle 4) -> 50.26544
(define (area-circle radius)
  (* PI (sqr radius)))

(define PI 3.14159)

Exercise 3.3.3.

Develop area-cylinder. The program consumes the radius of the cylinder's base disk and its height. Its result is the surface area of the cylinder.

Solution

;; area-cylinder : number number -> number
;; calculate surface area of cylinder
;; example: (area-cylinder 4 4) -> 201.06176
(define (area-cylinder radius height)
  (+
   (* 2
      (area-circle radius))
   (* height
      (circumference-circle radius))))

;; circumference-circle : number -> number
;; calculate circumference of circle
;; example: (circumference-circle 4) -> 25.13272
(define (circumference-circle radius)
  (* 2
     (* PI radius)))

;; area-circle : number -> number
;; calculate area of circle
;; example: (area-circle 4) -> 50.26544
(define (area-circle radius)
  (* PI (sqr radius)))

(define PI 3.14159)

Exercise 3.3.4.

Develop the function area-pipe. It computes the surface area of a pipe, which is an open cylinder. The program consumes three values: the pipe's inner radius, its length, and the thickness of its wall.

Develop two versions: a program that consists of a single definition and a program that consists of several function definitions. Which one evokes more confidence?

Solution

;; area-pipe number number number -> number
;; calculate surface area of open pipe
;; example: (area-pipe-multi 3 5 0.1) -> 195.4697298
(define (area-pipe-multi inner-radius length thickness-wall)
  (+
   (area-pipe-wall inner-radius length)
   (area-pipe-wall
    (+ inner-radius thickness-wall)
    length)
   (*
    2
    (-
     (area-circle (+ inner-radius thickness-wall))
     (area-circle inner-radius)))))

;; area-pipe-wall : number number -> number
;; calculate area of pipe wall
;; examples:
;; (area-pipe-wall 3 5) -> 94.2477
;; (area-pipe-wall 3.1 5) -> 97.38929
(define (area-pipe-wall radius length)
  (* (circumference-circle radius)
     length))

;; area-circle : number -> number
;; calculate area of circle
;; examples:
;; (area-circle 3) -> 28.27431
;; (area-circle 3.1) -> 30.1906799
(define (area-circle radius)
  (* PI (sqr radius)))

;; circumference-circle : number -> number
;; calculate circumference of circle
;; examples:
;; (circumference 3) -> 18.84954
;; (circumference 3.1) -> 19.477858
(define (circumference-circle radius)
  (* 2 PI radius))

(define PI 3.14159)

;; area-pipe : number number number -> number
;; calculate surface area of open pipe
(define (area-pipe radius length thickness-wall)
  (+
   (* 2 3.14159 radius length)
   (* 2 3.14159
      (+ radius thickness-wall)
      length)
   (* 2
      (-
       (* 3.14159 (sqr
                   (+ radius thickness-wall)))
       (* 3.14159 (sqr radius))))))

Obviously, the solution with the multiple definitions evokes more confidence, because you can develop a higher order function before getting into the details of the lower order functions.

Exercise 3.3.5.

Develop the program height, which computes the height that a rocket reaches in a given amount of time. If the rocket accelerates at a constant rate g, it reaches a speed of g * t in t time units and a height of 1/2 * v * t where v is the speed at t.

Solution

;; height : number -> number
;; calculate height of rocket at certain time
;; example: (height 3) -> 45
(define (height time)
  (* 0.5 (speed time) time))

;; speed : number -> number
;; calculate speed of rocket at certain time
;; example: (speed 3) -> 30
(define (speed time)
  (* G time))

(define G 10)

Exercise 3.3.6.

Recall the program Fahrenheit->Celsius from exercise 2.2.1. The program consumes a temperature measured in Fahrenheit and produces the Celsius equivalent.

Develop the program Celsius->Fahrenheit, which consumes a temperature measured in Celsius and produces the Fahrenheit equivalent.

Now consider the function

;; I : number -> number
;; to convert a Fahrenheit temperature to Celsius and back
(define (I f)
  (Celsius->Fahrenheit (Fahrenheit->Celsius f)))

Evaluate (I 32) by hand and using DrScheme's stepper. What does this suggest about the composition of the two functions?

Solution

;; Fahrenheit->Celsius number -> number
;; examples:
;; (Fahrenheit->Celsius 32) -> 0
;; (Fahrenheit->Celsius 212) -> 100
(define (Fahrenheit->Celsius F)
  (* (- F 32) (/ 5 9)))

;; Celsius->Fahrenheit number -> number
;; examples:
;; (Celsius->Fahrenheit 0) -> 32
;; (Celsius->Fahrenheit 100) -> 212
(define (Celsius->Fahrenheit C)
  (+ (* C (/ 9 5)) 32))

;; I : number -> number
;; to convert a Fahrenheit temperature to Celsius and back
(define (I f)
  (Celsius->Fahrenheit (Fahrenheit->Celsius f)))

(I 32) is Celsius->Fahrenheit applied to (Fahrenheit-Celsius 32)

(Fahrenheit-Celsius 32)
evaluates to
(/ (* (- 32 32) 5) 9)
(/ (* 0 5) 9)
(/ 0 9)
0

(Celsius-Fahrenheit 0)
evaluates to
(+ (/ (* 0 9) 5) 32)
(+ (/ 0 5) 32)
(+ 0 32)
32

DrScheme's Stepper:

(I 32)

(Celsius->Fahrenheit
  (Fahrenheit->Celsius 32))

(Celsius->Fahrenheit
  (Fahrenheit->Celsius 32))

(Celsius->Fahrenheit
  (* (- 32 32) (/ 5 9)))

(Celsius->Fahrenheit
  (* (- 32 32) (/ 5 9)))

(Celsius->Fahrenheit
  (* 0 (/ 5 9)))

(Celsius->Fahrenheit
  (* (/ 5 9)))

(Celsius->Fahrenheit (* 0 5/9))

(Celsius->Fahrenheit (* 0 5/9))

(Celsius->Fahrenheit 0)

(Celsius->Fahrenheit 0)

(+ (* 0 (/ 9 5)) 32)

(+ (* 0 (/ 9 5)) 32)

(+ (* 0 9/5) 32)

(+ (* 0 9/5) 32)

(+ 0 32)

(+ 0 32)

32

The constants 32 and 5/9 could be incorporated in both as variables.

How to Design Programs - 3.2 Variable Definitions

;; How to design a program
(define (profit ticket-price)
  (- (revenue ticket-price)
     (cost ticket-price)))

(define (revenue ticket-price)
  (* (attendees ticket-price) ticket-price))

(define (cost ticket-price)
  (+ 180
     (* 0.04 (attendees ticket-price))))

(define (attendees ticket-price)
  (+ 120
     (* (/ 15 .10) (- 5.00 ticket-price))))

Exercise 3.2.1.

Provide variable definitions for all constants that appear in the above profit program and replace the constants with their names.

Solution

;;; How to design a program
(define (profit ticket-price)
  (- (revenue ticket-price)
     (cost ticket-price)))

(define (revenue ticket-price)
  (* (attendees ticket-price) ticket-price))

(define (cost ticket-price)
  (+ FIXED-COST
     (* COST-PER-ATTENDEE (attendees ticket-price))))

(define (attendees ticket-price)
  (+ ATTENDEES-AT-BASE-PRICE
     (*
      (/
       MORE-ATTENDEES-PER-PRICE-DECREASE
       PRICE-DECREASE)
      (- BASE-PRICE ticket-price))))

(define FIXED-COST 180)
(define COST-PER-ATTENDEE 0.04)
(define ATTENDEES-AT-BASE-PRICE 120)
(define BASE-PRICE 5.00)
(define MORE-ATTENDEES-PER-PRICE-DECREASE 15)
(define PRICE-DECREASE .10)

How to Design Programs - 3.1 Composing Functions

Consider the following problem:

Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of $5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime ($.10) increases attendance by 15. Unfortunately, the increased attendance also comes at an increased cost. Every performance costs the owner $180. Each attendee costs another four cents ($0.04). The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit.

Exercise 3.1.1.

The next step is to make up examples for each of the functions. Determine how many attendees can afford a show at a ticket price of $3.00, $4.00, and $5.00. Use the examples to formulate a general rule that shows how to compute the number of attendees from the ticket price. Make up more examples if needed.

Solution

• 120 people can afford 5 dollar per ticket
• decreasing the ticket price by 0.1 dollar increases attendance by 15
  or:
  decreasing the ticket price by 1 dollar increases attendance by 150
  
  or:
  for every dollar less, 150 more people will attend
• if the ticket price is decreased by 5 dollar, 870 people will attend
  so:
  number of people = 870 - (price in dollars) * (150 per dollar)

price	attendees
5	120
4	270
3	420
2	570
1	720
0	870

Exercise 3.1.2.

Use the results of exercise 3.1.1 to determine how much it costs to run a show at $3.00, $4.00, and $5.00. Also determine how much revenue each show produces at those prices. Finally, figure out how much profit the monopolistic movie owner can make with each show. Which is the best price (of these three) for maximizing the profit?

Solution

• the costs are 180 dollars, plus 0.04 dollars timers the number of attendees
• the revenue is the number of attendees times the ticket price
• profit is revenue minus cost

price	attendees	cost	revenue	profit
5	120	184.8	600	415.2
4	270	190.8	1080	889.2
3	420	196.8	1260	1063.2
2	570	202.8	1140	937.2
1	720	208.8	720	511.2
0	870	214.8	0	-214.8

$3.00 is the best price of the three.

;; How to design a program
(define (profit ticket-price)
  (- (revenue ticket-price)
    (cost ticket-price)))

(define (revenue ticket-price)
  (* (attendees ticket-price) ticket-price))

(define (cost ticket-price)
  (+ 180
    (* .04 (attendees ticket-price))))

(define (attendees ticket-price)
  (+ 120
    (* (/ 15 .10) (- 5.00 ticket-price))))

;; How not to design a program
(define (profit price)
   (- (* (+ 120
            (* (/ 15 .10)
               (- 5.00 price)))
         price)
      (+ 180
        (* .04
          (+ 120
             (* (/ 15 .10)
                (- 5.00 price)))))))

Exercise 3.1.3.

Determine the profit that the movie owner makes at $3.00, $4.00, and $5.00 using both program definitions. Make sure that the results are the same as those predicted in exercise 3.1.2.

Solution

;; How to design a program
> (profit 5)
415.2
> (profit 4)
889.2
> (profit 3)
1063.2

;; How not to design a program
> (profit 5)
415.2
> (profit 4)
889.2
> (profit 3)
1063.2

The results are the same as before.

Exercise 3.1.4.

After studying the cost structure of a show, the owner discovered several ways of lowering the cost. As a result of his improvements, he no longer has a fixed cost. He now simply pays $1.50 per attendee.

Modify both programs to reflect this change. When the programs are modified, test them again with ticket prices of $3.00, $4.00, and $5.00 and compare the results.

Solution

;; How to design a program
(define (profit ticket-price)
  (- (revenue ticket-price)
    (cost ticket-price)))

(define (revenue ticket-price)
  (* (attendees ticket-price) ticket-price))

(define (cost ticket-price)
  (* 1.50 (attendees ticket-price)))

(define (attendees ticket-price)
  (+ 120
    (* (/ 15 .10) (- 5.00 ticket-price))))

> (profit 5)
420
> (profit 4)
675
> (profit 3)
630

;; how not to design a program
(define (profit price)
   (- (* (+ 120
            (* (/ 15 .10)
               (- 5.00 price)))
         price)
      (* 1.50
        (+ 120
          (* (/ 15 .10)
             (- 5.00 price))))))

> (profit 5)
420
> (profit 4)
675
> (profit 3)
630

The results for both methods are the same. Compared to the results in exercise 3.1.3, a ticket price of $4.00 is more favorable, instead of the earlier $3.00.

Towers of Hanoi - 3

Let's look at the steps for (move 3 1 2 3):

step disk from  to  spare
  1    1    1    2    3
  2    2    1    3    2
  3    1    2    3    1
  4    3    1    2    3
  5    1    3    1    2
  6    2    3    2    1
  7    1    1    2    3

Now reorder the lines on the disk row, in reverse order:

step disk from  to  spare
  4    3    1    2    3
  2    2    1    3    2
  6    2    3    2    1
  1    1    1    2    3
  3    1    2    3    1
  5    1    3    1    2
  7    1    1    2    3

This means disk 3 is moved once, disk 2 is moved twice, and disk 1 is moved four times. What causes this?

See what happens for each disk:

1. move pile on top of disk 3 on to spare
2. move disk to destination
3. move pile back on top of disk (at destination)

So, for each move of a disk, the pile on top of it is moved twice as often:

• disk 3 is moved once
• pile on top of disk 3 (disks 1 and 2) are moved twice

• disk 2 is moved twice
• for each move of disk 2, disk 1 on top of disk 2 is moved twice

• disk 1 is moved four times

More general for a pile of n disks, for p between 1 and n:

1. move pile on top of disk p (consisting of disks 1 tru p-1) to spare
2. move disk p to destination
3. move pile at spare to destination

• disk 1 tru p-1 is moved twice as often as disk p

Therefore, the total number of moves is:

Sum(p=1 tru n) { 2^n-p }

or

2ⁿ - 1

Another observation is that:

• disk 1 is always moved in odd steps (1, 3, 5, etc.)
• disk 2 is always moved in steps 2, 6, 10, etc.
• disk 3 is always moved in steps 4, 12, 20, etc.
• disk p is always moved in step

  2^p-1 mod 2^p

Look at the following moves, depending on the number of disks, n:

n = 1
disk 1: from → to

n = 2
disk 2: from → to
disk 1: from → spare → to

n = 3
disk 3: from → to
disk 2: from → spare → to
disk 1: from → to → spare → from → to

n = k
disk k-0: from → to
disk k-1: from → spare → to
disk k-2: from → to → spare → from → to
disk k-3: from → spare → to → from → spare → to → from → spare → to
...

To find the disk of a n disk Towers of Hanoi puzzle, depending on the current value of step, use this program:

;; find-disk-for-step: number number -> number
;; find the disk that is moved in a step
;; in a n high Tower of Hanoi
;; if step is out of range, then return a -1
(define (find-disk-for-step step n)
  (if (> step (- (expt 2 n) 1))
      -1
      (find-disk-for-step-loop step n 1)))
;; find-disk-loop number number number -> number
;; check which disk is moved in a certain step
;; of the Towers of Hanoi puzzle
;; seed this recursion with disk = 1
(define (find-disk-for-step-loop step n disk)
  (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk-for-step-loop step n (+ disk 1))))

The program consists of two definitions.

There is a the definition called find-disk-for-step, which consumes step (which stands for the step, or move number, in the puzzle) and n (which stands for the total number of disks in the puzzle), and produces either the disk that is moved in that step, or a value of -1 if the value of step is out of range (too high).

Then there is the definition that is called from the first definition, as a helper definition. This second definition is called find-disk-for-step-loop, which consumes step and n, and a disk parameter, which should be seeded with the value 1. The definition tests if a disk is moved for the given values of step and n. It checks if the following condition is true:

step mod 2^disk == 2^disk-1

if it is true, disk has been found and is returned as a result, otherwise a higher value of disk is tested, by recursing the find-disk-for-step-loop with disk + 1 as an argument for the disk parameter, and the same values as before for the other parameters.

Now we now which disk is moved in a particular step, we can use what we have observed before to formulate a definition that finds the move of a disk in a certain step, expressed in the values of from, to and spare, as used as arguments in (move n from to spare). Of course, we already know what disk moves.

What we observed was, that the bottom disk in the starting position, moves as follows:

disk n: from → to

The disk on top of the bottom disk, moves as follows:

disk n-1: from → spare → to

The disk on top of that disk, moves as follows:

disk n-2: from → to → spare → from → to

In general:

disk n - (even number):
from → to → spare → from → to → spare → ...

disk n - (odd number):
from → spare → to → from → spare → to → ...

Restated as follows:

if (modulo n 2) is equal to (modulo disk 2) then:
from → to → spare → from → to → spare → ...
else:
from → spare → to → from → spare → to → ...

If we want to find how many times a disk has moved in the puzzle, based on the value of step, we can use this formula:

        step - 2^disk-1
moved = —————————————
            2^disk

If moved is equal to zero, this particular disk hasn't moved. If it's equal to one, it has moved once, etc. We can use this to determine a move, once we have established which disk moves, which is based on the value of step. Now about the details:

if (modulo n 2) is equal to (modulo disk 2) then:

in case

(= (modulo moved 3) 0)
  (print-move disk from to)

(= (modulo moved 3) 1)
  (print-move disk to spare)

(= (modulo moved 3) 2)
  (print-move disk spare from)

else:

in case

(= (modulo moved 3) 0)
  (print-move disk from spare)

(= (modulo moved 3) 1)
  (print-move disk spare to)

(= (modulo moved 3) 2)
  (print-move disk to from)

So, now we can run the value of step from 1 to 2ⁿ-1, inclusive, determine which disk is moved, what the move is, and print that to the screen.

This all is enough to write the definitions:

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (move-loop n from to spare 1))

;; calculate each move through iteration
;; using step as a counter
;; seed step with 1
(define (move-loop n from to spare step)
  (define disk (find-disk step n 1))
  (if (< step (expt 2 n))
      (begin
        (print-step-move step n disk from to spare)
        (move-loop n from to spare (+ step 1)))
      "done"))

;; print a move of a disk
(define (print-step-move step n disk from to spare)
  (define moved (/ (- step (expt 2 (- disk 1))) (expt 2 disk)))
  (cond
    [(= (modulo n 2) (modulo disk 2))
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from to)]
        [(= (modulo moved 3) 1)
         (print-move disk to spare)]
        [else
         (print-move disk spare from)])]
    [else
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from spare)]
        [(= (modulo moved 3) 1)
         (print-move disk spare to)]
        [else
         (print-move disk to from)])]))

;; print a move
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))

;; find which disk is moved in the current step
(define (find-disk step n disk)
   (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk step n (+ disk 1))))

The iterative process is not necessarily faster than the recursive process, because, in contrast to the recursive process in the Fibonacci numbers, there are no steps that could be calculated from earlier steps, or something.

Remember, that in the Fibonacci number problem,

Fib(n) = Fib(n-1) - Fib(n-2)

uses Fib(n-2) when trying to calculate Fib(n-1) (which is equal to Fib(n-2) + Fib(n-3)). This lead to inefficiency when using the formulas straight in a code definition.

In the Towers of Hanoi, on the other hand, there is no such inefficiency. A recursive or iterative process is just another way to express a solution to the problem.

Towers of Hanoi - 2

In the video tutorial 1b of the MIT Lisp video tutorials, the solution of the Towers of Hanoi puzzle is expressed as this Lisp definition:

(define (move n from to spare)
  (cond
    ((= n 0) "done" )
    (else)
      (move (-1+ n) from spare to)
      (print-move n from to)
      (move (-1+ n) spare to from))))

I have translated that into DrScheme, using Textual (MzScheme, includes R5RS), which can be found at the end of this posting (see Program).

Now look at the program trace of (move 3 1 2 3), using substitution (as explained in the video tutorial):

(move 3 1 2 3)              ;;  n  T  F  S
  (move (-1+ 3) 1 3 2)      ;;  3  1  2  3
    (move (-1+ 2) 1 2 3)    ;;  2  1  3  2
      (move (-1+ 1) 1 3 2)  ;;  1  1  2  3
        "done"              ;;  0  1  3  2
      (print-move 1 1 2)    ;;  1  1  2  3
      (move (-1+ 1) 3 2 1)  ;;  1  1  2  3
        "done"              ;;  0  3  2  1
    (print-move 2 1 3)      ;;  2  1  3  2
    (move (-1+ 2) 2 3 1)    ;;  2  1  3  2
      (move (-1+ 1) 2 1 3)  ;;  1  2  3  1
        "done"              ;;  0  2  1  3
      (print-move 1 2 3)    ;;  1  2  3  1
      (move (-1+ 1) 1 3 2)  ;;  1  2  3  1
  (print-move 3 1 2)        ;;  3  1  2  3
  (move (-1+ 3) 3 2 1)      ;;  3  1  2  3
    (move (-1+ 2) 3 1 2)    ;;  2  3  2  1
      (move (-1+ 1) 3 2 1)  ;;  1  3  1  2
        "done"              ;;  0  3  2  1
      (print-move 1 3 1)    ;;  1  3  1  2
      (move (-1+ 1) 2 1 3)  ;;  1  3  1  2
        "done"              ;;  0  2  1  3
    (print-move 2 3 2)      ;;  2  3  2  1
    (move (-1+ 2) 1 2 3)    ;;  2  3  2  1
     (move (-1+ 1) 1 3 2)   ;;  1  1  2  3
        "done"              ;;  0  1  3  2
     (print-move 1 1 2)     ;;  1  1  2  3
     (move (-1+ 1) 3 2 1)   ;;  1  1  2  3
        "done"              ;;  0  3  2  1

I have used indentation to show how deep the trace is in the iteration (in essence, how low the value of n is), and color coding to indicate which of the three steps is being executed inside the combination of the alternative expression (see MIT/GNU Scheme - Conditionals) as used in the definition above. Furthermore, I have added in the comments fields the substituted values for n, from, to, and spare (n F T S).

As you can see, this is a recursive process, and certainly not an iteration. Now, can we rewrite this program, so it does an iterative process to solve the puzzle, instead of the current recursive process?

Program

;; Towers of Hanoi, solution 1

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (cond
    [(= n 0) "done" ]
    [else (begin
            (move (-1+ n) from spare to)
            (print-move n from to)
            (move (-1+ n) spare to from))]))
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))
(define (-1+ x)
  (- x 1))

Towers of Hanoi

The Towers of Hanoi puzzle is not that easy to solve. If you want to play a digital version of that puzzle, go to Towers of Hanoi DHTML game.

Now let's see how to solve a four disk puzzle.



This is the start position.



And this is the end position.

A step in between the start and end position could be something like this:



Directly followed by this:



This is the only move the largest red disk will make.

How about the next disk, the yellow one?

Well, it has three positions, the start position, on tower 2 (while the red disk is still on tower 1), and on top of the red disk on tower 3):



The red disk hasn't moved yet, and the yellow disk have moved to tower 2.



The red disk has moved, and the yellow disk has moved on top of the red disk on tower 3.

Now, let's recap what we've done so far:

• We have moved the disks on top of the red disk, to make the red disk free, and move it to it's final tower.
• In order to make the red disk free to move from tower 1 to tower 3, we have to move the other disks to tower 2, with the yellow disk at the bottom of the pile of disks. In order to be able to move the yellow disk to tower 2, we need to move the disks on top of it to tower 3. Then we move the yellow disk to tower 2, and the other disks on top of the yellow disk on tower 2.
• Once the red disk is on tower 3, we need to move the yellow disk on tower 2 to tower 3. In order to do that, we need to move the disks on top of the yellow disk to tower 1. After that, we can move the yellow disk on top of the red disk on tower 3.

I see a pattern there, in order to move a disk at the bottom of a pile of disks, we need to move the disks on top of it to the spare tower. If you want to move a disk from tower O to tower D, the remaining tower S is the spare tower (where O, D, and S can either be one of 1, 2, 3). That smells like a recursive process.

So this is the process:

• move disks on top of red disk to tower 2:
  • move disks on top of yellow disk to tower 3:
    • move cyan disk on top of green disk to tower 2
    • move green disk to tower 3
    • move cyan disk to tower 3, on top of green disk
  • move yellow disk to tower 2
  • move disks on tower 3 to tower 2, on top of yellow disk:
    • move cyan disk on top of green disk to tower 1, on top of red disk
    • move green disk to tower 2, on top of yellow disk
    • move cyan disk to tower 2, on top of green disk
• move red disk to tower 3
• move disks on tower 2 to tower 3, on top of red disk:
  • move disks on top of yellow disk to tower 1:
    • move cyan disk on top of green disk to tower 3
    • move green disk to tower 1
    • move cyan disk to tower 1, on top of green disk
  • move yellow disk top tower 3, on top of red disk
  • move disks on tower 1 to tower 3, on top of yellow disk:
    • move cyan disk on top of green disk to tower 2
    • move green disk to tower 3, on top of yellow disk
    • move cyan disk to tower 3, on top of green disk

Here is an animation of this procedure:



If we study this more closely, we can see that in order to move a pile of disks from the origin to the destination, you need to:

1. park the disks on top of the bottom disk to the spare
2. move the freed bottom disk to it's destination
3. move the parked pile back on the bottom disk

That should be enough to understand the puzzle, but not quite enough to develop our program to solve the puzzle.