Taco Crawl Challenge (Sightseeing Optimization)

Readme.md

Requirements

• npm install heap-js @types/node

Running without debug

• install TSX locally or globally as --save-dev dependency
• TSX can run typescript files
• or use TSX via NPX: npx tsx filename.ts

Running in debug (VSCode)

• install the Typescript compiler (TSC)
• I am using this build task in VSCode for the debug build (put into launch.json)

    {
			"label": "compile-ts-file",
			"type": "shell",
			"command": "tsc",
			"args": [
				"${file}",
				"--target", "esnext",
				"--module", "nodenext",
				"--outDir", "./out",
				"--sourcemap",
				"--lib", "esnext",
				"--types", "node",
			],
			"problemMatcher": [
				"$tsc"
			],
			"group": "build"
		}

• I am using this launch configuration for debugging (put into tasks.json)

    {
			"preLaunchTask": "compile-ts-file",
			"name": "Debug TS File",
			"program": "${file}",
			"request": "launch",
			"skipFiles": [
				"<node_internals>/**"
			],
			"type": "node",
			"outFiles": [
				"${workspaceFolder}/**/${fileBasenameNoExtension}.(m|c|)js(|.map)",
				"!**/node_modules/**"
			]
		}

Algorithm.md

optimizing visited value per distance travelled (sightseeing, tourist problem):

• is it possible to turn tastiness and distance into one weight?

  • weight w = (target tastiness / edge length, edge length)
  • (a, x) + (a, y) = (a, x + y)
  • (a, x) + (b, x) = ((a + b)/2 , 2x)
  • (a, x) + (b, y) = ((x·a + y·b)/(x+y), x+y) = (2x/(x+y) ·a, (x+y)/2) + (2y/(x+y) ·b, (x+y)/2)
  • weights are compared only in the first component

• essential insights:

  • for any path, the result is a convex combination of the segment values weighed by the segment distance to the total distance.
  • the total value of a path can only increase by adding edges with higher value than the current weighted average
  • it makes most sense to try the highest value edges first
    • we can walk through the value-sorted list of edges to search for new nodes
  • when the taco spots are fixed (defined via "explicit edges"), we only need to find the smallest distance for connecting them
    • we can walk through the distance-sorted list of edges to compute the lower bound heuristic
    • the upper bound is simply a set of explicit edges without any connecting edges between

• we can use the B* search algorithm

  • each node is a set of explicitly selected best edges together with a set of heuristically generated implicit edges in between the explicit ones
    • transpositions (redundancy of nodes) are handled by merging nodes with equal path
    • we need to prevent cycles to allow propagation of results from children to parents
  • edges are directed and asymmetric
  • the upper bound is the sum of the explicit best edges (without implicit ones)
  • the lower bound is the sum of the explicit best edges plus a heuristic combination with implicit edges (which connect the explicit edges into a path from the starting point)
    • problem: finding the best implicit edges is complex
      • we can discard any edges with too low value directly
      • the precise optimum is not important for a lower bound, therefore I use Kruskal's Algorithm as a heuristic to find a good path.
    • non-incident explicit edges need to be connected with a direct edge
    • one explicit edge must be connected to the starting point with a direct edge
  • each node expansion tests adding one or two new Taco Spots by adding one explicit edge
  • when new tree nodes are explored, it requires the backup process to propgate changes to parents (including transposed parents), repeated recursively until the root
    • take the maximum lower bound and maximum upper bound independently from any children
  • nodes whose upper bound is strictly dominated by the lower bound of a sibling are pruned from the priority queue (removed)
    • same for explored new child nodes dominated by the parent
    • I try to compute all final leafs and update the best final node during the process

