-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.go
51 lines (42 loc) · 1.19 KB
/
bfs.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
package day20
import (
"github.com/chigley/advent2020"
"github.com/chigley/advent2020/bfs"
)
type BFSNode struct {
picture Picture
tilesToPlace map[int]Tile
noncer *Noncer
}
func (b *BFSNode) IsGoal() bool {
return b.picture.NextEmptySquare() == nil
}
func (b *BFSNode) Neighbours() ([]bfs.Node, error) {
var neighbours []bfs.Node
squareToFill := *b.picture.NextEmptySquare()
for tileID, baseTile := range b.tilesToPlace {
for _, tile := range baseTile.Permutations() {
if b.picture.Fits(tile, squareToFill) {
neighbours = append(neighbours, b.placeTile(tile, tileID, squareToFill))
}
}
}
return neighbours, nil
}
// We don't need to worry about hitting the same state twice. Stop the BFS
// implementation from worrying about this with this lovely little bodge.
func (b *BFSNode) Key() interface{} {
return b.noncer.Nonce()
}
func (b *BFSNode) placeTile(tile Tile, tileID int, pos advent2020.XY) *BFSNode {
tilesToPlace := make(map[int]Tile)
for tileID, t := range b.tilesToPlace {
tilesToPlace[tileID] = t
}
delete(tilesToPlace, tileID)
return &BFSNode{
picture: b.picture.Place(tile, tileID, pos),
tilesToPlace: tilesToPlace,
noncer: b.noncer,
}
}