AoC 2022: day24.js

const util = require('util')

const mapString = `
#.########################################################################################################################
#<^vvv<v^v>^vvv.v<vv<>^^<^><.vvv^>v<^<<<<^>^vv^>^<^>>v>v^v^>^v>vv>^.^..v<^<^^^>>>><<>v<^^^v<>>><>.vv^vv>v.vv<<^<.v...^v.<#
#<^^><><^^^<^>>v^^>v<^vvvv><vv<v.<vv^v<>v^.v^>v^v<>^<>^<vv.v^.^<<<^^^..<.><<v<vv^<v^^>>.><v<vv.>v>><<v.v^<^<v^^^^vv^v>^v>#
#<^.>>v<<vv^^<<<<<.<v<>^>v^v<v<<<^<v^<<vvvv>v<^v<^v<>v.<>v^^^.^vv.<vv>v<^^v^>>.><^.><<<>v^>><^.<><>v^vv>>^v>>.><vvv^<<>v<#
#>v^v<>^<.^.^>><>>..<vv<>^>>vv<.<.<^v<^<>>><<^v.v^<v<vv><v.<v.>v^v^<.v>^v^<^.v>.v.>^<v^>vv><<v.>^>v><<^vv<v^>v>v>.>v>>><.#
#><<<^<v.><>>^>v<^><^<^v.^v<vv<<^^vvv><^^>>>>v^.^^v^<v^^.vv^v^<.v<v^^v<^..>>v<^v^.v^^^^.>v^<vv^<<>><<>vv><^<<^^><..vv.v^.#
#<^>^.^v.><^>.v<v<>^<^<<<<<^^><vv.>^v><^<.>>.><^<v>>>^^^vvv<>v^^^<.^v^<^v<v>^.^.<>v^.v>v<v^<^^vv.^<><>v^>>.^>>><>><>v..^<#
#>.^>^>^.v<vv.<>.>>v<>><^vv>>^<<v^.><^^>^^^.<><><.<v<<^.^<><<^>v<v<v<v>^^<^<v<<...<<>v<v<>.^v>>^^^^<<<><v<^>.^v^.>v<v>v.>#
#<.>.^.<>^^<^v<<^^^^v..<><>^vvv<^>..v<>^vvvv<<<>v^<v.v^<<>v.<^v^>^>>vv<.<<.<^^^v^v<vv<.>^<^.v.<<<v.v^v>v^^<vv^^^>v>v^>><>#
#<v>v>^<vvv^v<^>^v>.<<^v^^>v>^v>^.<<v<vv<<v^<v<^vvv.<>.<>^vv.>^vvv<v<><v^.<^v<..><<><^v..v>^>v<>>.<<>^<^v>v.^><<^v<<.v^>>#
#<<<^<<^v^vv><><<>vv<>...<^<<<vv^^^...<><<<^vv^<vv<^<v>^<^^^^>v^>>.<^<^<>>v^><><v^v>>><v>^^<^.>><><^<v<^.>>v^>^v^v<v^^^<<#
#<>.><^v.vv><.v<v>^.>^><<^<><vv>^v<^>v<^.v^.v<>^.>^>vv>^^>>v<^><^v.>v^>^vvv^^<v<>..v^^<>..v^>v^^^<<>vv^vv>v><<v<.>><<vvv>#
#><><.^^<<<<.<<><v^<v>^>^>vv..v>^v<<v^<^^.<<>^>>.<>>^<<v.^>^^vv>^^v.^<<.>>><v^>.>>^.>>^<^v>^<>v<v.v<.<^.v>^<>v^v>.^.><^v>#
#><>>>>^<>>>v^v^v^vv.<^^.^.^>^v>>v<<^..^>><<.^<v><>v>>><<>vv.<>v.^<^^<v^vv^>v<>v><^^vv>vvv.v><v.<<<<>>>vv>v.>v>>^^v>.^<><#
#<<><><^>^v<>v^.^<.^<v^<v.>.>v^v.<^><<vv<vvv^<>^>.v>>v^><><<<v<.^v>><vv<^v<>^v>v.^<^.><.^<.v^v<^^><>^.^>v>.>^<..<<^>^vv..#
#><v>v.v<>>v<<><>>^<>vv^<<>^vvv^<>^>>v><^<v.<^<<<^><<<<<^.^v><><<><><v.vv^^v.<<<<>.<<>v^.<^.v<v>>v^<..^><v<<^^<^>^^v^>.<>#
#.<<>>>v.<>^<<^v.^<>v<><vv>.^v.^>.<v.>v<.^vvv>v^<<v<><^<v^.>vv^.<<^v^v>>vvv>.>>^>^<<<v.>>.vv>>>^v^vv^v<v<<^>>><.<>>^>v^<<#
#<<>><><>>^v>^>.<v^v..v.v^v^>.><^.><^<>^.>>v.^>vv^v><^..<>^vv<>.<<.<>v^^..>^<>v><<^>^v><<v>..>vvv<.>>v<v<vv<^^v>^v<v^v<v.#
#>vvv.><<<^<>>><<<v><>>>>^v<<.<><vvv.<<^^v.v<>^<>^v.^^>.<v>v>v^v^^<^.v^>^><v>^>>^<>>vvvv<.vv^v<^v^^^.^>^><><^vvv.>.v^<<v>#
#>vv.><>>^.^v<.>vv>>.^v^vv>^v^>>><v<<vv.><^><>.><>>><^<>v^v<>^<<<^>^>^<.><.v>><v<>v>>><vv^.>^v.>v^<>v>v^vv^<v<<^v^v<<^>^>#
#<v^vvv<><<<vv.<^v<<v^^>v^<vvv^^vvv^^>v<.<>v^>>>>^>.^><^>^^<^<^.v>>>v>^<<<v>>.v^v<v><^>>v.<^>^v^vv>>^^vv<<v<v<<vv^<^<.vv>#
#<^>v^^^^vv><>>^>v>^>v<vv<><v.v<^vv><v<^^^^^.<<><v<><^.>^^.<^v>^<v>^<<.v>>^v^^.^<.<v>.^><.>^v^^v<><v<.v<.>>><^>^vv<.^.>><#
#<>^^vvv<<v^vv<<>v>.^<>v^>.vv<vv^>.<^>v>v^>.^v<.<>^<vv^v><^v.^v>^^>v^>>><>vv<>vv>.^v><>.<^^v<<<^>^^^><>^^>^.^>vv<.<><<^>>#
#<<^^..>v>vv<v<>>v<><^<v<v^>.<>v>^^>^v<.v^.<>>.<<>>v^><<^^<>^.<v^vvv^v^<<<^v.^vv^^^<v><<<v^<<>^.<><vvv^<>v<^>.>>><>^v<>v<#
#<>>^.>^^^vv<>^>^<v.^^v><.v<^<vv>^^v><<>v<>>>>>.<^^vv^^^>.<<>v^>>.^.<v^>.>.v^vv>><>.><<^^>>v^>>>^>v<>.^^v>^>vvv^^^^.^^^.<#
#>v<vvv<^^>v^>>^^<vvvv.v.v>^<v^>>v><><<v^.<><v<^>v.<^v<>>^v<.^><^v>^^>v^<v^v>>^vv><v.^<><<v<<<v^v>vv><<^<>v^<<^...<<.<>^<#
########################################################################################################################.#
`;

