You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
98 lines
2.2 KiB
98 lines
2.2 KiB
import { readFileSync } from 'node:fs'; |
|
|
|
const input = readFileSync('input', 'utf-8'); |
|
|
|
function getMap() { |
|
return input |
|
.split('\n') |
|
.filter(line => line) |
|
.map((line, y) => line |
|
.split('') |
|
.map((elevation, x) => { |
|
const isStart = elevation === 'S'; |
|
const isEnd = elevation === 'E'; |
|
elevation = elevation.replaceAll('S', 'a'); |
|
elevation = elevation.replaceAll('E', 'z'); |
|
const height = elevation.charCodeAt(0) - 97; |
|
return { |
|
x, |
|
y, |
|
height, |
|
isStart, |
|
isEnd, |
|
path: null |
|
}; |
|
}) |
|
); |
|
} |
|
|
|
const cardinals = [ |
|
[0, -1], // North |
|
[1, 0], // East |
|
[0, 1], // South |
|
[-1, 0] // West |
|
]; |
|
|
|
// Recursively walk through map stopping whenever we encounter a square with a |
|
// shorter path than ours |
|
function solve(map, x, y, canMoveToSquare, path = []) { |
|
const square = map[y][x]; |
|
path = [...path, [x, y]]; |
|
|
|
if (square.path && square.path.length <= path.length) { |
|
return; |
|
} |
|
|
|
square.path = path; |
|
|
|
cardinals |
|
.map(c => map[y + c[1]]?.[x + c[0]]) |
|
// Filter undefined squares |
|
.filter(s => s) |
|
// Filter squares we can't reach |
|
.filter(s => canMoveToSquare(square, s)) |
|
.forEach(s => solve(map, s.x, s.y, canMoveToSquare, [...path])); |
|
} |
|
|
|
function shortestPathStartToEnd() { |
|
const map = getMap(); |
|
const start = map.flat().find(square => square.isStart); |
|
solve( |
|
map, |
|
start.x, |
|
start.y, |
|
(from, to) => to.height <= from.height + 1 |
|
); |
|
const end = map.flat().find(square => square.isEnd); |
|
return end.path; |
|
} |
|
|
|
function shortestPathEndToA() { |
|
const map = getMap(); |
|
const end = map.flat().find(square => square.isEnd); |
|
solve( |
|
map, |
|
end.x, |
|
end.y, |
|
(from, to) => to.height >= from.height - 1 |
|
); |
|
|
|
const squareWithShortestDistance = map |
|
.flat() |
|
.filter(square => square.path) |
|
.filter(square => square.height === 0) |
|
.sort((s1, s2) => s1.path.length - s2.path.length)[0]; |
|
|
|
return squareWithShortestDistance.path; |
|
} |
|
|
|
|
|
console.log('This will take a minute...'); |
|
|
|
let path; |
|
|
|
path = shortestPathStartToEnd(); |
|
console.log(`The least steps from start to end is: ${path.length - 1}`); |
|
|
|
path = shortestPathEndToA(); |
|
console.log(`The least steps from 'a' to end is: ${path.length - 1}`);
|
|
|