astar

// Finding the shortest path between Arad and Bucharest
// on a Romanian road map fragment. The road map is represented
// as an undirected graph; edge costs are distances between cities.
//
// An example from Stuart Russell and Peter Norvig's
// “Artificial Intelligence. A Modern Approach”, 3rd ed., 2009, p. 68.
package main

import (
	"fmt"
)

type Graph struct {
	edges map[string]map[string]float64
	curr  string
}

func (g Graph) Start() interface{} { return "Arad" }
func (g Graph) Finish() bool       { return "Bucharest" == g.curr }

func (g *Graph) Move(state interface{}) { g.curr = state.(string) }
func (g Graph) Successors(transitions map[interface{}]interface{}) []interface{} {
	successors := []interface{}{}
	for succ := range g.edges[g.curr] {
		successors = append(successors, succ)
	}

	return successors
}

func (g Graph) Cost(given interface{}) float64 {
	return g.edges[g.curr][given.(string)]
}

// Precalculated distances to Bucharest (Ibid., figure 3.22, p. 93.)
func (g Graph) Estimate(given interface{}) float64 {
	estimates := map[string]float64{
		"Arad":           366,
		"Bucharest":      0,
		"Craiova":        160,
		"Drobeta":        242,
		"Eforie":         161,
		"Făgăraș":        176,
		"Giurgiu":        77,
		"Hârșova":        151,
		"Iași":           226,
		"Lugoj":          244,
		"Mehadia":        241,
		"Neamt":          234,
		"Oradea":         380,
		"Pitești":        100,
		"Râmnicu Vâlcea": 193,
		"Sibiu":          253,
		"Timișoara":      329,
		"Urziceni":       80,
		"Vaslui":         199,
		"Zerind":         374,
	}

	return estimates[given.(string)]
}

func main() {
	g := &Graph{
		edges: map[string]map[string]float64{
			"Arad":           {"Zerind": 75, "Timișoara": 118, "Sibiu": 140},
			"Bucharest":      {"Pitești": 101, "Făgăraș": 211, "Urziceni": 85, "Giurgiu": 90},
			"Craiova":        {"Drobeta": 120, "Râmnicu Vâlcea": 146, "Pitești": 138},
			"Drobeta":        {"Mehadia": 75, "Craiova": 120},
			"Eforie":         {"Hârșova": 86},
			"Făgăraș":        {"Sibiu": 99, "Bucharest": 211},
			"Giurgiu":        {"Bucharest": 90},
			"Hârșova":        {"Urziceni": 98, "Eforie": 86},
			"Iași":           {"Neamt": 87, "Vaslui": 92},
			"Lugoj":          {"Timișoara": 111, "Mehadia": 70},
			"Mehadia":        {"Lugoj": 70, "Drobeta": 75},
			"Oradea":         {"Zerind": 71, "Sibiu": 151},
			"Pitești":        {"Râmnicu Vâlcea": 97, "Craiova": 138, "Bucharest": 101},
			"Râmnicu Vâlcea": {"Sibiu": 80, "Pitești": 97, "Craiova": 146},
			"Sibiu":          {"Arad": 140, "Oradea": 151, "Făgăraș": 99, "Râmnicu Vâlcea": 80},
			"Timișoara":      {"Arad": 118, "Lugoj": 111},
			"Urziceni":       {"Bucharest": 85, "Vaslui": 142, "Hârșova": 98},
			"Vaslui":         {"Urziceni": 142, "Iași": 92},
			"Zerind":         {"Arad": 75, "Oradea": 71},
		}}
	if path, _, err := Search(g); err == nil {
		fmt.Printf("%q\n", path)
	}
}

Output:

["Arad" "Sibiu" "Râmnicu Vâlcea" "Pitești" "Bucharest"]

// Water pouring puzzle.
//
// Measure out 6 ounces of water using two glasses of 9 and 4 oz.
// You're allowed to pour water from one glass to another as well as emptying
// and refilling them.
//
// Use A* Search to solve it.
//
//	             =()=
//	            .-||--|
//	           .   ___|
//	           '==’
//	            ||
//	            ||
//	|     |     ||
//	|     |
//	|     |   |    |
//	|     |   |    |
//	|     |   |    |
//	|     |   |    |
//	+-----+   +----+
//	 9 oz.     4 oz.
package main

import (
	"os"
	"text/template"
)

// Glasses’ capacities and the goal.
type Puzzle struct {
	CapFirst, CapSecond int
	Goal                int
}

// Glasses state.
type State struct {
	p      *Puzzle
	Action string
	First  int
	Second int
}

func (s State) Start() interface{} { return State{s.p, "Both Empty", 0, 0} }
func (s State) Finish() bool {
	// One of the glasses contains the goal amount.
	return s.p.Goal == s.First || s.p.Goal == s.Second
}
func (s *State) Move(x interface{})            { *s = x.(State) }
func (s State) Cost(x interface{}) float64     { return 1 }
func (s State) Estimate(x interface{}) float64 { return 1 }
func (s State) Successors(transitions map[interface{}]interface{}) []interface{} {
	succ := []interface{}{}

	First, Second, CapFirst, CapSecond := s.First, s.Second, s.p.CapFirst, s.p.CapSecond

	// Fill first glass.
	succ = append(succ, State{s.p, "Fill First", CapFirst, Second})

	// Fill second glass.
	succ = append(succ, State{s.p, "Fill Second", First, CapSecond})

	// Empty first glass.
	succ = append(succ, State{s.p, "Empty First", 0, Second})

	// Empty second glass.
	succ = append(succ, State{s.p, "Empty Second", First, 0})

	// Pour from the first glass into the second.
	if First+Second > CapSecond {
		succ = append(succ, State{s.p, "First –> Second", First - (CapSecond - Second), CapSecond})
	} else {
		succ = append(succ, State{s.p, "First –> Second", 0, First + Second})
	}

	// Pour from the second glass into the first.
	if First+Second > CapFirst {
		succ = append(succ, State{s.p, "Second –> First", CapFirst, Second - (CapFirst - First)})
	} else {
		succ = append(succ, State{s.p, "Second –> First", First + Second, 0})
	}
	return succ
}

const PouringTmpl = `
{{range .}}  {{printf "%-16s (%v %v)\n" .Action .First .Second}}{{end}}
`

func main() {
	if path, _, err := Search(&State{p: &Puzzle{
		CapFirst:  9,
		CapSecond: 4,
		Goal:      6,
	}}); err == nil {
		template.Must(template.New("Pouring Puzzle").Parse(PouringTmpl)).Execute(os.Stdout, path)
	}
}

Output:

  Both Empty       (0 0)
  Fill First       (9 0)
  First –> Second  (5 4)
  Empty Second     (5 0)
  First –> Second  (1 4)
  Empty Second     (1 0)
  First –> Second  (0 1)
  Fill First       (9 1)
  First –> Second  (6 4)