const map = mapString.split('\n').filter(val => val).map(string => [...string]);

// Trim ### edges
map.shift();
map.pop();
map.forEach(line => {
    line.shift();
    line.pop();
});

const printMap = () => {
    map.forEach(line => {
       console.log(line.join('')); 
    });
    console.log('\n');
};

const printStorms = (x = -1, y = -1) => {
    const stormMap = [];
    
    map.forEach((line, lineIndex) => {
        stormMap.push(new Array(line.length).fill('.'))
    });
    
    storms.forEach(storm => {
        stormMap[storm.x][storm.y] = storm.direction; 
    });
    
    stormMap.forEach((line, lineIndex) => {
        if (x < 0 || x == lineIndex) {
            console.log(line.join('')); 
        }
    });
    console.log('\n');
};

// Set up storms array.
const storms = [];
map.forEach((line, x) => {
    line.forEach((char, y) => {
        if ('^v<>'.indexOf(map[x][y]) !== -1) {
            storms.push({
                direction: map[x][y],
                x,
                y,
            });
        }
    })
});

// Memoize storm checks to save time.
let stormChecker = [];

// Update storms.
const updateStorm = (storm) => {
    let {direction, x, y} = storm;

    if ('^' == direction) {
        x--;
    } else if ('v' == direction) {
        x++;
    } else if ('<' == direction) {
        y--;
    } else if ('>' == direction) {
        y++;
    }
    
    x %= map.length;
    y %= map[0].length;
    
    x = x >= 0 ? x : map.length + x;
    y = y >= 0 ? y : map[0].length + y;
    
    storm.x = x;
    storm.y = y;
};
const updateStorms = () => {
    storms.forEach(storm => {
       updateStorm(storm); 
    })
    
    stormChecker = [];
};

