forked from pietv/astar
-
Notifications
You must be signed in to change notification settings - Fork 0
/
example_pouring_puzzle_test.go
115 lines (101 loc) · 2.98 KB
/
example_pouring_puzzle_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 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 astar
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(current StatePointer) []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 ExampleSearch_pouringPuzzle() {
if state := Search(&State{p: &Puzzle{
CapFirst: 9,
CapSecond: 4,
Goal: 6,
}}); state != nil {
path := []State{}
for ; state != nil; state = state.Previous {
path = append(path, state.Pather.(State))
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
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)
}