• B* finds the winner in the 2nd 5th node expansion but requires to evaluate 1456 736 503 node expansions in total to prove it.

  The optimal path has a total tastiness of 49 97, a total value of 3.0815368890863177 2.8945153290979557 and a total distance of 15.901156391649948 33.51165531060739.

  === Winner
  (1) [{…}]
  ┌─────────┬──────────────────┬───────────┬────────────────────┬────────────────────┬────────────────────┬───────────────────┐
  │ (index) │ node             │ tastiness │ upper bound        │ min distance       │ lower bound        │ max distance      │
  ├─────────┼──────────────────┼───────────┼────────────────────┼────────────────────┼────────────────────┼───────────────────┤
  │ 0       │ '0,7,5,6,2,10,4' │ 97        │ 4.2719432557779635 │ 15.683728923454211 │ 2.8945153290979557 │ 33.51165531060739 │
  └─────────┴──────────────────┴───────────┴────────────────────┴────────────────────┴────────────────────┴───────────────────┘
  

• The "MaximumFringe" heuristic finds the same winner in fewer node expansions due to lower upper bounds but maybe underestimates the upper bound in special problems.

taco_crawl_challenge.ts

import Heap from "heap-js";

let spotLimit = 8;

class TacoSpot
{
	public readonly distanceFrom = new Map<TacoSpot, number>();

	constructor(
		public name: number,
		public coordinates: [number, number],
		public tastiness: number,
	)
	{
	}

	public static all = new Map([
		[0, new TacoSpot(0, [0, 0], 0)],
		[1, new TacoSpot(1, [2, 8], 7)],
		[2, new TacoSpot(2, [15, 3], 17)],
		[3, new TacoSpot(3, [6, 6], 8)],
		[4, new TacoSpot(4, [20, 15], 30)],
		[5, new TacoSpot(5, [11, 2], 12)],
		[6, new TacoSpot(6, [14, 1], 15)],
		[7, new TacoSpot(7, [7, 3], 5)],
		[8, new TacoSpot(8, [1, 12], 12)],
		[9, new TacoSpot(9, [3, 6], 3)],
		[10, new TacoSpot(10, [14, 13], 18)],
	]);
	public static origin = TacoSpot.all.get(0)!;
}

class Stats
{
	public tastiness: number = NaN;
	public distance: number = NaN;
	public utility: number = NaN;

	constructor();
	constructor(array: Stats[]);
	constructor(tastiness: number, distance: number);
	constructor(
		arg0?: number | Stats[],
		arg1?: number,
	)
	{
		if (arg0 !== undefined)
		{
			this.computeStats(arg0 as any, arg1 as any);
		}
	}

	public computeStats(array: Stats[]): void;
	public computeStats(tastiness: number, distance: number): void;
	public computeStats(
		arg0: number | Stats[],
		arg1?: number,
	)
	{
		if (Array.isArray(arg0))
		{
			let {tastiness, distance, utility} = Stats.join(arg0);
			this.tastiness = tastiness;
			this.distance = distance;
			this.utility = utility;
		}
		else
		{
			this.tastiness = arg0;
			this.distance = arg1!;
			this.utility = this.tastiness / this.distance;
		}
	}

	public static join(array: Stats[]): Stats
	{
		let [tastiness, distance] =
				array.reduce(
					([tastiness, distance], s) => [tastiness + s.tastiness, distance + s.distance]
					, [0, 0]
				);
		
		return Object.assign(new Stats(), {tastiness, distance, utility: Stats.computeUtility(tastiness, distance)});
	}

	public static computeDistance(start: TacoSpot, end: TacoSpot)
	{
		return Math.sqrt((end.coordinates[0] - start.coordinates[0]) ** 2 + (end.coordinates[1] - start.coordinates[1]) ** 2);
	}

	public static computeUtility(tastiness: number, distance: number)
	{
		return (distance != 0)? tastiness / distance : 0;
	}
}

class Edge extends Stats
{
	public readonly start: TacoSpot;
	public readonly end: TacoSpot;

