Go A* implementation

astar_nodequeue.go

package astar

import "container/heap"

type NodeQueue []Node

func NewNodeQueue() NodeQueue {
	return make(NodeQueue, 0, 1000)
}

func (q NodeQueue) Empty() bool {
	return len(q) == 0
}

func (q NodeQueue) Len() int {
	return len(q)
}

func (q NodeQueue) Less(i, j int) bool {
	return f(q[i].State) < f(q[j].State)
}

func (q NodeQueue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
}

func (q *NodeQueue) Push(n interface{}) {
	*q = append(*q, n.(Node))
}

func (q *NodeQueue) Pop() interface{} {
	n := len(*q)
	last := (*q)[n-1]
	*q = (*q)[0:n-1]
	return last
}

func (q *NodeQueue) Take() Node {
	return heap.Pop(q).(Node)
}

func (q *NodeQueue) Put(n Node) {
	heap.Push(q, n)
}

astar_search.go

package astar

type State interface {
	Hash() int
	Equal(o interface{}) bool

	Cost() int
	CostToGoal() int
	
	Neighbors() []State
}

type Node struct {
	State State
	Parent *Node
}

type Solution []State

func backtrack(final Node) Solution {
	depth := 1
	for n := &final; n.Parent != nil; n = n.Parent {
		depth += 1
	}

	solution := make(Solution, depth)
	n := &final
	for i := depth - 1; i >= 0; i -= 1 {
		solution[i] = n.State
		n = n.Parent
	}

	return solution
}

func f(s State) int {
	return s.Cost() + s.CostToGoal()
}

func Search(initial State) (Solution, bool) {
	frontier := NewNodeQueue()
	examined := NewStateSet()

	frontier.Put(Node{initial})
	for !frontier.Empty() {
		n := frontier.Take()

		if(n.State.CostToGoal() == 0) {
			return backtrack(n), true
		}

		examined.Add(n.State)

		for _, newstate := range n.State.Neighbors() {
			if past, ok := examined.Get(newstate); ok {
				if f(past) >= f(newstate) {
					continue
				}
				examined.Remove(past)
			}
			frontier.Put(Node{newstate, &n})
		}
	}

	return nil, false
}

astar_stateset.go

package astar

type StateSet map[int][]State

func NewStateSet() StateSet {
	return make(StateSet)
}

func(set StateSet) Add(v State) {
	h := v.Hash()
	set[h] = append(set[h], v)
}

func(set StateSet) Remove(v State) {
	h := v.Hash()
	items := set[h]
	for i, item := range items {
		if v.Equal(item) {
			set[h] = append(items[0:i], items[i+1:]...)
			break
		}
	}
}

func(set StateSet) Get(v State) (State, bool) {
	h := v.Hash()
	items := set[h]
	for _, item := range items {
		if v.Equal(item) {
			return item, true
		}
	}
	return nil, false
}

main.go

package main

import (
  "fmt"
  "astar"
)

func main() {
	items := []int{5,2,4,3,1}
	initial := &Move{items, -1, calchash(items), 0, estimatecost(items)}
	solution, _ := astar.Search(initial)

	for _, move := range solution {
		move := move.(*Move)
		fmt.Printf("%v -> %v \n", move.flip, move.Items)
	}
}

pancake.go

package main

type Move struct {
	Items []int
	flip int
	hash int
	flipcount int
	costToGoal int
}

func (s *Move) Hash() int { return s.hash }
func (s *Move) Cost() int { return s.flipcount }
func (s *Move) CostToGoal() int { return s.costToGoal }

func (s *Move) equal(o *Move) bool {
	if s.hash != o.hash {
		return false
	}

	for i, v := range s.Items {
		if o.Items[i] != v {
			return false
		}
	}

	return true
}

func (s *Move) Equal(o interface{}) bool {
	if o, ok := o.(*Move); ok {
		return s.equal(o)
	}
	return false
}

func estimatecost(items []int) int {
	prev := items[0]
	inc := 0
	dec := 1

	for _, v := range items {
		if v < prev {
			inc += 1
		} else if v > prev {
			dec += 1
		}
		prev = v
	}

	if dec < inc {
		return dec
	}
	return inc
}

func calchash(items []int) int {
	hash := 17
	for _, v := range items {
		hash = (hash << 4 + hash) ^ v
	}
	return hash
}

func domove(pre *Move, flip int) *Move {
	var move Move
	items := make([]int, len(pre.Items))
	N := len(pre.Items)

	copy(items[:flip], pre.Items)

	i := N - 1
	for _, v := range pre.Items[flip:] {
		items[i] = v
		i -= 1
	}

	move.Items = items
	move.flip = flip
	move.hash = calchash(items)
	move.flipcount = pre.flipcount + 1
	move.costToGoal = estimatecost(items)

	return &move
}

func (s *Move) Neighbors() []State {
	N := len(s.Items)
	states := make([]State, N-1)
	for i := range states {
		states[i] = domove(s, i)
	}

	return states
}