Skip to content

Instantly share code, notes, and snippets.

@kevinleedrum

kevinleedrum/advent-of-code-2022-12.js

Last active December 12, 2022 16:52
Download ZIP

Revisions

  1. kevinleedrum revised this gist Dec 12, 2022. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions advent-of-code-2022-12.js
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ function findPathDistance(startChar, endChar, isReverse = false) {
    if (visited.has([x, y].join(","))) continue;
    if (grid[x][y] === endChar) return d;
    visited.add([x, y].join(","));
    const neighbors = getNeighbors(x, y, isReverse);
    const neighbors = getNeighbors(x, y);
    q.push(...neighbors.map(([x, y]) => [x, y, d + 1]));
    }
    }
    @@ -33,16 +33,16 @@ function findPathDistance(startChar, endChar, isReverse = false) {
    return { grid, start };
    }

    function getNeighbors(x, y, isReverse) {
    function getNeighbors(x, y) {
    const neighbors = [];
    if (isWalkable(x, y - 1, grid[x][y], isReverse)) neighbors.push([x, y - 1]);
    if (isWalkable(x, y + 1, grid[x][y], isReverse)) neighbors.push([x, y + 1]);
    if (isWalkable(x - 1, y, grid[x][y], isReverse)) neighbors.push([x - 1, y]);
    if (isWalkable(x + 1, y, grid[x][y], isReverse)) neighbors.push([x + 1, y]);
    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, isReverse) {
    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;
  2. kevinleedrum revised this gist Dec 12, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion advent-of-code-2022-12.js
    View file
    Original file line number Diff line number Diff line change
    @@ -11,7 +11,7 @@ function findPathDistance(startChar, endChar, isReverse = false) {

    function findPath() {
    for (let i = 0; i < q.length; i++) {
    const [x, y, d] = [...q][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(","));
  3. kevinleedrum revised this gist Dec 12, 2022. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions advent-of-code-2022-12.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    const INPUT = `...`;

    console.log(findPathDistance("S", "E"));
    console.log(findPathDistance("E", "a", true));
    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);
  4. kevinleedrum created this gist Dec 12, 2022.
    63 changes: 63 additions & 0 deletions advent-of-code-2022-12.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    const INPUT = `...`;

    console.log(findPathDistance("S", "E"));
    console.log(findPathDistance("E", "a", true));

    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, isReverse);
    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, isReverse) {
    const neighbors = [];
    if (isWalkable(x, y - 1, grid[x][y], isReverse)) neighbors.push([x, y - 1]);
    if (isWalkable(x, y + 1, grid[x][y], isReverse)) neighbors.push([x, y + 1]);
    if (isWalkable(x - 1, y, grid[x][y], isReverse)) neighbors.push([x - 1, y]);
    if (isWalkable(x + 1, y, grid[x][y], isReverse)) neighbors.push([x + 1, y]);
    return neighbors;
    }

    function isWalkable(x, y, h, isReverse) {
    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;
    }
    }