I want to punch this gardener

Advent of Code 2024: Day 12

Easily the most frustrating puzzle I've tried so far, this was 😩

Essentially we have a gardener who didn't like the idea of boring, rectangular patches of land for his farm; instead he decided to plotting all sorts of weird shapes, concave and convex, and with loads of angles. Why do we care, you may ask? Well, because our task for today is to calculate all the plots' areas and perimeters.

AAAA
BBCD
BBCC
EEEC

Excluding the initial part where I thought I could be clever and simply go from cell to cell, calculating the perimeters based on adjacent cells equal to the current one and do + 1 for the area, thus avoiding having to do a flooding algorithm - except then realising that plots can have the same ids, and that for example the perimeter (8) and area (4) of a square of side 2 are quite different from the perimeters (4 each) and areas (1 each) of four squares of side 1, so my cleverness went down the toilet very quickly 🙄 - part 1 was fairly straightforward.

Here's the simple flood-fill function I created for the purpose: starting from a given coordinate, it uses a stack to explore all connected cells with the same fieldId. Then it keeps track of visited cells to calculate the total area, while incrementing the perimeter whenever a neighboring cell doesn't match the field or is out of bounds.

function floodFill(start: Coord) {
    const stack: Coord[] = [start];
    const fieldId = grid.get(start.serialize());
    let area = 0;
    let perimeter = 0;
    const sideSegments: Map<Cardinal, string[]> = new Map();

    while (stack.length > 0) {
        const current = stack.pop()!;
        const currentStr = current.serialize();
        if (visited.has(currentStr))
            continue;

        visited.add(currentStr);
        area++;

        for (const neighbor of getNeighborCoords(current)) {
            if (grid.get(neighbor) === fieldId) {
                if (!visited.has(neighbor.serialize())) {
                    stack.push(neighbor);
                }
            } else {
                perimeter++;
            }
        }
    }

So, we made our gardener happy so we can go home and forget about crazily-shaped plots of land, right?

Well, not exactly, because the elves have figured out a way to save money on the meters of fence: the perimeter no longer counts - the number of sides of a plot of land does. A simple region like C below has a perimeter of 10 and 8 total sides. Good luck with that 😛

+-+-+-+-+
|A A A A|
+-+-+-+-+     +-+
              |D|
+-+-+   +-+   +-+
|B B|   |C|
+   +   + +-+
|B B|   |C C|
+-+-+   +-+ +
          |C|
+-+-+-+   +-+
|E E E|
+-+-+-+

To be fair, identifying a single cell's side was the easiest part: I just expanded my getNeighborCoords to be getNeighborCoordsWithDirections:

export function getNeighborCoordsWithDirections(coord: Coord): [Cardinal, Coord][] {
    return [
        [Cardinal.NORTH, new Coord(coord.x, coord.y - 1)],
        [Cardinal.EAST, new Coord(coord.x + 1, coord.y)],
        [Cardinal.SOUTH, new Coord(coord.x, coord.y + 1)],
        [Cardinal.WEST, new Coord(coord.x - 1, coord.y)],
    ];
}

The directions are useful because they help keep track of a cell's boundaries, i.e. how many sides it has. Above, for example:

The left-most cell of the A plot has three sides - North, West, South.
The two cells on its right have two - North and South.
Similarly, the right-most cell faces North, East and South.

There's just one small problem to solve: for example, the four North sides of the A region obviously form a single side for the whole rectangle; so in order to compute the total sides of the region, we need to "merge" these 4 North sides into one.

Again, I'm not going to show the full code because I'm not too proud of that (feel free to check it out https://github.com/martapanc/Advent-of-Code/blob/master/2024/src/2024/day12/day12.ts, though), but here's my idea behind it:

for each of the directions, we have groups of cells sharing either the X (for West-East sides) or the Y (for North-South sides) axis: for instance, the coordinates of A's North-facing side would be {0,0} {1,0} {2,0} {3,0})
The X (or Y) for the cells with the same direction is not always the same: for example C has two North-facing sides with different Y - so counting unique Xs or Ys for the same direction is a start.
There could also be cases where counting the unique X / Y values is not enough.

For example for a region like this:

....CC..
....CCC.
...CC...
.CCC|...
..C.....
...C|...
...C|...

we have two distinct East-facing sides sharing the same X. The solution I found for these cases was to check if, for cells with the same X, their Ys are consecutive or not: if so, we found one single side; otherwise, we have as many sides as there are "holes" on the Y axis.

Well, after a few hours of debugging and finding ways to solve special cases, I've proudly managed to achieve the 2nd star 💫

I want to punch this gardener

Categories

Tags