95 lines
2.0 KiB
JavaScript
95 lines
2.0 KiB
JavaScript
import * as R from "remeda";
|
|
import Victor from "@a-robu/victor";
|
|
|
|
import { readFile } from "../05/part1.js";
|
|
|
|
const V = (x, y) => new Victor(x, y);
|
|
|
|
export const findAs = (topoMap) => {
|
|
const locations = [];
|
|
|
|
topoMap.forEach((line, x) =>
|
|
line.forEach((v, y) => {
|
|
if (v === "a") locations.push([x, y]);
|
|
})
|
|
);
|
|
|
|
return locations;
|
|
};
|
|
|
|
export const findEnd = (topoMap) => {
|
|
let y;
|
|
let x = R.findIndex(topoMap, (row) => {
|
|
let z = row.indexOf("E");
|
|
if (z === -1) return false;
|
|
y = z;
|
|
return true;
|
|
});
|
|
return V(x, y);
|
|
};
|
|
|
|
const directions = [
|
|
[0, 1],
|
|
[0, -1],
|
|
[1, 0],
|
|
[-1, 0],
|
|
].map((d) => V(...d));
|
|
|
|
const outOfMap = (maxX, maxY) => (loc) => {
|
|
if (Math.min(loc.x, loc.y) < 0) return true;
|
|
if (loc.x >= maxX) return true;
|
|
if (loc.y >= maxY) return true;
|
|
return false;
|
|
};
|
|
|
|
const isReachable = (topoMap, pos) => {
|
|
const baseline = topoMap[pos.x][pos.y].charCodeAt(0);
|
|
|
|
return (next) => {
|
|
return baseline - topoMap[next.x][next.y].charCodeAt(0) <= 1;
|
|
};
|
|
};
|
|
|
|
function findShortestPath(topoMap) {
|
|
const final = findEnd(topoMap);
|
|
final.steps = 0;
|
|
|
|
topoMap = topoMap.map((line) =>
|
|
line.map((c) => c.replace("S", "a").replace("E", "z"))
|
|
);
|
|
|
|
const initial = findAs(topoMap);
|
|
|
|
const potentials = [final];
|
|
|
|
const beenThere = topoMap.map((line) => line.map(() => 9999));
|
|
|
|
const oom = outOfMap(topoMap.length, topoMap[0].length);
|
|
|
|
let failsafe = 10; //topoMap.length*topoMap[0].length ;
|
|
while (potentials.length > 0) {
|
|
// if(! failsafe--) return;
|
|
const pos = potentials.shift(); // depth-first
|
|
|
|
if (beenThere[pos.x][pos.y] <= pos.steps) continue;
|
|
beenThere[pos.x][pos.y] = pos.steps;
|
|
|
|
const next = directions
|
|
.map((d) => d.clone().add(pos))
|
|
.filter(R.isNot(oom))
|
|
.filter(isReachable(topoMap, pos));
|
|
|
|
next.forEach((n) => (n.steps = pos.steps + 1));
|
|
|
|
potentials.push(...next);
|
|
}
|
|
|
|
return R.pipe(
|
|
initial,
|
|
R.map(([x, y]) => beenThere[x][y]),
|
|
R.minBy(R.identity)
|
|
);
|
|
}
|
|
|
|
export default findShortestPath;
|