Dijkstra’s shortest path.

// Dijkstra's shortest paths over walking times in whole minutes. Every path is two-way.
export const MAX_PLACES = 64;
export const MAX_PATHS = 256;
export const MAX_MINUTES = 1440; // one day

export type Path = { a: string; b: string; minutes: number };
export type Campus = { places: string[]; paths: Path[] };
// A settled place: its final walking time, and the settled place it was reached from.
export type Settled = { place: string; minutes: number; via: string | null };

export type RouteErrorCode = 'too-big' | 'bad-place' | 'unknown-place' | 'bad-minutes';

export class RouteError extends Error {
	readonly code: RouteErrorCode;
	constructor(code: RouteErrorCode, message: string) {
		super(message);
		this.name = 'RouteError';
		this.code = code;
	}
}

type Entry = { minutes: number; place: string };

// Fewer minutes first; equal minutes by place id, so ties settle the same way in every language.
const ahead = (x: Entry, y: Entry) =>
	x.minutes < y.minutes || (x.minutes === y.minutes && x.place < y.place);

// A binary min-heap: the frontier of places reached but not yet settled.
class Frontier {
	#items: Entry[] = [];
	get size() {
		return this.#items.length;
	}
	push(entry: Entry) {
		const items = this.#items;
		items.push(entry);
		for (let i = items.length - 1; i > 0;) {
			const parent = (i - 1) >> 1;
			if (!ahead(items[i], items[parent])) break;
			[items[i], items[parent]] = [items[parent], items[i]];
			i = parent;
		}
	}
	pop(): Entry {
		const items = this.#items;
		const top = items[0];
		const last = items.pop()!;
		if (items.length > 0) {
			items[0] = last;
			for (let i = 0; ;) {
				let best = i;
				for (const child of [2 * i + 1, 2 * i + 2])
					if (child < items.length && ahead(items[child], items[best])) best = child;
				if (best === i) break;
				[items[i], items[best]] = [items[best], items[i]];
				i = best;
			}
		}
		return top;
	}
}

export function paths(campus: Campus): Map<string, { to: string; minutes: number }[]> {
	if (campus.places.length > MAX_PLACES || campus.paths.length > MAX_PATHS)
		throw new RouteError('too-big', `up to ${MAX_PLACES} places and ${MAX_PATHS} paths`);
	const next = new Map<string, { to: string; minutes: number }[]>();
	for (const place of campus.places) {
		if (!/^[a-z][a-z0-9-]{0,23}$/.test(place) || next.has(place))
			throw new RouteError('bad-place', `place ids are unique lowercase slugs: ${place}`);
		next.set(place, []);
	}
	for (const { a, b, minutes } of campus.paths) {
		if (!next.has(a) || !next.has(b))
			throw new RouteError('unknown-place', `a path joins places that don't exist: ${a}, ${b}`);
		if (!Number.isInteger(minutes) || minutes < 0 || minutes > MAX_MINUTES)
			throw new RouteError('bad-minutes', `minutes are whole numbers from 0 to ${MAX_MINUTES}`);
		next.get(a)!.push({ to: b, minutes });
		next.get(b)!.push({ to: a, minutes });
	}
	return next;
}

// Settle places in order of walking time from start. Stops as soon as `target` is settled.
export function settle(campus: Campus, start: string, target?: string): Settled[] {
	const next = paths(campus);
	for (const place of target === undefined ? [start] : [start, target])
		if (!next.has(place)) throw new RouteError('unknown-place', `no such place: ${place}`);
	const best = new Map<string, number>([[start, 0]]);
	const via = new Map<string, string | null>([[start, null]]);
	const done = new Set<string>();
	const frontier = new Frontier();
	frontier.push({ minutes: 0, place: start });
	const settled: Settled[] = [];
	while (frontier.size > 0) {
		const { minutes, place } = frontier.pop();
		if (done.has(place)) continue; // a stale entry: this place already settled with fewer minutes
		done.add(place);
		settled.push({ place, minutes, via: via.get(place)! });
		if (place === target) break;
		for (const { to, minutes: walk } of next.get(place)!) {
			const offer = minutes + walk;
			// Only a strictly shorter offer wins, so a tie keeps the route found first.
			if (!done.has(to) && offer < (best.get(to) ?? Infinity)) {
				best.set(to, offer);
				via.set(to, place);
				frontier.push({ minutes: offer, place: to }); // the old, longer entry stays and is skipped
			}
		}
	}
	return settled;
}

