Advent of Code is a yearly puzzle that runs through December where each day a new puzzle is released that gets progressively harder. The goal is to take the text input and create an algorithm in any language to solve the puzzle.

For this year I decided to make my solutions into interactive widgets on the web.

Spoilers

WARNING - Below is a spoiler. If you want to figure it out yourself have a look at the puzzle on Advent of Code and come back after you have solved it.

The Puzzle

Puzzle 4 gives a 2d grid of characters @ and . representing a warehourse floor plan. The idea is to count how many parts of the floor are accessible based on one rule - looking at the up to 8 adjacent cells, if 3 or fewer of them are @ then the cell is accessible.

.@..@      ✗✓✗✗✓
@.@.@      ✓✗✗✗✓
@@@@@  ->  ✓✗✓✗✓
@...@      ✗✗✗✗✓
@@..@      ✓✓✗✗✓

This sort of problem reminds me of the game of life, where each cell’s state is determined by its neighbours.

Solution

Parsing the input

To parse this input first I want to think about the data structure. In this case aI am thinking a simple 2d array of booleans will work well, where true represents an @ and false a .. But for my use case in order to render the grid later I will be parsing to an object array with the coordinates and some other metadata included.

Honestly it is likely that no parsing phase is even required for this, but I find it easier to keep things separated incase I need to extend for part 2.

function parseInputToBooleanArray(input) {
    return input.split("\n")
        .map(line => line.split("").map(char => char === "@"));
}

function parseToObjectArray(input) {
    return input.split("\n")
        .map((line, x) => line.split("").map((char, y) => ({
            x,
            y,
            value: char,
            occupied: char === "@"
        })));
}

Processing the grid

Processing the grid is just a matter of iterating over each cell and checking the neighbours. Each neighbour is at a relative coordinate to the current cell, defined as:

const neighbours = [
    [-1, -1], [0, -1], [1, -1],
    [-1,  0],          [1,  0],
    [-1,  1], [0,  1], [1,  1],
];

The only real trick to processing this is handling the edges, where a neighbour won’t exist in many of the cases. A missing neighbour counts as a . so it is safe to default to that.

function countAccessibleCells(grid) {
    let count = 0;

    // Loop through all cells
    for (let y = 0; y < grid.length; y++) {
        for (let x = 0; x < grid[y].length; x++) {

            // Count occupied neighbours
            let occupiedCount = 0;
            for (const [dx, dy] of neighbours) {
                const neighbour = grid[x + dx]?.[y + dy]?.value === "@" ?? false;

                if (neighbour) {
                    occupiedCount++;
                }
            }

            // If 3 or fewer occupied neighbours, cell is considered accessible
            if (occupiedCount <= 3) {
                count++;
            }
        }
    }

    return count;
}

There is a bit much nesting here for my liking, but for now it will do as the core logic is pretty simple.

Showing the results

This solution was used to make the interactive widget below. You can change the inputs to anything you like.

Run

Part 2

The second part of this puzzle requires the same process to occur iteratively until no more changes occur. When an accessible cell is found, it then becomes an empty cell . for the next iteration.

Run

---

Want to read more? Check out more posts below!

---