Tower of Hanoi

tower_of_hanoi.go

package main

import "fmt"

const (
	// Rods are 1, 2, and 3
	// Given src and dst, the other buffer rod is (1+2+3) - (src + dst) = 6 - (src + dst)
	rod1 = iota + 1
	rod2
	rod3

	sumRod = rod1 + rod2 + rod3
)

func main() {
	towerOfHanoi(4, 1, 3)
}

func towerOfHanoi(n, src, dst int) {
	if n == 1 {
		move(src, dst)
		return
	}

	buf := sumRod - (src + dst)
	towerOfHanoi(n-1, src, buf) // Move the "top disks" to buf
	towerOfHanoi(1, src, dst)   // Move the bottom (largest disk) to dst
	towerOfHanoi(n-1, buf, dst) // Move the other disks from buf to dst
}

func move(start, end int) {
	fmt.Println(start, "->", end)
}