advent2022/d12/main.js

const fs = require('fs');
const readline = require('readline');

function computeScore(pos, target, map) {
}

function taxicab(src, target) {
    return Math.abs(src[0] - target[0]) + Math.abs(src[1] - target[1]);
}

let seen = {};

function pushPossibility(arr, currentPos, pos, target, map) {
    if (pos[0] < 0 || pos[1] < 0 || pos[0] >= map[0].length || pos[1] >= map.length || map[pos[1]][pos[0]] - map[currentPos.pos[1]][currentPos.pos[0]] > 1 || arr.find(i => i.pos[0] === pos[0] && i.pos[1] === pos[1]) || seen[pos[0]+'x'+pos[1]])
        return;
    let elevScore = map[target[1]][target[0]] - map[pos[1]][pos[0]]
    seen[pos[0]+'x'+pos[1]] = true;
    arr.push({ pos: pos, elevScore: elevScore, score: elevScore + taxicab(pos, target) + currentPos.score, history: currentPos });
}

function pushPossibilities(arr, target, map) {
    let pos = arr.shift();
    pushPossibility(arr, pos, [pos.pos[0]+1, pos.pos[1]], target, map);
    pushPossibility(arr, pos, [pos.pos[0]-1, pos.pos[1]], target, map);
    pushPossibility(arr, pos, [pos.pos[0], pos.pos[1]+1], target, map);
    pushPossibility(arr, pos, [pos.pos[0], pos.pos[1]-1], target, map);
    return arr.sort((a, b) => a.score - b.score);
}

function backtrack(item) {
    let result = [];
    while (item) {
        result.push(item.pos);
        item = item.history;
    }
    return result.reverse();
}

function AStar(pos, target, map) {
    let possibilities = [ { pos: pos, score: taxicab(pos, target), elevScore: 0 } ];
    seen = {};
    let output = null;
    do {
        possibilities = pushPossibilities(possibilities, target, map);
        output = possibilities.filter(i => i.pos[0] === target[0] && i.pos[1] === target[1]);
    } while (possibilities.length && !output.length);
    return backtrack(output[0]).length -1;
}

async function main() {
    let map = [];
    let currentPos = [];
    let target = [];
    let lineIndex = 0;
    for await (let line of readline.createInterface({ input: process.stdin })) {
        map.push(line.split('').map((i, pos) => {
            if (i === 'S') { currentPos = [ pos, lineIndex ]; i = 'a'; }
            if (i === 'E') { target = [ pos, lineIndex ]; i = 'z'; }
            return i.charCodeAt(0) - 'a'.charCodeAt(0);}));
        ++lineIndex;
    }
    console.log("Step 1: ", AStar(currentPos, target, map));
    let minSteps = Infinity;
    for (let i =0; i < map.length; ++i)
        for (let j =0; j < map.length; ++j)
            if (map[i][j] === 0) {
                let steps = AStar([j, i], target, map);
                if (steps > 0)
                    minSteps = Math.min(minSteps, steps);
            }
    console.log("Step 2: ", minSteps);
};

(main());