	private constructor(
		start: TacoSpot | number,
		end: TacoSpot | number,
	)
	{
		let start_: TacoSpot;
		let end_: TacoSpot;
		
		if (typeof(start) === "number")
			start_ = TacoSpot.all.get(start)!;
		else
			start_ = start;
		if (typeof(end) === "number")
			end_  = TacoSpot.all.get(end)!;
		else
			end_ = end;

		console.assert(start_ != undefined && end_ != undefined);
		super(end_.tastiness, Stats.computeDistance(start_, end_))

		this.start = start_;
		this.end = end_;
	}

	public static get(start: number, end: number)
	{
		let edge = Edge.toFromNode.get(end)?.get(start);
		return edge;
	}

	public static readonly zero = new Edge(TacoSpot.origin, TacoSpot.origin);

	public static sorted: Edge[];
	public static distanceSorted: Edge[];
	// the collection of keys will be sorted for each map
	public static nodeIndexOf: Map<Edge, number>;
	public static toFromNode: Map<number, Map<number,Edge>>;  // to x from y
	public static fromToNode: Map<number, Map<number, Edge>>;  // from x to y
	static {
		this.createEdges();
		this.sortEdges();
		this.fillEdgeMaps();
	}

	private static createEdges()
	{
		this.sorted = [];

		for (let index = 1; TacoSpot.all.has(index); index++) {
			
			const targetSpot = TacoSpot.all.get(index)!.name;

			for (let j = 0; TacoSpot.all.has(j); j++) {
				const startSpot = TacoSpot.all.get(j)!.name;
				
				if (targetSpot === startSpot)
					continue;
				
				let edge = new Edge(startSpot, targetSpot);
				Edge.sorted.push(edge);
			}
		}

		this.distanceSorted = [...this.sorted];
	}

	private static sortEdges()
	{
		Edge.nodeIndexOf = new Map();
		Edge.sorted.sort((a, b) => b.utility - a.utility);
		for (let i = 0; i < Edge.sorted.length; i++) {
			const edge = Edge.sorted[i];
			
			this.nodeIndexOf.set(edge, i);
		}

		Edge.distanceSorted.sort((a, b) => a.distance - b.distance);
	}

	private static fillEdgeMaps()
	{
		Edge.toFromNode = new Map();
		Edge.fromToNode = new Map();

		for (let i = 0; i < Edge.sorted.length; i++) {
			const edge = Edge.sorted[i];
			
			let map = Edge.toFromNode.get(edge.end.name) ?? new Map<number, Edge>();
			map.set(edge.start.name, edge);
			Edge.toFromNode.set(edge.end.name, map);

			map = Edge.fromToNode.get(edge.start.name) ?? new Map<number, Edge>();
			map.set(edge.end.name, edge);
			Edge.fromToNode.set(edge.start.name, map);
		}
	}
}

class EdgeStats extends Stats
{
	public edges: Edge[];
	public next!: Map<TacoSpot, Edge>;
	public previous!: Map<TacoSpot, Edge>;

	public implicitEdges: Edge[];
	public toNodeImplicitly!: Map<TacoSpot, Edge>;
	public fromNodeImplicitly!: Map<TacoSpot, Edge>;
	
	public explicitNext: Map<TacoSpot, Edge>;
	public explicitPrevious: Map<TacoSpot, Edge>;
	public explicitEdgeSet!: Set<Edge>;
	constructor(public explicitEdges: Edge[], public uniqueSourceSpot = false, public useBestEdge = false)
	{
		super();
		this.explicitEdges = [...explicitEdges];
		[this.explicitNext, this.explicitPrevious] = this.generateExplicitMaps();
		this.implicitEdges = this.computeImplicitEdges();
		this.edges = [...explicitEdges, ...this.implicitEdges];
		super.computeStats(this.edges);
	}

