1.3: The Towers of Hanoi

The Towers of Hanoi is an old puzzle and quite the popular example for recursion in many languages. The legend is that the world will end once you move 64 disks.

This is type of the callback that performs the Hanoi move. An interface{} could be used here but since no state is being maintained a function type is a better choice.

type (
 MoveFunc func(n int, start, end string)
)

The Hanoi function. Moves n pegs from start to end using 3 pegs.

func hanoi(n int, pegStart, pegEnd, pegExtra string, mover MoveFunc) {
 if n == 1 {
  mover(1, pegStart, pegEnd)
 } else {
  hanoi(n-1, pegStart, pegExtra, pegEnd, mover)
  mover(n, pegStart, pegEnd)
  hanoi(n-1, pegExtra, pegEnd, pegStart, mover)
 }
}

A basic moving function. Simply prints out the actual move (e.g. Move disk 2 from "A" to "C").

func move(n int, start, end string) {
 fmt.Printf("Move disk %d from %q to %q.\n", n, start, end)
}

Kicks of the process for 4 disks.

func main() {
 hanoi(4, "A", "B", "C", move)
}

This function constructs a MoveFunc function that wraps around an actual move function. The idea here is to check if certain invariants hold before each move.

func checkmove(n int, peg string, move MoveFunc) MoveFunc {
 position := make([]string, n+1)
 for i := 1; i < len(position); i++ {
  position[i] = peg
 }
 return func(n int, start, end string) {
  if n < 1 || n > len(position)-1 {
   panic(fmt.Sprintf("Bad disk number %d, should be 1..%d", n, len(position)-1))
  }
  if position[n] != start {
   panic(fmt.Sprintf("Tried to move disk %d from %q, but it is on peg %q", n, start, position[n]))
  }
  for i := 1; i < n-1; i++ {
   if position[i] == start {
    panic(fmt.Sprintf("Can't move disk %n from %q because %n is on top of it", n, start, i))
   } else if position[i] == end {
    panic(fmt.Sprintf("Can't move disk %n to %q becasue %n is already there", n, end, i))
   }
  }
  move(n, start, end)
  position[n] = end
 }
}

Again, kicking of the process for  4 disks, now using the wrapper to construct the invariant function around the mover.

func main() {
 hanoi(4, "A", "B", "C", checkmove(4, "A", move))
}

Get the source at GitHub