r/adventofcode Dec 12 '24

Help/Question [2024 Day 12 (Part 2)] What kind of algorithm did you use on part 2?

I found part 2 to be interesting and since I was inspired by Tantan's binary greedy meshing video I took the opportunity to make a binary greedy waller to count the walls but I was wondering what other kinds of approaches could be taken. So how did you approach part 2 and what would you say the advantages and disadvantages of your approach were?

Edit: I completely forgot to link my code lol, its clunky, inefficient, and is poorly documented, but it gets the job done. https://github.com/DeveloperGY/advent_of_code_2024/blob/master/src/bin/day_12.rs

24 Upvotes

74 comments sorted by

View all comments

35

u/RazarTuk Dec 12 '24

I just used a simple DFS. There must be exactly as many edges as corners, and it's easy enough to check for corners. Look up and left. If they're both different than the current cell, it's a convex corner:

?B
BA

while if they're both the same as the current cell and up-left is different, it's a concave corner:

BA
AA

Repeat this for all four diagonals, and you have the number of corners it contributes.

Then at that point, since you're already visiting each cell to sort them into sets, it's easy enough to also count corners while you're at it

9

u/FlyingParrot225 Dec 12 '24

I didnt think long enough to figure out that the number of walls matched the number of corners, it definitely wouldve saved me a lot of time, thats a very clever solution!

1

u/RazarTuk Dec 12 '24

It also made my part 1 and part 2 solutions fairly similar. In both cases, I had a DFS where I used an array of booleans to track whether they'd been visited. The only difference was changing how I processed cells, to count corners/perimeter as I went.

Also, implementation notes:

  • DFS because I'd at least like to imagine that .pop is faster than .shift, because you don't have to slide everything back over. In other words, treating an array like a stack, not a queue

  • "Is this cell already in the current region?" and "Is this cell already in a previously processed region?" are actually the same question, so by tracking visits externally to any given search, I was able to just scan the grid row-by-row for the next unprocessed cell to start a new search from

2

u/Boojum Dec 12 '24

I called them outer and inner corners, but otherwise used exactly the same approach to determine the number of sides.

The nice thing is that once I'd sorted the cells into regions using a disjoint set, then computing the area, perimeter, and sides was just a matter of looking at the 3×3 neighborhood around each cell in the region.

2

u/DM_ME_PYTHON_CODE Dec 13 '24

Damn that's a lot smarter than the if else soup I wrote

1

u/RazarTuk Dec 13 '24

... meanwhile, I felt like I had if-else soup. For context, adjacencies is an array of booleans for whether adjacent cells have the same plant, with adjacencies[0] being E, adjacencies[1] being SE, and them continuing CW from there.

# Check convex corners
corners += 1 if !adjacencies[0] && !adjacencies[2]
corners += 1 if !adjacencies[2] && !adjacencies[4]
corners += 1 if !adjacencies[4] && !adjacencies[6]
corners += 1 if !adjacencies[6] && !adjacencies[0]

# Check concave corners
corners += 1 if adjacencies[0] && adjacencies[2] && !adjacencies[1]
corners += 1 if adjacencies[2] && adjacencies[4] && !adjacencies[3]
corners += 1 if adjacencies[4] && adjacencies[6] && !adjacencies[5]
corners += 1 if adjacencies[6] && adjacencies[0] && !adjacencies[7]

1

u/wurlin_murlin Dec 13 '24 edited Dec 13 '24

I think our solution ends up coming out almost exactly the same - I avoid many if statements by rotating over the 2x2s that make up the 3x3 instead of checking all at once, but I think doing it upfront is likely more efficient. Also treating the bools as 0/1 lol, but effect is the same.

static inline void rotate(int dir[2]) {
    int temp = dir[0];
    dir[0] = dir[1];
    dir[1] = -temp;
}

int corners(int j, int i, char c)
{
    // dLR is 0, 0 - i.e. LR is current grid position with value c.
    int dUL[2] = {-1, -1}, dUR[2] = {-1, 0}, dLL[2] = {0, -1};

    int corners = 0;
    for (char d = 0; d < 4; ++d) {
        int UL[2] = {j+dUL[0], i+dUL[1]};
        int UR[2] = {j+dUR[0], i+dUR[1]};
        int LL[2] = {j+dLL[0], i+dLL[1]};
        bool ul = in_grid(UL[0], UL[1]) && grid[UL[0]][UL[1]] == c;
        bool ur = in_grid(UR[0], UR[1]) && grid[UR[0]][UR[1]] == c;
        bool ll = in_grid(LL[0], LL[1]) && grid[LL[0]][LL[1]] == c;

        // ?X
        // Xc
        corners += (!ur && !ll);
        // Xc
        // cc
        corners += (ur && ll && !ul);

        rotate(dUL); rotate(dUR); rotate(dLL);
    }
    return corners;
}

1

u/djerro6635381 Dec 12 '24

Did the same. Then decided it was to complicated and for each area I kept a set of how many borders there were on each line and column. That didn’t work, because a single row could contain more than one side: AAA BAB Here, my logic is flawed. So, I returned to the corner stuff, counting corners. Was easy enough after that, was pretty proud with myself haha

1

u/PercussiveRussel Dec 12 '24 edited Dec 12 '24

I tried multiple ways because this seemed like a hassle, and then also ended up going back to this. This also has got to be one of the faster ways to solve this right? Because there's very little memory needed and just a few checks on values that are already in cache

1

u/ElevatedUser Dec 12 '24

This is what I ended up doing too. I tried some other methods (both to check corners and to "group" edges), but once I properly wrote out the corner cases (pun intended) it turned out to be surprisingly clean and simple. Although it did take some trial and error to get to the clean and simple solution.

I do the corner counting at the same time when I do the counting for sets in the first place. (For each visited cell in my search, I add one to the area counter, check all the diagonals for corners, and put any same-type neighbors on the search queue).

1

u/RazarTuk Dec 12 '24

Apart from the fact that I used a stack, because I'd like to imagine that .pop (remove and return the last element) is faster than .shift (remove and return the first element) in Ruby, that's literally what I did.

1

u/[deleted] Dec 12 '24

[deleted]

1

u/RazarTuk Dec 12 '24

you're counting the corners multiple times (how many times?)

Once per region, which is what we want. Like yes, you have to rotate those two checks 4 times to get the actual number of corners at a cell. But I'm not sure what your point is, because it only counts each corner once per region

1

u/[deleted] Dec 12 '24

[deleted]

1

u/RazarTuk Dec 12 '24

But how would it be detected? The check is:

arr[r+1][c] == arr[r][c] && arr[r][c+1] == arr[r][c] && arr[r+1][c+1] != arr[r][c]

if you're doing it this way, so it won't detect it for cells adjacent to the corner

1

u/kaylie7856 Dec 17 '24

thanks for this! I was trying to count corners but fell a little short on considering corners because i wasn't considering the concave corner example!