	private sourceSpots!: Set<TacoSpot>;
	private targetSpots!: Set<TacoSpot>;
	public computeImplicitEdges()
	{
		let implicitEdges = new Array<Edge>();
		this.toNodeImplicitly = new Map<TacoSpot, Edge>();
		this.fromNodeImplicitly = new Map<TacoSpot, Edge>();

		this.next = new Map(this.explicitNext);
		this.previous = new Map(this.explicitPrevious);

		this.initSourceTargetSpots(this.explicitEdges);

		for (let edge of Edge.distanceSorted)
		{
			if (this.sourceSpots.size <= 0)
				break;
			
			if (!this.sourceSpots.has(edge.end) || (!this.useBestEdge && !this.targetSpots.has(edge.start)))
				continue;
			if (this.toNodeImplicitly.has(edge.end))
				continue;
			if (this.uniqueSourceSpot && this.fromNodeImplicitly.has(edge.start))
				continue;
			if (this.isContainedInPath(edge.end, edge.start))
				continue;
			
			this.toNodeImplicitly.set(edge.end, edge);
			this.fromNodeImplicitly.set(edge.start, edge);
			this.next.set(edge.start, edge);
			this.previous.set(edge.end, edge);
			this.sourceSpots.delete(edge.end);
			this.targetSpots.delete(edge.start);
			implicitEdges.push(edge);
		}

		return implicitEdges;
	}

	public initSourceTargetSpots(edges: Edge[])
	{
		this.sourceSpots = new Set<TacoSpot>();
		this.targetSpots = new Set<TacoSpot>();
		this.explicitEdgeSet = new Set<Edge>();

		for (let edge of edges)
		{
			this.targetSpots.add(edge.end);
			this.sourceSpots.add(edge.start);
			this.explicitEdgeSet.add(edge);
		}

		this.targetSpots.add(TacoSpot.origin);

		for (let spot of this.targetSpots.values())
		{
			if (this.sourceSpots.has(spot))
			{
				this.targetSpots.delete(spot);
				this.sourceSpots.delete(spot);
			}
		}
	}

	public generateExplicitMaps()
	{
		let explicitNext = new Map<TacoSpot, Edge>();
		let explicitPrevious = new Map<TacoSpot, Edge>();

		for (let edge of this.explicitEdges)
		{
			explicitNext.set(edge.start, edge);
			explicitPrevious.set(edge.end, edge);
		}

		return [explicitNext, explicitPrevious];
	}

	/** indicates whether the edge can be added without violating the path criterion  */
	public canAddEdgeToPath(edge: Edge)
	{
		let containsEdge = this.explicitEdgeSet.has(edge);
		if (containsEdge)
			return false;

		let isOccupied = this.explicitPrevious.get(edge.end) !== undefined || this.explicitNext.get(edge.start) !== undefined;
		if (isOccupied)
			return false;

		return !this.isContainedInPath(edge.end, edge.start, this.explicitNext);
	}

	public isContainedInPath(start: TacoSpot, spot: TacoSpot, next = this.next)
	{
		let current: TacoSpot | undefined = start;
		while(current !== undefined)
		{
			if (current === spot)
				return true;

			var edge = next.get(current);
			current = edge?.end;
		}

		return false;
	}
}

class EdgeSet
{
	public upperBound: Stats;
	public lowerBound: Path;

	constructor(public explicitEdges: Edge[])
	{
		//this.upperBound = new SpanningTree(explicitEdges);  // somewhere between Stats and Path
		//this.upperBound = new MaximumFringe(explicitEdges);  // not sufficient in generality but provides faster results by reducing the upper bound estimate
		this.upperBound = new Stats(explicitEdges);
		this.lowerBound = new Path(explicitEdges);
	}

	public getSpotList(): string
	{
		let spots = [TacoSpot.origin];
		
		let current = TacoSpot.origin;
		while (this.lowerBound.next.has(current))
		{
			current = this.lowerBound.next.get(current)!.end;
			spots.push(current);
		}

		return spots.map(s => s.name).join(",");
	}

	public getStatistics()
	{
		return ({
			node: this.getSpotList(),
			tastiness: this.lowerBound.tastiness,
			"upper bound": this.upperBound.utility,
			"upper distance": this.upperBound.distance,
			"lower bound": this.lowerBound.utility,
			"lower distance": this.lowerBound.distance, 
		});
	}
}

