A breadth-first Tower of Hanoi solver in Go

output.md

Example Output

Lower numbers in the towers represent larger disks, so higher integers must always be to the right of smaller ones.

World:
0 [1]
1 [2]
2 [3 4 5 6]
---------------
0 [1 2]
1 []
2 [3 4 5 6]
---------------
0 [1 2]
1 [6]
2 [3 4 5]
---------------
0 [1 2 5]
1 [6]
2 [3 4]
---------------
0 [1 2 5 6]
1 []
2 [3 4]
---------------
0 [1 2 5 6]
1 [4]
2 [3]
---------------
0 [1 2 5]
1 [4]
2 [3 6]
---------------
0 [1 2]
1 [4 5]
2 [3 6]
---------------
0 [1 2]
1 [4 5 6]
2 [3]
---------------
0 [1 2 3]
1 [4 5 6]
2 []
---------------
0 [1 2 3 6]
1 [4 5]
2 []
---------------
0 [1 2 3 6]
1 [4]
2 [5]
---------------
0 [1 2 3]
1 [4]
2 [5 6]
---------------
0 [1 2 3 4]
1 []
2 [5 6]
---------------
0 [1 2 3 4]
1 [6]
2 [5]
---------------
0 [1 2 3 4 5]
1 [6]
2 []
---------------
0 [1 2 3 4 5 6]
1 []
2 []

simple_search.go

package simple_search

import (
	"fmt"
	"math/rand"
	"reflect"
	"time"
)

type Tower []int

type World struct {
	NumBlocks, NumTowers int
	Towers               []Tower
	Previous             *World
}

type Move struct {
	From, To int
}

var (
	randGen = rand.New(rand.NewSource(time.Now().UnixNano()))
)

func NewWorld(numBlocks, numTowers int) *World {
	world := new(World)
	world.NumBlocks = numBlocks
	world.NumTowers = numTowers
	world.Towers = make([]Tower, numTowers)
	remainingBlocks := numBlocks
	total := 0
	for i := 0; i < numTowers-1; i++ {
		height := randGen.Intn(remainingBlocks + 1)
		remainingBlocks -= height
		world.Towers[i] = make(Tower, height)
		for val := 0; val < height; val++ {
			total++
			world.Towers[i][val] = total
		}
	}
	world.Towers[numTowers-1] = make(Tower, remainingBlocks)
	for val := 0; val < remainingBlocks; val++ {
		total++
		world.Towers[numTowers-1][val] = total
	}
	return world
}

func (w *World) Clone() *World {
	newWorld := new(World)
	newWorld.NumBlocks = w.NumBlocks
	newWorld.NumTowers = w.NumTowers
	newWorld.Towers = make([]Tower, w.NumTowers)
	for i, tower := range w.Towers {
		newWorld.Towers[i] = make(Tower, len(tower))
		for j, value := range tower {
			newWorld.Towers[i][j] = value
		}
	}
	return newWorld
}

func (m *Move) ApplyTo(w *World) *World {
	newWorld := w.Clone()
	newWorld.Towers[m.To] = append(newWorld.Towers[m.To], newWorld.Towers[m.From][len(newWorld.Towers[m.From])-1])
	newWorld.Towers[m.From] = newWorld.Towers[m.From][:len(newWorld.Towers[m.From])-1]
	newWorld.Previous = w
	return newWorld
}

func (w *World) ActiveTowers() int {
	open := 0
	for _, tower := range w.Towers {
		if len(tower) > 0 {
			open += 1
		}
	}
	return open
}

func (w *World) TopOf(index int) int {
	if length := len(w.Towers[index]); length > 0 {
		return w.Towers[index][length-1]
	} else {
		return -1
	}
}

func (w *World) Moves() []Move {
	moves := make([]Move, 0)
	for from, fromTower := range w.Towers {
		if len(fromTower) > 0 {
			for to := range w.Towers {
				if to != from && w.TopOf(to) < w.TopOf(from) {
					moves = append(moves, Move{from, to})
				}
			}
		}
	}
	return moves
}

func (w *World) Solve() *World {
	seen := make([]*World, 0)
	queue := make([]*World, 1)
	queue[0] = w

	for {
		world := queue[0]
		queue = queue[1:]
		seen = append(seen, world)
		if world.ActiveTowers() == 1 {
			return world
		}
		for _, move := range world.Moves() {
			applied := move.ApplyTo(world)

			skip := false
			for _, existing := range seen {
				if reflect.DeepEqual(existing.Towers, applied.Towers) {
					skip = true
					break
				}
			}

			if !skip {
				queue = append(queue, applied)
			}
		}
	}
}

