RWC: Start to End

start-to-end.js

const ORIGIN = 1;
const DESTINATION = 2;
const WALL = 3;

/**
 * @typedef {{
 * 	coordinates: string,
 * 	distanceFromOrigin: number,
 * 	shortestPaths: Direction[][]
 * }} DjikstraNode
 * 
 * Representation of a given cell, as well as memory of the currently shortest
 * known path to that cell.
 */

/**
 * Determines all valid neighbors of a given cell.
 * Valid neighbors are cells which…
 *  - Are in the bounds of the grid
 *  - Are not walls
 *  - Don't have a guaranteed shortest path yet (aren't yet "visited," according to Djikstra's algorithm)
 * 
 * @param {DjikstraNode} currentCell the "unvisited" cell with the shortest known path to get there
 * @param {DjikstraNode[]} unvisited list of all unvisited nodes
 * @returns {{
 * 		coordinates: string,
 * 		direction: 'up' | 'down' | 'left' | 'right'
 * }[]} valid neighbors we could move to
 */
function getValidNeighbors(currentCell, unvisited) {
	const [rowString, colString] = currentCell.coordinates.split(',');
	const row = Number.parseInt(rowString);
	const col = Number.parseInt(colString);

	/**
	 * @type {{
 	 *	coordinates: string,
 	 * 	direction: 'up' | 'down' | 'left' | 'right'
 	 * }[]}
	 */
	const neighbors = [];

	// If coordinates exist in `unvisited`, it means both that it's valid coordinates
	// in bound with the grid, and that its shortest path hasn't been guaranteed.

	if (unvisited.find(node => node.coordinates === `${row - 1},${col}`)) {
		neighbors.push({
			coordinates: `${row - 1},${col}`,
			direction: 'up'
		});
	}

	if (unvisited.find(node => node.coordinates === `${row + 1},${col}`)) {
		neighbors.push({
			coordinates: `${row + 1},${col}`,
			direction: 'down'
		});
	}

	if (unvisited.find(node => node.coordinates === `${row},${col - 1}`)) {
		neighbors.push({
			coordinates: `${row},${col - 1}`,
			direction: 'left'
		});
	}

	if (unvisited.find(node => node.coordinates === `${row},${col + 1}`)) {
		neighbors.push({
			coordinates: `${row},${col + 1}`,
			direction: 'right'
		});
	}

	return neighbors;
}

/**
 * Employ's Djikstra's algorithm to find the shortest path from the "1" cell to the "2"
 * cell, avoiding all "3" wall cells.
 * 
 * @see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm
 * @typedef {0 | 1 | 2 | 3} Cell
 * @typedef {'up' | 'down' | 'left' | 'right'} Direction
 * @param {Cell[][]} grid 2D grid —
 * 	`0` represents a generic space, `1` represents the origin,
 * 	`2` represents the destination, and `3` represents walls
 * @returns {Direction[][]} list of all of the shortest paths to reach the destination
 */
function startToEnd(grid) {
	/**
	 * All nodes for which the shortest path is NOT yet known.
	 * @type {DjikstraNode[]}
	 */
	const unvisited = [];

	/** @type {DjikstraNode} */
	let origin;
	/** @type {DjikstraNode} */
	let destination;
	/** @type {DjikstraNode} */
	let currentCell;

	// To start, determine every valid node, and mark all of them
	// except the origin as unvisited.
	for (let row = 0; row < grid.length; row++) {
		for (let column = 0; column < grid[row].length; column++) {
			const cell = grid[row][column];
			const coordinates = `${row},${column}`;

			if (cell === ORIGIN) {
				origin = {coordinates, distanceFromOrigin: 0, shortestPaths: []};
				currentCell = origin;
			} else if (cell !== WALL) {
				let node = {coordinates, distanceFromOrigin: Number.POSITIVE_INFINITY, shortestPaths: []};
				unvisited.push(node);

				if (cell === DESTINATION) {
					destination = node;
				}
			}
		}
	}

	// Calculate shortest distances to *every* cell in the grid
	while (unvisited.length > 0) {
		const validNeighbors = getValidNeighbors(currentCell, unvisited);
		const distanceToNeighbors = currentCell.distanceFromOrigin + 1;

		// If this path is the fastest so far to each of the current cell's neighbors,
		// replace the neighbors' current fastest paths with this one.
		for (let neighbor of validNeighbors) {
			const {coordinates, direction} = neighbor;
			const neighborNode = unvisited.find(node => node.coordinates === coordinates);
			if (distanceToNeighbors < neighborNode.distanceFromOrigin) {
				neighborNode.distanceFromOrigin = distanceToNeighbors;
				
				if (distanceToNeighbors === 1) {
					neighborNode.shortestPaths = [
						[direction]
					];
				} else {
					neighborNode.shortestPaths = currentCell
						.shortestPaths
						.map(path => [...path, direction]);
				}
			} else if (distanceToNeighbors === neighborNode.distanceFromOrigin) {
				if (distanceToNeighbors === 1) {
					neighborNode.shortestPaths.push([direction]);
				} else {
					const paths = currentCell
						.shortestPaths
						.map(path => [...path, direction]);

					neighborNode.shortestPaths.push(...paths);
				}
			}
		}

		// Remove current cell from consideration — there's no faster way to get it to it.
		const indexOfCurrentCell = unvisited.indexOf(currentCell);
		if (indexOfCurrentCell > -1) {
			unvisited.splice(indexOfCurrentCell, 1);
		}

		// Pick the unvisited cell with the next least distance to get there.
		let nextShortestDistance = Number.POSITIVE_INFINITY;
		for (let node of unvisited) {
			if (node.distanceFromOrigin < nextShortestDistance) {
				currentCell = node;
				nextShortestDistance = node.distanceFromOrigin;
			}
		}
	}

	// Profit.
	return destination.shortestPaths;
}

let grid1 = [
	[1, 0, 0],
	[0, 0, 2]
];
	
let grid2 = [
	[1, 3, 0],
	[0, 0, 2]
];

console.log(startToEnd(grid1));
console.log(startToEnd(grid2));