codekingpro/portable-devtools

1// run2 3// Copyright 2021 The Go Authors. All rights reserved.4// Use of this source code is governed by a BSD-style5// license that can be found in the LICENSE file.6 7package main8 9import (10	"errors"11	"fmt"12)13 14// _SliceEqual reports whether two slices are equal: the same length and all15// elements equal. All floating point NaNs are considered equal.16func _SliceEqual[Elem comparable](s1, s2 []Elem) bool {17	if len(s1) != len(s2) {18		return false19	}20	for i, v1 := range s1 {21		v2 := s2[i]22		if v1 != v2 {23			isNaN := func(f Elem) bool { return f != f }24			if !isNaN(v1) || !isNaN(v2) {25				return false26			}27		}28	}29	return true30}31 32// A Graph is a collection of nodes. A node may have an arbitrary number33// of edges. An edge connects two nodes. Both nodes and edges must be34// comparable. This is an undirected simple graph.35type _Graph[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {36	nodes []_Node37}38 39// _NodeC is the constraints on a node in a graph, given the _Edge type.40type _NodeC[_Edge any] interface {41	comparable42	Edges() []_Edge43}44 45// _EdgeC is the constraints on an edge in a graph, given the _Node type.46type _EdgeC[_Node any] interface {47	comparable48	Nodes() (a, b _Node)49}50 51// _New creates a new _Graph from a collection of Nodes.52func _New[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]](nodes []_Node) *_Graph[_Node, _Edge] {53	return &_Graph[_Node, _Edge]{nodes: nodes}54}55 56// nodePath holds the path to a node during ShortestPath.57// This should ideally be a type defined inside ShortestPath,58// but the translator tool doesn't support that.59type nodePath[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {60	node _Node61	path []_Edge62}63 64// ShortestPath returns the shortest path between two nodes,65// as an ordered list of edges. If there are multiple shortest paths,66// which one is returned is unpredictable.67func (g *_Graph[_Node, _Edge]) ShortestPath(from, to _Node) ([]_Edge, error) {68	visited := make(map[_Node]bool)69	visited[from] = true70	workqueue := []nodePath[_Node, _Edge]{nodePath[_Node, _Edge]{from, nil}}71	for len(workqueue) > 0 {72		current := workqueue73		workqueue = nil74		for _, np := range current {75			edges := np.node.Edges()76			for _, edge := range edges {77				a, b := edge.Nodes()78				if a == np.node {79					a = b80				}81				if !visited[a] {82					ve := append([]_Edge(nil), np.path...)83					ve = append(ve, edge)84					if a == to {85						return ve, nil86					}87					workqueue = append(workqueue, nodePath[_Node, _Edge]{a, ve})88					visited[a] = true89				}90			}91		}92	}93	return nil, errors.New("no path")94}95 96type direction int97 98const (99	north direction = iota100	ne101	east102	se103	south104	sw105	west106	nw107	up108	down109)110 111func (dir direction) String() string {112	strs := map[direction]string{113		north: "north",114		ne:    "ne",115		east:  "east",116		se:    "se",117		south: "south",118		sw:    "sw",119		west:  "west",120		nw:    "nw",121		up:    "up",122		down:  "down",123	}124	if str, ok := strs[dir]; ok {125		return str126	}127	return fmt.Sprintf("direction %d", dir)128}129 130type mazeRoom struct {131	index int132	exits [10]int133}134 135type mazeEdge struct {136	from, to int137	dir      direction138}139 140// Edges returns the exits from the room.141func (m mazeRoom) Edges() []mazeEdge {142	var r []mazeEdge143	for i, exit := range m.exits {144		if exit != 0 {145			r = append(r, mazeEdge{146				from: m.index,147				to:   exit,148				dir:  direction(i),149			})150		}151	}152	return r153}154 155// Nodes returns the rooms connected by an edge.156//157//go:noinline158func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) {159	m1, ok := zork[e.from]160	if !ok {161		panic("bad edge")162	}163	m2, ok := zork[e.to]164	if !ok {165		panic("bad edge")166	}167	return m1, m2168}169 170// The first maze in Zork. Room indexes based on original Fortran data file.171// You are in a maze of twisty little passages, all alike.172var zork = map[int]mazeRoom{173	11: {exits: [10]int{north: 11, south: 12, east: 14}}, // west to Troll Room174	12: {exits: [10]int{south: 11, north: 14, east: 13}},175	13: {exits: [10]int{west: 12, north: 14, up: 16}},176	14: {exits: [10]int{west: 13, north: 11, east: 15}},177	15: {exits: [10]int{south: 14}},                   // Dead End178	16: {exits: [10]int{east: 17, north: 13, sw: 18}}, // skeleton, etc.179	17: {exits: [10]int{west: 16}},                    // Dead End180	18: {exits: [10]int{down: 16, east: 19, west: 18, up: 22}},181	19: {exits: [10]int{up: 29, west: 18, ne: 15, east: 20, south: 30}},182	20: {exits: [10]int{ne: 19, west: 20, se: 21}},183	21: {exits: [10]int{north: 20}}, // Dead End184	22: {exits: [10]int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}},185	23: {exits: [10]int{east: 22, west: 28, up: 24}},186	24: {exits: [10]int{ne: 25, down: 23, nw: 28, sw: 26}},187	25: {exits: [10]int{sw: 24}}, // Grating room (up to Clearing)188	26: {exits: [10]int{west: 16, sw: 24, east: 28, up: 22, north: 27}},189	27: {exits: [10]int{south: 26}}, // Dead End190	28: {exits: [10]int{east: 22, down: 26, south: 23, west: 24}},191	29: {exits: [10]int{west: 30, nw: 29, ne: 19, south: 19}},192	30: {exits: [10]int{west: 29, south: 19}}, // ne to Cyclops Room193}194 195func TestShortestPath() {196	// The Zork maze is not a proper undirected simple graph,197	// as there are some one way paths (e.g., 19 -> 15),198	// but for this test that doesn't matter.199 200	// Set the index field in the map. Simpler than doing it in the201	// composite literal.202	for k := range zork {203		r := zork[k]204		r.index = k205		zork[k] = r206	}207 208	var nodes []mazeRoom209	for idx, room := range zork {210		mridx := room211		mridx.index = idx212		nodes = append(nodes, mridx)213	}214	g := _New[mazeRoom, mazeEdge](nodes)215	path, err := g.ShortestPath(zork[11], zork[30])216	if err != nil {217		panic(fmt.Sprintf("%v", err))218	}219	var steps []direction220	for _, edge := range path {221		steps = append(steps, edge.dir)222	}223	want := []direction{east, west, up, sw, east, south}224	if !_SliceEqual(steps, want) {225		panic(fmt.Sprintf("ShortestPath returned %v, want %v", steps, want))226	}227}228 229func main() {230	TestShortestPath()231}232