func (w *World) Print() {
	for index, tower := range w.Towers {
		fmt.Printf("%d %d\n", index, tower)
	}
}

func (w *World) FullPrint() {
	if w.Previous == nil {
		fmt.Println("World:")
	} else {
		w.Previous.FullPrint()
		fmt.Println("---------------")
	}
	w.Print()
}

simple_search_test.go

package simple_search

import (
	"reflect"
	"testing"
)

// Lower numbers in the towers are larger disks.
func makeWorld() *World {
	world := NewWorld(4, 5)
	world.Towers[0] = Tower{}
	world.Towers[1] = Tower{1, 2}
	world.Towers[2] = Tower{}
	world.Towers[3] = Tower{4}
	world.Towers[4] = Tower{3}
	return world
}

func TestNewWorld(t *testing.T) {
	for i := 0; i < 100; i++ {
		world := NewWorld(10, 5)
		sum := 0
		for _, tower := range world.Towers {
			sum += len(tower)
		}
		if sum != 10 {
			t.Errorf("Not all blocks used (got %i, want %i)", sum, 10)
		}
	}
}

func TestClone(t *testing.T) {
	world := makeWorld()
	newWorld := world.Clone()
	if world == newWorld {
		t.Errorf("Worlds should not be same object")
	}
	if !reflect.DeepEqual(world, newWorld) {
		t.Errorf("Worlds should be the same structure")
	}
}

func TestActiveTowers(t *testing.T) {
	world := makeWorld()
	if open := world.ActiveTowers(); open != 3 {
		t.Errorf("ActiveTowers returned %i, expected %i", open, 3)
	}
}

func TestTopOf(t *testing.T) {
	world := makeWorld()
	if world.TopOf(0) != -1 {
		t.Errorf("TopOf(0) expected %i, got %i", -1, world.TopOf(0))
	}
	if world.TopOf(1) != 2 {
		t.Errorf("TopOf(1) expected %i, got %i", 2, world.TopOf(1))
	}
	if world.TopOf(2) != -1 {
		t.Errorf("TopOf(2) expected %i, got %i", -1, world.TopOf(2))
	}
	if world.TopOf(3) != 4 {
		t.Errorf("TopOf(3) expected %i, got %i", 4, world.TopOf(3))
	}
	if world.TopOf(4) != 3 {
		t.Errorf("TopOf(4) expected %i, got %i", 3, world.TopOf(4))
	}
}

func TestMoves(t *testing.T) {
	world := makeWorld()
	moves := world.Moves()

	table := []Move{
		Move{1, 0}, Move{1, 2},
		Move{3, 0}, Move{3, 1}, Move{3, 2}, Move{3, 4},
		Move{4, 0}, Move{4, 1}, Move{4, 2},
	}

	if !reflect.DeepEqual(table, moves) {
		t.Errorf("Moves returned %q, expected %q", moves, table)
	}
}

func TestMoveApplyTo(t *testing.T) {
	world := makeWorld()
	move := Move{1, 2}
	resultingWorld := move.ApplyTo(world)
	if resultingWorld == world {
		t.Errorf("Worlds should not be same object")
	}

	world.Towers[1] = Tower{1}
	world.Towers[2] = Tower{2}

	if !reflect.DeepEqual(world.Towers, resultingWorld.Towers) {
		t.Errorf("Expected the resulting world to be correct, but got %q", resultingWorld.Towers)
	}

	if resultingWorld.Previous != world {
		t.Errorf("Expected the resulting world's Previous to point to the original world", resultingWorld)
	}
}

func TestSolve(t *testing.T) {
	world := makeWorld()
	solved := world.Solve()
	if !reflect.DeepEqual(solved.Towers[1], Tower{1, 2, 3, 4}) {
		t.Errorf("Expected the solved world to be solved, but got %q", solved)
	}
}

Lazy review from golint:

simple_search.go:1:1: don't use an underscore in package name
simple_search.go:85:9: if block ends with a return statement, so drop this else and outdent its block (move short variable declaration to its own line if necessary)
simple_search.go:76:4: should replace open += 1 with open++
simple_search.go:91:2: can probably use "var moves []Move" instead
simple_search.go:105:2: can probably use "var seen []*World" instead

This looks pretty good. From what I've seen of idiomatic go, people would probably prefer to define a .String() method (to implement the Stringer interface) than to define .Print().

They also often use the object literal syntax instead of new. e.g. world := &World{Numblocks: ...}`

In terms of the code, it passes the tests, so must be good enough :).