hanoi.go

package main

import (
	"fmt"
	"time"
)

const height = 5

func main() {
	a := NewStack("Src. ", height)
	b := NewStack("Dst. ", height)
	c := NewStack("Spare", height)

	// Add initial disk
	for i := 0; i < height; i++ {
		a.AddDisk(height - i - 1)
	}

	t0 := time.Now()
	moves := 0
	moveTower(a.Len()-1, a, b, c, func() {
		moves++
		fmt.Printf("--- Move #%d ---\n", moves)
		fmt.Println(a)
		fmt.Println(b)
		fmt.Println(c)
		fmt.Println()
	})

	fmt.Printf("Moving tower of height %d took %d moves in %v\n", height, moves, time.Since(t0))
}

func moveDisk(src, dst *Stack, trace func()) {
	dst.AddDisk(src.RemoveDisk())
	trace()
}

func moveTower(idx int, src, dst, spare *Stack, trace func()) {
	if idx == 0 {
		moveDisk(src, dst, trace)
		return
	}
	moveTower(idx-1, src, spare, dst, trace)
	moveDisk(src, dst, trace)
	moveTower(idx-1, spare, dst, src, trace)
}

type Stack struct {
	name  string
	stack []int
}

func NewStack(name string, size int) *Stack {
	return &Stack{
		name:  name,
		stack: make([]int, 0, size),
	}
}

func (st *Stack) AddDisk(idx int) {
	l := len(st.stack)
	if l == cap(st.stack) {
		panic("Too many disk on stack " + st.name)
	}
	if l != 0 && st.stack[l-1] <= idx {
		panic("Cannot add smaller disk to stack " + st.name)
	}
	st.stack = append(st.stack, idx)
}

func (st *Stack) RemoveDisk() int {
	l := len(st.stack)
	if l == 0 {
		panic("Empty stack " + st.name)
	}
	res := st.stack[l-1]
	st.stack = st.stack[0 : l-1]
	return res
}

func (st *Stack) Len() int {
	return len(st.stack)
}

func (st *Stack) String() string {
	return fmt.Sprintf("%q: %v", st.name, st.stack)
}

Live code - https://play.golang.org/p/rNLlO2VTK_
Output:

--- Move #1 ---
"Src. ": [4 3 2 1]
"Dst. ": [0]
"Spare": []

--- Move #2 ---
"Src. ": [4 3 2]
"Dst. ": [0]
"Spare": [1]

--- Move #3 ---
"Src. ": [4 3 2]
"Dst. ": []
"Spare": [1 0]

--- Move #4 ---
"Src. ": [4 3]
"Dst. ": [2]
"Spare": [1 0]

--- Move #5 ---
"Src. ": [4 3 0]
"Dst. ": [2]
"Spare": [1]

--- Move #6 ---
"Src. ": [4 3 0]
"Dst. ": [2 1]
"Spare": []

--- Move #7 ---
"Src. ": [4 3]
"Dst. ": [2 1 0]
"Spare": []

--- Move #8 ---
"Src. ": [4]
"Dst. ": [2 1 0]
"Spare": [3]

--- Move #9 ---
"Src. ": [4]
"Dst. ": [2 1]
"Spare": [3 0]

--- Move #10 ---
"Src. ": [4 1]
"Dst. ": [2]
"Spare": [3 0]

--- Move #11 ---
"Src. ": [4 1 0]
"Dst. ": [2]
"Spare": [3]

--- Move #12 ---
"Src. ": [4 1 0]
"Dst. ": []
"Spare": [3 2]

--- Move #13 ---
"Src. ": [4 1]
"Dst. ": [0]
"Spare": [3 2]

--- Move #14 ---
"Src. ": [4]
"Dst. ": [0]
"Spare": [3 2 1]

--- Move #15 ---
"Src. ": [4]
"Dst. ": []
"Spare": [3 2 1 0]

--- Move #16 ---
"Src. ": []
"Dst. ": [4]
"Spare": [3 2 1 0]

--- Move #17 ---
"Src. ": [0]
"Dst. ": [4]
"Spare": [3 2 1]

--- Move #18 ---
"Src. ": [0]
"Dst. ": [4 1]
"Spare": [3 2]

--- Move #19 ---
"Src. ": []
"Dst. ": [4 1 0]
"Spare": [3 2]

--- Move #20 ---
"Src. ": [2]
"Dst. ": [4 1 0]
"Spare": [3]

--- Move #21 ---
"Src. ": [2]
"Dst. ": [4 1]
"Spare": [3 0]

--- Move #22 ---
"Src. ": [2 1]
"Dst. ": [4]
"Spare": [3 0]

--- Move #23 ---
"Src. ": [2 1 0]
"Dst. ": [4]
"Spare": [3]

--- Move #24 ---
"Src. ": [2 1 0]
"Dst. ": [4 3]
"Spare": []

--- Move #25 ---
"Src. ": [2 1]
"Dst. ": [4 3 0]
"Spare": []

--- Move #26 ---
"Src. ": [2]
"Dst. ": [4 3 0]
"Spare": [1]

--- Move #27 ---
"Src. ": [2]
"Dst. ": [4 3]
"Spare": [1 0]

--- Move #28 ---
"Src. ": []
"Dst. ": [4 3 2]
"Spare": [1 0]

--- Move #29 ---
"Src. ": [0]
"Dst. ": [4 3 2]
"Spare": [1]

--- Move #30 ---
"Src. ": [0]
"Dst. ": [4 3 2 1]
"Spare": []

--- Move #31 ---
"Src. ": []
"Dst. ": [4 3 2 1 0]
"Spare": []

Moving tower of height 5 took 31 moves in 0s