const doesStormOccupyPosition = (x, y) => {   
    const hasStorm = storms.filter(storm => {
        return storm.x == x && storm.y == y; 
    }).length;
    
    return hasStorm;
}

let stepsArray = [];

const startPosition = [-1,0];


let steps = 0;
let currentPositions = [[startPosition[0], startPosition[1], []]];
let nextPositions = [];
let endReached = false;

let i = 0;
const max = 1000;
while(!endReached && i <= max) {
    i++;
    console.log(`\nROUND ${i} ============`);
    
    // Move storms.
    updateStorms();
    //printStorms();
    //
    
    while (currentPositions.length) {
        let [x, y, history] = currentPositions.shift();

        // Check if we're at the end, and if so maybe set a new min!
        if (x == map.length - 1 && y == map[0].length - 1) {
            console.log('END REACHED!', x, y);
            endReached = true;
            break;
        }
        
//         console.log('checking curr:', x, y)

        // Try different directions
        let newPositionsToTry = [
            [x,y], // Current position (wait)
            [x - 1, y], // Up
            [x + 1,y], // Down
            [x, y - 1], // Left
            [x, y + 1], // Right
        ];
        
        const alreadyInQueue = (x,y) => nextPositions.filter(item => item[0] == x && item[1] == y).length > 0;

        newPositionsToTry.forEach(([newX, newY]) => {
            
            // Only proceed if the position exists.
            if (
                map[newX] && map[newX][newY] // Exists
                && !doesStormOccupyPosition(newX, newY) // Isn't storm
                && !alreadyInQueue(newX, newY) // Not already queued
            ) {
                let newHistory = JSON.parse(JSON.stringify(history));
                newHistory.push([newX, newY]);
                nextPositions.push([newX, newY, newHistory]);
            }

        });
        
        // Always push current position since we can always wait.
        if (!alreadyInQueue(x, y)) {
            let newHistory = JSON.parse(JSON.stringify(history));
            newHistory.push([x, y]);
            nextPositions.push([x, y, newHistory]);
        }
    }
    
    if (i == max) {
        nextPositions.sort((a, b) => {
            if (a[0] > b[0]) return 1;
            if (a[0] < b[0]) return -1;   
            if (a[1] > b[1]) return 1;
            if (a[1] < b[1]) return -1;
        });
        console.log('Valid next positions:', nextPositions.pop())
    }
    
    currentPositions = JSON.parse(JSON.stringify(nextPositions));
    nextPositions = [];
}

const matching = currentPositions.filter(a => a[0] == map.length - 1 && a[1] == map[0].length - 1 )[0];
console.log(matching)
matching[2].forEach((item, index) => console.log(index + 1, item));