blob: cecf349a9ad7da758487ef03eccfc28f22d9751d [file] [log] [blame]
 // run -gcflags=-G=3 // 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 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: int{north: 11, south: 12, east: 14}}, // west to Troll Room 12: {exits: int{south: 11, north: 14, east: 13}}, 13: {exits: int{west: 12, north: 14, up: 16}}, 14: {exits: int{west: 13, north: 11, east: 15}}, 15: {exits: int{south: 14}}, // Dead End 16: {exits: int{east: 17, north: 13, sw: 18}}, // skeleton, etc. 17: {exits: int{west: 16}}, // Dead End 18: {exits: int{down: 16, east: 19, west: 18, up: 22}}, 19: {exits: int{up: 29, west: 18, ne: 15, east: 20, south: 30}}, 20: {exits: int{ne: 19, west: 20, se: 21}}, 21: {exits: int{north: 20}}, // Dead End 22: {exits: int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}}, 23: {exits: int{east: 22, west: 28, up: 24}}, 24: {exits: int{ne: 25, down: 23, nw: 28, sw: 26}}, 25: {exits: int{sw: 24}}, // Grating room (up to Clearing) 26: {exits: int{west: 16, sw: 24, east: 28, up: 22, north: 27}}, 27: {exits: int{south: 26}}, // Dead End 28: {exits: int{east: 22, down: 26, south: 23, west: 24}}, 29: {exits: int{west: 30, nw: 29, ne: 19, south: 19}}, 30: {exits: 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, zork) 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() }