// Dijkstra's shortest paths over walking times in whole minutes. Every path is two-way.
const (
	MaxPlaces  = 64
	MaxPaths   = 256
	MaxMinutes = 1440 // one day
)

type Path struct {
	A, B    string
	Minutes int
}

type Campus struct {
	Places []string
	Paths  []Path
}

// Settled is a place's final walking time and the settled place it was reached from.
// Via is "" for the start.
type Settled struct {
	Place   string
	Minutes int
	Via     string
}

type RouteError struct{ Code, Message string }

func (e *RouteError) Error() string { return e.Message }

type entry struct {
	minutes int
	place   string
}

// frontier is a min-heap for container/heap: fewer minutes first, then place id, so ties
// settle the same way in every language.
type frontier []entry

func (f frontier) Len() int { return len(f) }
func (f frontier) Less(i, j int) bool {
	if f[i].minutes != f[j].minutes {
		return f[i].minutes < f[j].minutes
	}
	return f[i].place < f[j].place
}
func (f frontier) Swap(i, j int) { f[i], f[j] = f[j], f[i] }
func (f *frontier) Push(x any)   { *f = append(*f, x.(entry)) }
func (f *frontier) Pop() any {
	old := *f
	last := old[len(old)-1]
	*f = old[:len(old)-1]
	return last
}

type walk struct {
	to      string
	minutes int
}

var placeID = regexp.MustCompile(`^[a-z][a-z0-9-]{0,23}$`)

func Neighbours(c Campus) (map[string][]walk, error) {
	if len(c.Places) > MaxPlaces || len(c.Paths) > MaxPaths {
		return nil, &RouteError{"too-big", fmt.Sprintf("up to %d places and %d paths", MaxPlaces, MaxPaths)}
	}
	next := make(map[string][]walk, len(c.Places))
	for _, place := range c.Places {
		if _, seen := next[place]; seen || !placeID.MatchString(place) {
			return nil, &RouteError{"bad-place", "place ids are unique lowercase slugs: " + place}
		}
		next[place] = nil
	}
	for _, p := range c.Paths {
		_, okA := next[p.A]
		_, okB := next[p.B]
		if !okA || !okB {
			return nil, &RouteError{"unknown-place", "a path joins places that don't exist: " + p.A + ", " + p.B}
		}
		if p.Minutes < 0 || p.Minutes > MaxMinutes {
			return nil, &RouteError{"bad-minutes", fmt.Sprintf("minutes are whole numbers from 0 to %d", MaxMinutes)}
		}
		next[p.A] = append(next[p.A], walk{p.B, p.Minutes})
		next[p.B] = append(next[p.B], walk{p.A, p.Minutes})
	}
	return next, nil
}

// Settle settles places in order of walking time from start. It stops as soon as target is
// settled; an empty target settles every reachable place.
func Settle(c Campus, start, target string) ([]Settled, error) {
	next, err := Neighbours(c)
	if err != nil {
		return nil, err
	}
	for _, place := range []string{start, target} {
		if _, ok := next[place]; !ok && (place == start || target != "") {
			return nil, &RouteError{"unknown-place", "no such place: " + place}
		}
	}
	best := map[string]int{start: 0}
	via := map[string]string{start: ""}
	done := map[string]bool{}
	f := &frontier{{0, start}}
	var settled []Settled
	for f.Len() > 0 {
		e := heap.Pop(f).(entry)
		if done[e.place] {
			continue // a stale entry: this place already settled with fewer minutes
		}
		done[e.place] = true
		settled = append(settled, Settled{e.place, e.minutes, via[e.place]})
		if e.place == target {
			break
		}
		for _, w := range next[e.place] {
			offer := e.minutes + w.minutes
			// Only a strictly shorter offer wins, so a tie keeps the route found first.
			if current, reached := best[w.to]; !done[w.to] && (!reached || offer < current) {
				best[w.to] = offer
				via[w.to] = e.place
				heap.Push(f, entry{offer, w.to}) // the old, longer entry stays and is skipped
			}
		}
	}
	return settled, nil
}