The Matrix strikes back, I guess

A bit of a breather, after the challenging tasks of the past couple of days! ☺️

On day 2 I said that the task's input felt like a representation of the Matrix - I found this to be even truer for today's task, lol.

We start with a list of pairs that we're told represent an X,Y coordinate:

5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1

Starting from the top, each coordinate is the position of a byte that falls into the memory space, making it corrupted - so for example after the first 12 falling bytes we have a grid like this:

...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....

The task for part 1 is to simulate the fall of the first kilobyte, that is the first 1024 bytes, onto the memory space. Then we need to find the best path from the top-left corner to the bottom-right corner avoiding all the bytes.

SO.#OOO
.O#OO#O
.OOO#OO
...#OO#
..#OO#.
.#.O#..
#.#OOOE

Nothing too complicated for now.

We simply need to read the first 1024 lines of the input and parse the coordinates to determine where the # "obstacles" are placed.

const grid: Grid = new Map<string, string>();
for (let y = 0; y < side; y++) {
    for (let x = 0; x < side; x++) {
        const coord = `${x},${y}`;
        if (lines.slice(0, firstCount).some((l) => l === coord)) {
            grid.set(`{${coord}}`, '#');
        } else {
            grid.set(`{${coord}}`, '.');
        }
    }
}

We can then figure the best path out via a classical exploration algorithm using BFS:

function findPath(grid: Grid, end: Coord, side: number, firstCount: number) {
    let currentPos = new Coord(0, 0);

    const queue = new PriorityQueue<State>((a, b) => a.length - b.length);
    queue.enqueue({ position: currentPos.serialize(), length: 0 });
    let visited = new Set<string>();

    while (queue.size() > 0) {
        const { position, length } = queue.dequeue()!;
        const curr = Coord.deserialize(position);

        if (curr.equals(end)) {
            return length;
        }

        if (visited.has(position)) continue;
        visited.add(position);

        for (let n of getNeighborCoords(curr)) {
            const neighbor = n.serialize();
            if (grid.get(neighbor) === '.') {
                queue.enqueue({ position: neighbor, length: length + 1 });
            }
        }
    }

    return -1;
}

Moving to part 2, it is a matter of using the remaining part of the input - of course, when has anyone ever seen an AoC task where part of the input is ignored until the end? 🙄

The bytes keep falling onto our memory grid, and we're told there's a moment when all the possible paths to the end get blocked: our goal is to find the first coordinates of such byte, effectively making the end unreachable.

I could bet there is a more efficient way to achieve this, but I decided not to try and be too smart - after all my function for part 1 was already pretty fast (~90ms). My idea was simply to keep adding bytes to the grid and call the pathfinding function, until it returned -1 meaning that a path could not be found.

function findFirstBlockingByte(
    lines: string[],
    end: Coord,
    side: number,
    firstCount: number
) {
    let count = firstCount + 1; // Starting from 1024 + 1
    let grid: Grid = new Map<string, string>();

    while (count < lines.length) {
        for (let y = 0; y < side; y++) {
            for (let x = 0; x < side; x++) {
                const coord = `${x},${y}`;
                if (lines.slice(0, count).some((l) => l === coord)) {
                    // Introducing a new byte to the grid with each iteration
                    grid.set(`{${coord}}`, '#');
                } else {
                    grid.set(`{${coord}}`, '.');
                }
            }
        }

        const path = findPath(lines, end, side, count); // Use the function from part 1 to find a path, if any
        if (path === -1) {
            return lines[count - 1]; // If path not found, return the coordinates of the byte that caused the blockage
        }
        count++;
    }
}