class SpanningTree extends EdgeStats
{
	constructor(explicitEdges: Edge[])
	{
		super(explicitEdges, false);
	}
}

class MaximumFringe extends EdgeStats
{
	/** Adds the biggest utility edge whose target equals a source spot */
	constructor(explicitEdges: Edge[])
	{
		super(explicitEdges, true, true);
	}
	
}

class Path extends EdgeStats
{
	/** Missing edges betweeen adjacent edges are added */
	constructor(explicitEdges: Edge[])
	{
		super(explicitEdges, true);
	}
}

class BStarTree
{
	public children = new Heap<BStarTree>((a, b) => b.node.upperBound.utility - a.node.upperBound.utility);
	public bestNode: EdgeSet;
	public root: BStarTree;
	public nodes: Map<string, BStarTree>;
	
	private constructor(
		public node: EdgeSet,
		public parents: BStarTree[],
		public sortedEdgeStart: number,  // edge index which is added first during the search into children
	)
	{
		this.bestNode = node;
		this.root = parents[0]?.root ?? this;
		this.nodes = parents[0]?.nodes ?? new Map<string, BStarTree>();
	}

	public getNode(node: EdgeSet, parents: BStarTree[], sortedEdgeStart: number): [BStarTree, boolean]
	{
		let spotList = node.getSpotList();

		let transposedNode = this.nodes.get(spotList);
		if (!transposedNode)
		{
			let newNode = new BStarTree(node, parents, sortedEdgeStart);
			this.nodes.set(spotList, newNode);
			return [newNode, true];
		}

		if (node.upperBound.utility < transposedNode.node.upperBound.utility)
		{
			transposedNode.node = node;
		}

		for (let parent of parents)
		{
			if (transposedNode.includes(parent) || parent.includes(transposedNode))
				continue;
			
			transposedNode.parents.push(parent);
			parent.children.push(transposedNode);
		}
		return [transposedNode, false];
	}

	/** Creates relevant children at the current node */
	public expand()
	{
		let maxLowerNode = this.bestNode;
		let maxUpperNode = null as EdgeSet | null;
		let children = new Array<BStarTree>();
		let oldNodes = new Set<BStarTree>();

		for (let i=this.sortedEdgeStart; i < Edge.sorted.length; i++)
		{
			const edge = Edge.sorted[i];

			if (edge.utility < this.node.lowerBound.utility)
				break;

			if (!this.node.lowerBound.canAddEdgeToPath(edge))
				continue;

			const newNode = new EdgeSet([...this.node.explicitEdges, edge]);

			// the upper bound is not monotonous (because the distance varies)
			if (newNode.upperBound.utility <= this.root.bestNode.lowerBound.utility)
				continue;
			if (newNode.lowerBound.edges.length > spotLimit)
				continue;

			let [node, isNew] = this.getNode(newNode, [this], i+1);
			if (!node.includes(this))
			{
				children.push(node);
				if (!isNew) oldNodes.add(node);
			}

			if (!(newNode.lowerBound.utility <= this.root.bestNode.lowerBound.utility) && this !== this.root)
				this.root.bestNode = newNode;
			if (!(newNode.lowerBound.utility <= maxLowerNode.lowerBound.utility))
				maxLowerNode = newNode;
			if (!(newNode.upperBound.utility <= maxUpperNode?.upperBound.utility!))
				maxUpperNode = newNode;
		}

		let [retainedChildren, removedNodes] = this.updateChildren(children, maxLowerNode, maxUpperNode);

		let newChildren = retainedChildren.filter(n => !oldNodes.has(n));

		return [newChildren, removedNodes];
	}

	public includes(node: BStarTree, debug = 20): boolean
	{
		if (node === this)
			return true;

		return this.children.heapArray.some(child => child.includes(this, debug -1));
	}

	public updateChildren(children: BStarTree[], maxLowerNode: EdgeSet, maxUpperNode: EdgeSet | null)
	{
		let [retainedChildren, removedNodes] = this.filterChildren(children, maxLowerNode);

		if (retainedChildren.length > 0)
		{
			this.propagateBackUp(maxLowerNode, maxUpperNode, removedNodes);
		}

		return [retainedChildren, removedNodes];
	}

	private filterChildren(children: BStarTree[], maxLowerNode: EdgeSet)
	{
		if (this.bestNode.lowerBound.utility >= maxLowerNode.lowerBound.utility) {
			this.children.clear();
			this.children.addAll(children);
			return [children, []];
		}

		let removedNodes = new Array<BStarTree>();
		let retainedChildren = new Array<BStarTree>();

		this.bestNode = maxLowerNode;

		for (let t of children) {

			const isRetained = t.node.upperBound.utility > this.bestNode.lowerBound.utility
				|| t.node.lowerBound.utility >= this.bestNode.lowerBound.utility;
			if (isRetained) {
				retainedChildren.push(t);
			}

			else {
				removedNodes.push(t);
			}
		}

		this.children.clear();
		this.children.addAll(retainedChildren);

		return [retainedChildren, removedNodes];
	}

	public propagateBackUp(maxLowerNode: EdgeSet, maxUpperNode: EdgeSet | null, outRemovedNodes: BStarTree[])
	{
		if (this.node.lowerBound.utility < maxLowerNode.lowerBound.utility)
			this.node.lowerBound = maxLowerNode.lowerBound;
		if (maxUpperNode)
			this.node.upperBound = maxUpperNode.upperBound;

		for (let parent of this.parents)
		{
			var [_, removed] = parent.updateChildren(parent.children.heapArray, maxLowerNode, maxUpperNode);
			outRemovedNodes.push(...removed);
		}
	}

	static search()
	{
		const root = new BStarTree(new EdgeSet([]), [], 0);
		root.node.upperBound.utility = Infinity;

		const fringe = new Heap<BStarTree>((a, b) => b.node.upperBound.utility - a.node.upperBound.utility);
		fringe.init([root]);

		for (let cycle = 1; ; cycle++)
		{
			//console.log(`fringe (${fringe.length} node/s)`);
			//console.table(fringe.heapArray.map(t => t.node.getStatistics() ).sort((a, b) => b["lower bound"] - a["lower bound"]));

			if (fringe.isEmpty())
				break;
			console.log(`=== cycle ${cycle}`);

			let current = fringe.pop()!;
			//console.log(`children of ${current.node.getSpotList()}`);
			
			let [newChildren, removedNodes] = current.expand();
			//console.table(newChildren.map(t => t.node.getStatistics() ).sort((a,b) => b["lower bound"] - a["lower bound"]));

			let removedLeafs = BStarTree.getLeafs(removedNodes);
			let retainedLeafs = fringe.heapArray.concat(newChildren).filter(n => !removedLeafs.has(n) && n.node.upperBound.utility >= root.bestNode.lowerBound.utility);
			fringe.clear();
			fringe.addAll(retainedLeafs);
		}

		return root;
	}

	/** return Set of every node of (nodes or node.children) with no .children
	 * (→ an optimal formal language can do this in one line.) */
	static getLeafs(nodes: BStarTree[])
	{
		let leafs = new Set<BStarTree>();

		while (nodes.length > 0)
		{
			let newNodes = new Array<BStarTree>();
			for (let node of nodes) {

				if (node.children.isEmpty())
					leafs.add(node);

				else
					newNodes.push(...node.children.heapArray);
			}
			nodes = newNodes;
		}

		return leafs;
	}
}

const result = BStarTree.search();

console.log(`=== Winner`)
console.table([result.bestNode.getStatistics()]);
debugger;

updated coordinates of spot 6 from 14,3 to 14,1

Changed wrong remarks in algorithm explanation and code comments.

Renamed "min distance" and "max distance" to "upper distance" and "lower distance"

Optimization: testing less useful edges is redundant. Therefore: Only add explicit edges which can improve the parent's total utility in hope to raise the lower bound.