Skip to content

Instantly share code, notes, and snippets.

@kevinleedrum
Last active December 12, 2022 16:52
Show Gist options
  • Save kevinleedrum/1aa15a65c6ce944896b5331b8787565d to your computer and use it in GitHub Desktop.
Save kevinleedrum/1aa15a65c6ce944896b5331b8787565d to your computer and use it in GitHub Desktop.
Advent of Code Day 2022 - Day 12
const INPUT = `...`;
console.log(findPathDistance("S", "E")); // Part 1
console.log(findPathDistance("E", "a", true)); // Part 2
function findPathDistance(startChar, endChar, isReverse = false) {
const { grid, start } = parseInput(startChar);
const q = [[...start, 0]];
const visited = new Set();
return findPath();
function findPath() {
for (let i = 0; i < q.length; i++) {
const [x, y, d] = q[i];
if (visited.has([x, y].join(","))) continue;
if (grid[x][y] === endChar) return d;
visited.add([x, y].join(","));
const neighbors = getNeighbors(x, y);
q.push(...neighbors.map(([x, y]) => [x, y, d + 1]));
}
}
function parseInput(startChar) {
const grid = [];
let start = [0, 0];
INPUT.split(/\n/).forEach((line, y) => {
line.split("").forEach((char, x) => {
grid[x] = grid[x] || [];
grid[x].push(char);
if (char === startChar) start = [x, y];
});
});
return { grid, start };
}
function getNeighbors(x, y) {
const neighbors = [];
if (isWalkable(x, y - 1, grid[x][y])) neighbors.push([x, y - 1]);
if (isWalkable(x, y + 1, grid[x][y])) neighbors.push([x, y + 1]);
if (isWalkable(x - 1, y, grid[x][y])) neighbors.push([x - 1, y]);
if (isWalkable(x + 1, y, grid[x][y])) neighbors.push([x + 1, y]);
return neighbors;
}
function isWalkable(x, y, h) {
if (!grid[x] || !grid[x][y]) return false;
if (visited.has([x, y].join(","))) return false;
if (!isReverse && getChar(grid[x][y]) <= getChar(h)) return true;
if (isReverse && getChar(grid[x][y]) >= getChar(h)) return true;
if (
Math.abs(getChar(h).charCodeAt(0) - getChar(grid[x][y]).charCodeAt(0)) ===
1
)
return true;
return false;
}
function getChar(c) {
if (c === "S") return "a";
if (c === "E") return "z";
return c;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment