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.

Fibonacci numbers

Fibonacci numbers can be defined as follows:



We can simply write a Scheme program that does just that:

;; Fib : number -> number
;; calculate Fibonacci number
;; examples:
;; (Fib 0) -> 0
;; (Fib 1) -> 1
;; (Fib 5) -> 5
;; (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else
     (+
      (Fib (- n 1))
      (Fib (- n 2)))]))

Testing:

> (Fib 0)
0
> (Fib 1)
1
> (Fib 5)
5
> (Fib 10)
55

Here is the trace of (Fib 4), leaving out the uninteresting bits:

(Fib 4)
(+ (Fib 3) (Fib (- 4 2)))
(+ (+ (Fib 2) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ 1 (Fib 0)) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ 1 (Fib 1)) (Fib (- 4 2)))
(+ 2 (Fib 2))
(+ 2 (+ (Fib 1) (Fib (- 2 2)))
(+ 2 (+ 1 (Fib 0)))
3

Compare this with (Fib 3):

(Fib 3)
(+ (Fib 2) (Fib (- 3 2)))
(+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2)))
(+ (+ 1 (Fib 0)) (Fib (- 3 2)))
(+ 1 (Fib 1))
2

According to the lecture video (see below), in this process, space of Fib(n) is proportional to n, and time is proportional to Fib(n).

Notice that some terms are calculated several times, which indicates code inefficiency. This is clearly not an iterative process, but rather some kind of recursive process.

Can the program be rewritten so, that it does an iterative process, instead of the current recursive process?

Well, how about starting the calculation from 2 and going upwards to n? If n is 0 or 1, the answers are 0 and 1, respectively. Then we use the following definition of Fibs, in which we pass intermediate Fibonacci values as parameters of Fibs, in a recursive fashion:

(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

In this definition, b is the previous Fibonacci number, a is the Fibonacci number before that, c indicates the order of the current intermediate Fibonacci number, and n indicates the desired order for the Fibonacci number. We seed Fibs with a = 0, b = 1, c = 2, n = n.

Let's try (Fibs 0 1 2 5) in a trace:

(Fibs 0 1 2 5)
(Fibs 1 1 3 5)
(Fibs 1 2 4 5)
(Fibs 2 3 5 5)
(Fibs 3 5 6 5)
5

We can see that the time of Fibs is proportional to n, and the space is proportional to 1. This, therefore, is an iteration process.

Here is the complete program for calculating a Fibonacci number:

;; Fib : number -> number
;; calculate a Fibonacci number
;; e.g. (Fib 4) -> 3
;; e.g. (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else (Fibs 0 1 2 n)]))
(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

And (Fib 10) produces 55:

> (Fib 10)
55

If you try out both programs with a really large number (say 100000), you will notice a distinct difference in speed. The second is much faster than the first.

Credits

I have to confess that I didn't come up with the solutions myself.

The first solution was taken from a Lisp tutorial video (lesson 1b of the MIT Lisp video tutorials), and converted into Scheme.

The second solution was taken from Lecture notes about Fibonacci numbers by David Eppstein, professor of Computer Science. The code was written in Python, so I needed to convert from an imperative language notation into the declarative language notation of Scheme, which I had never done before. So there was indeed a, though modest, learning experience in all of this. On that same notes page are some alternative methods you could try.

When in need for a solution, Google is your friend.

Linear iteration and linear recursion

Although all loops in Scheme are done using recursion, the resulting code execution, can be quite different. Observe this peano arithmetic (only increment and decrement by one) addition, taken from the lesson 1b (Procedures and Processes; Substitution Model) of the MIT Lisp video tutorial page and modified for DrScheme (also see this tutorial on Google Video):

;; plus1 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus1 3 5) should produce 8
(define (plus1 x y)
  (if (= x 0)
      y
      (plus1 (dec x) (inc y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus1 3 5)

If we trace this (plus1 3 5), leaving out the uninteresting parts, we get this:

(plus1 3 5) |
(plus1 2 6) |
(plus1 1 7) | time = O(x)
(plus1 0 8) |
8           |
------------
space = O(1)

linear iteration : time = O(x), space = O(1)

The time it takes to run the code is proportional to the value of x, in other words, ordinal to x (O(x)). The amount of memory storage it takes to execute this code, the space, is constant, or ordinal to 1 (O(1)). This is the hallmark of a linear iteration.

If we modify the code of plus1, so it delays the addition of y until the end of the execution, we get something like this:

;; plus2 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus2 3 5) should produce 8
(define (plus2 x y)
  (if (= x 0)
      y
      (inc (plus2 (dec x) y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus2 3 5)

If we trace (plus2 3 5) as before, we get this:

(plus2 3 5)                   |
(inc (plus2 2 5))             |
(inc (inc (plus2 1 5)))       |
(inc (inc (inc (plus2 0 5)))) | time = O(x)
(inc (inc (inc 5)))           |
(inc (inc 6))                 |
(inc 7)                       |
8                             |
------------------------------
space = O(x)

linear recursion : time = O(x), space = O(x)

Again, the number of steps is proportional to the value of x (that there are twice as many steps doesn't matter at this point). However, the amount of space isn't constant, but proportional to value of x. This is the hallmark of a linear recursion.

Although both methods plus1 and plus2 use the same recursive looping technique, the resulting code execution (process) is quite different.

There are two other interesting problems discussed in this video tutorial lesson, Fibonacci numbers and the Towers of Hanoi. These can be expressed both as a recursive and an iterative process. I will discuss both problems in separate posts, once I've digested the concepts of this video tutorial.

Software Development Process

I haven't considered that there are different methods to develop software, especially if it is done in collaboration.

I have five interesting Wikipedia entries I should read and digest (entry summaries taken from Wikipedia):

Software development process

A software development process is a structure imposed on the development of a software product. Synonyms include software lifecycle and software process. There are several models for such processes, each describing approaches to a variety of tasks or activities that take place during the process.

Waterfall model

The waterfall model is a sequential software development model (a process for the creation of software) in which development is seen as flowing steadily downwards (like a waterfall) through the phases of requirements analysis, design, implementation, testing (validation), integration, and maintenance. The origin of the term "waterfall" is often cited to be an article published in 1970 by W. W. Royce; ironically, Royce himself advocated an iterative approach to software development and did not even use the term "waterfall". Royce originally described what is now known as the waterfall model as an example of a method that he argued "is risky and invites failure".

Iterative and incremental development

Iterative and Incremental development is a software development process developed in response to the weaknesses of the more traditional waterfall model. The two most well known iterative development frameworks are the Rational Unified Process and the Dynamic Systems Development Method. Iterative and incremental development is also an essential part of Extreme Programming and all other agile software development frameworks.

Agile software development

Agile software development is a conceptual framework for undertaking software engineering projects.

There are a number of agile software development methods, such as those espoused by The Agile Alliance. Most agile methods attempt to minimize risk by developing software in short timeboxes, called iterations, which typically last one to four weeks. Each iteration is like a miniature software project of its own, and includes all of the tasks necessary to release the mini-increment of new functionality: planning, requirements analysis, design, coding, testing, and documentation. While an iteration may not add enough functionality to warrant releasing the product, an agile software project intends to be capable of releasing new software at the end of every iteration. In many cases, software is released at the end of each iteration. This is particuarly true when the software is web-based and can be released easily. Regardless, at the end of each iteration, the team reevaluates project priorities.

Agile methods emphasize realtime communication, preferably face-to-face, over written documents. Most agile teams are located in a bullpen and include all the people necessary to finish software. At a minimum, this includes programmers and their "customers" (customers are the people who define the product; they may be product managers, business analysts, or actual customers). The bullpen may also include testers, interaction designers, technical writers, and managers.

Agile methods also emphasize working software as the primary measure of progress. Combined with the preference for face-to-face communication, agile methods produce very little written documentation relative to other methods. This has resulted in criticism of agile methods as being undisciplined.

Formal methods

In computer science and software engineering, formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the expectation that, as in other engineering disciplines, performing appropriate mathematical analyses can contribute to the reliability and robustness of a design. However, the high cost of using formal methods means that they are usually only used in the development of high-integrity systems, where safety or security is important.

Of course, there are many more articles to read on this subject. There is a list on Wikipedia of all entries about the Software Development Process.

After listening to the Cincon Smalltalk podcast series (of which most episodes have Industry Misinterpretations in their title), episode Industry Misinterpretations Episode 23: Retrospective Coherence (MP3 file), I came to the conclusion that this topic, the software development process, is a really interesting.

Some fun and interesting paraphrases from that podcast episode:

Most people hear to listen, not to understand, like they have read-only memory

in order for a complex system to have resilience, it has to have some degree of inefficiency

process and code optimization should always be the last step in development, otherwise the system loses it's flexibility and ultimately breaks down

the purpose of most meetings is to keep people from taking responsibility

And then there are many more profound notions in this episode. Be sure to listen, but be warned that the audio quality is a bit poor.

How to read technical texts

Perhaps I should reveal a recipe how to read technical texts more efficiently. It is really simple:

1. read the text through and try to keep track of the global ideas; stop if you lose track of the material, and restart from the point you started, using method 2
2. read the text more carefully, and do all the exercise and examples; stop if you lose track and get stuck in solving the exercise or doing the examples, and restart from the point you started, using method 3
3. read the text for a third time, do all the exercise and examples, and add some of yourself; stop if you get stuck

Every time you get stuck, start over again from the point you started the last time, up to the point you got stuk. During the rereading of this part of the text, use a higher order method (1, 2, 3). So you could be reading little pieces of text, each time in another reading mode (1, 2, 3). Once you get past the point you got stuck in the text in the latest iteration, switch back to a lower order reading method.

If you get stuck in step 3, you need to find alternative information sources to supplement your reading. Try to find those sources through Google, by using the items you didn't understand as search terms. It simply means you lack information you need to understand the text. Once you have grasped the new concepts, reread the difficult parts of the technical text, using method 3.

You should have read the complete text at least three times, using methods 1, 2, and 3. Here is a diagram of the reading methods

1) global reading without doing exercises and examples
->
2) detailed reading doing all exercises and examples
->
3) reading doing all exercises and examples with some examples of your own

Structure and Interpretation of Computer Programs

Through the Code Newbie forum (I'm forum member Rasheed), I got a reference to Structure and Interpretation of Computer Programs by MIT Press. They use Scheme, just like that other great on-line book, How to Design Programs (also see Why this blog?, and the tag How to Design Programs on this blog).

There is also a series of hour long lectures on Google video. I have here a list of videos I have found (lectures 9a, 9b, and 10a were missing when I did a search on Google Video):

• Lecture 1a: Overview and Introduction to Lisp
• Lecture 1b: Procedures and Processes; Substitution Model
• Lecture 2a: Higher-order Procedures
• Lecture 2b: Compound Data
• Lecture 3a: Henderson Escher Example
• Lecture 3b: Symbolic Differentiation; Quotation
• Lecture 4a: Pattern Matching and Rule-based Substitution
• Lecture 4b: Generic Operators
• Lecture 5a: Assignment, State, and Side-effects
• Lecture 5b: Computational Objects
• Lecture 6a: Streams, Part 1
• Lecture 6b: Streams, Part 2
• Lecture-7a: Metacircular Evaluator, Part 1
• Lecture 7b: Metacircular Evaluator, Part 2
• Lecture 8a: Logic Programming, Part 1
• Lecture 8b: Logic Programming, Part 2
• Lecture 10b: Storage Allocation and Garbage Collection

I also found the original videos, which you can download from this page. That is perhaps the best way to retrieve the videos. You can either download or torrent a DIVX .avi or a MPEG video file from each of the 20 lectures (ten times a and b lessons). This was a good reason for me to start using the Azureus bit-torrent client, because I want these lessons burnt on DVD.