| // run |
| |
| // Copyright 2021 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package main |
| |
| import ( |
| "errors" |
| "fmt" |
| ) |
| |
| // _Equal reports whether two slices are equal: the same length and all |
| // elements equal. All floating point NaNs are considered equal. |
| func _SliceEqual[Elem comparable](s1, s2 []Elem) bool { |
| if len(s1) != len(s2) { |
| return false |
| } |
| for i, v1 := range s1 { |
| v2 := s2[i] |
| if v1 != v2 { |
| isNaN := func(f Elem) bool { return f != f } |
| if !isNaN(v1) || !isNaN(v2) { |
| return false |
| } |
| } |
| } |
| return true |
| } |
| |
| // A Graph is a collection of nodes. A node may have an arbitrary number |
| // of edges. An edge connects two nodes. Both nodes and edges must be |
| // comparable. This is an undirected simple graph. |
| type _Graph[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct { |
| nodes []_Node |
| } |
| |
| // _NodeC is the contraints on a node in a graph, given the _Edge type. |
| type _NodeC[_Edge any] interface { |
| comparable |
| Edges() []_Edge |
| } |
| |
| // Edgec is the constraints on an edge in a graph, given the _Node type. |
| type _EdgeC[_Node any] interface { |
| comparable |
| Nodes() (a, b _Node) |
| } |
| |
| // _New creates a new _Graph from a collection of Nodes. |
| func _New[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]](nodes []_Node) *_Graph[_Node, _Edge] { |
| return &_Graph[_Node, _Edge]{nodes: nodes} |
| } |
| |
| // nodePath holds the path to a node during ShortestPath. |
| // This should ideally be a type defined inside ShortestPath, |
| // but the translator tool doesn't support that. |
| type nodePath[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct { |
| node _Node |
| path []_Edge |
| } |
| |
| // ShortestPath returns the shortest path between two nodes, |
| // as an ordered list of edges. If there are multiple shortest paths, |
| // which one is returned is unpredictable. |
| func (g *_Graph[_Node, _Edge]) ShortestPath(from, to _Node) ([]_Edge, error) { |
| visited := make(map[_Node]bool) |
| visited[from] = true |
| workqueue := []nodePath[_Node, _Edge]{nodePath[_Node, _Edge]{from, nil}} |
| for len(workqueue) > 0 { |
| current := workqueue |
| workqueue = nil |
| for _, np := range current { |
| edges := np.node.Edges() |
| for _, edge := range edges { |
| a, b := edge.Nodes() |
| if a == np.node { |
| a = b |
| } |
| if !visited[a] { |
| ve := append([]_Edge(nil), np.path...) |
| ve = append(ve, edge) |
| if a == to { |
| return ve, nil |
| } |
| workqueue = append(workqueue, nodePath[_Node, _Edge]{a, ve}) |
| visited[a] = true |
| } |
| } |
| } |
| } |
| return nil, errors.New("no path") |
| } |
| |
| type direction int |
| |
| const ( |
| north direction = iota |
| ne |
| east |
| se |
| south |
| sw |
| west |
| nw |
| up |
| down |
| ) |
| |
| func (dir direction) String() string { |
| strs := map[direction]string{ |
| north: "north", |
| ne: "ne", |
| east: "east", |
| se: "se", |
| south: "south", |
| sw: "sw", |
| west: "west", |
| nw: "nw", |
| up: "up", |
| down: "down", |
| } |
| if str, ok := strs[dir]; ok { |
| return str |
| } |
| return fmt.Sprintf("direction %d", dir) |
| } |
| |
| type mazeRoom struct { |
| index int |
| exits [10]int |
| } |
| |
| type mazeEdge struct { |
| from, to int |
| dir direction |
| } |
| |
| // Edges returns the exits from the room. |
| func (m mazeRoom) Edges() []mazeEdge { |
| var r []mazeEdge |
| for i, exit := range m.exits { |
| if exit != 0 { |
| r = append(r, mazeEdge{ |
| from: m.index, |
| to: exit, |
| dir: direction(i), |
| }) |
| } |
| } |
| return r |
| } |
| |
| // Nodes returns the rooms connected by an edge. |
| //go:noinline |
| func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) { |
| m1, ok := zork[e.from] |
| if !ok { |
| panic("bad edge") |
| } |
| m2, ok := zork[e.to] |
| if !ok { |
| panic("bad edge") |
| } |
| return m1, m2 |
| } |
| |
| // The first maze in Zork. Room indexes based on original Fortran data file. |
| // You are in a maze of twisty little passages, all alike. |
| var zork = map[int]mazeRoom{ |
| 11: {exits: [10]int{north: 11, south: 12, east: 14}}, // west to Troll Room |
| 12: {exits: [10]int{south: 11, north: 14, east: 13}}, |
| 13: {exits: [10]int{west: 12, north: 14, up: 16}}, |
| 14: {exits: [10]int{west: 13, north: 11, east: 15}}, |
| 15: {exits: [10]int{south: 14}}, // Dead End |
| 16: {exits: [10]int{east: 17, north: 13, sw: 18}}, // skeleton, etc. |
| 17: {exits: [10]int{west: 16}}, // Dead End |
| 18: {exits: [10]int{down: 16, east: 19, west: 18, up: 22}}, |
| 19: {exits: [10]int{up: 29, west: 18, ne: 15, east: 20, south: 30}}, |
| 20: {exits: [10]int{ne: 19, west: 20, se: 21}}, |
| 21: {exits: [10]int{north: 20}}, // Dead End |
| 22: {exits: [10]int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}}, |
| 23: {exits: [10]int{east: 22, west: 28, up: 24}}, |
| 24: {exits: [10]int{ne: 25, down: 23, nw: 28, sw: 26}}, |
| 25: {exits: [10]int{sw: 24}}, // Grating room (up to Clearing) |
| 26: {exits: [10]int{west: 16, sw: 24, east: 28, up: 22, north: 27}}, |
| 27: {exits: [10]int{south: 26}}, // Dead End |
| 28: {exits: [10]int{east: 22, down: 26, south: 23, west: 24}}, |
| 29: {exits: [10]int{west: 30, nw: 29, ne: 19, south: 19}}, |
| 30: {exits: [10]int{west: 29, south: 19}}, // ne to Cyclops Room |
| } |
| |
| func TestShortestPath() { |
| // The Zork maze is not a proper undirected simple graph, |
| // as there are some one way paths (e.g., 19 -> 15), |
| // but for this test that doesn't matter. |
| |
| // Set the index field in the map. Simpler than doing it in the |
| // composite literal. |
| for k := range zork { |
| r := zork[k] |
| r.index = k |
| zork[k] = r |
| } |
| |
| var nodes []mazeRoom |
| for idx, room := range zork { |
| mridx := room |
| mridx.index = idx |
| nodes = append(nodes, mridx) |
| } |
| g := _New[mazeRoom, mazeEdge](nodes) |
| path, err := g.ShortestPath(zork[11], zork[30]) |
| if err != nil { |
| panic(fmt.Sprintf("%v", err)) |
| } |
| var steps []direction |
| for _, edge := range path { |
| steps = append(steps, edge.dir) |
| } |
| want := []direction{east, west, up, sw, east, south} |
| if !_SliceEqual(steps, want) { |
| panic(fmt.Sprintf("ShortestPath returned %v, want %v", steps, want)) |
| } |
| } |
| |
| func main() { |
| TestShortestPath() |
| } |