--- Day 12: Fence Pricing ---

December 12

Listening to: N.U.D.E. | Liquid DnB / Jungle Mix


There's been more than enough 2d grids this year that I'm just creating a bunch of utility functions to deal with it.

public static List<List<T>> Duplicate2DList<T>(List<List<T>> list);
public static void PadGrid<T>(List<List<T>> space, T padValue);
public static void Print2D<T>(IEnumerable<IEnumerable<T>> grid);

I'm sure it'll make sens to start doing some other utilities as they come along, though I'm not sure I'll write about all of them.


Here it didn't seem too bad - 2d depth-first search from any given point. I did a little extra work to pad the grid initially, as well as clear the plot I checked afterwards, to make sure that I didn't double-count anything. Maybe inefficient, but it worked plenty fast on the input.

private long GetFenceCost(List<List<char>> garden, int row, int col)
{
    char crop = garden[row][col];
    if (crop == '.') return 0;

    long area = 0, perimeter = 0;

    var toCheck = new Queue<(int, int)>();
    var visited = new HashSet<(int, int)>();
    toCheck.Enqueue((row, col));

    while (toCheck.Any())
    {
        var (x, y) = toCheck.Dequeue();
        if (garden[x][y] != crop || visited.Contains((x, y))) continue;

        visited.Add((x, y));
        area++;

        if (garden[x - 1][y] != crop) perimeter++;
        if (garden[x + 1][y] != crop) perimeter++;
        if (garden[x][y + 1] != crop) perimeter++;
        if (garden[x][y - 1] != crop) perimeter++;

        toCheck.Enqueue((x + 1, y));
        toCheck.Enqueue((x - 1, y));
        toCheck.Enqueue((x, y + 1));
        toCheck.Enqueue((x, y - 1));
    }

    // Clear area
    toCheck.Enqueue((row, col));

    while (toCheck.Any())
    {
        var (x, y) = toCheck.Dequeue();
        if (garden[x][y] != crop) continue;

        garden[x][y] = '.';

        if (garden[x - 1][y] == crop) toCheck.Enqueue((x - 1, y));
        if (garden[x + 1][y] == crop) toCheck.Enqueue((x + 1, y));
        if (garden[x][y + 1] == crop) toCheck.Enqueue((x, y + 1));
        if (garden[x][y - 1] == crop) toCheck.Enqueue((x, y - 1));
    }

    return area * perimeter;
}

Okay, I will admit, at first glance, I don't even know how to start figuring out how many sides something has. And this part 2 requires it.

...

I love my partner.

I breifly described the problem to them, and what they pointed out was that I should be counting the corners, not the sides. The number of corners should always equal the number of sides, and can be determined on an individual cell's level!

For example:

123
4.5
678

An upper-left outer corner is present if 2 and 4 don't match the middle, and an upper-left inner corner is present if 2 and 4 match the middle, but 1 doesn't! The same logic applies to all four diagonal directions.

I just added the following after my peremeter check in the main loop:

// Outer corners
if (garden[x - 1][y] != crop && garden[x][y - 1] != crop) corners++;
if (garden[x - 1][y] != crop && garden[x][y + 1] != crop) corners++;
if (garden[x + 1][y] != crop && garden[x][y - 1] != crop) corners++;
if (garden[x + 1][y] != crop && garden[x][y + 1] != crop) corners++;

// Inner corners
if (garden[x - 1][y] == crop && garden[x][y - 1] == crop && garden[x - 1][y - 1] != crop) corners++;
if (garden[x - 1][y] == crop && garden[x][y + 1] == crop && garden[x - 1][y + 1] != crop) corners++;
if (garden[x + 1][y] == crop && garden[x][y - 1] == crop && garden[x + 1][y - 1] != crop) corners++;
if (garden[x + 1][y] == crop && garden[x][y + 1] == crop && garden[x + 1][y + 1] != crop) corners++;

I made another small change, this time just for the profiling I added. In this solution, since it made since to do both parts in one pass, I modified the parsing code to be profiled as well, seeing as all the actual solution functions are just reading and summing the results of the actual work done within the parsing code.

+----------------+
|  Results       |
+---+------+-----+
| P |      | 6ms |
| 1 | 1930 | 0ms |
| 2 | 1206 | 0ms |
+----------------+

Time taken: 1 Hour

My solutions for today's puzzles