--- Day 18: Lava Lagoon ---

December 18

Listening to: Jungle in Gaming Mix


This seems pretty simple. Use the directions provided to dig out a trench (in the form of a 2d array), and simply expand the array as needed. After, use a polygon filling algorithm to get the rest.

Hmm. This input also has hex color values, but doesn't actually seem to use it. Yet.

auto parts = split(line, " ");

int distance = stoi(parts[1]);
for (int i = 0; i < distance; i++)
{
    switch (parts[0][0])
    {
        case 'U': 
            x--;
            if (x < 0)
            {
                field.insert(field.begin(), string(field[0].size(), '.'));
            }
            break;

        case 'D': // Down resize logic...
        case 'L': // Left resize logic...
        case 'R': // Right resize logic...
    }

    field[x][y] = '#';
}

That gets the outside of the field in place...

Now for the next part, it looks really previous to a previous day's puzzle, so I might just steal what to do from that:

  1. Add an extra set of empty space around the field
  2. Flood-fill the field with empty space ( )
  3. Dig out all interior spaces (remaining .)
// Flood fill field
queue<pair<int, int>> queue;
queue.push(pair<int, int>(0, 0));
while (!queue.empty())
{
    auto space = queue.front(); queue.pop();

    if (space.first < 0 || space.first >= field.size() || space.second < 0 || space.second >= field[0].size()) continue;
    if (field[space.first][space.second] != '.') continue;
    field[space.first][space.second] = ' ';

    queue.push(pair<int, int>(space.first+1, space.second));
    queue.push(pair<int, int>(space.first-1, space.second));
    queue.push(pair<int, int>(space.first, space.second+1));
    queue.push(pair<int, int>(space.first, space.second-1));
}  

for (int i = 0; i < field.size(); i++)
    for (int j = 0; j < field[i].size(); j++)
        if (field[i][j] == '.')
            field[i][j] = '#';

AUGH I should have seen something like this coming. There's no way simply having a flood-fill type algorithm will work for this... I'll have to completely rework this. Basically, instead of each line being something like 5 units, it's around 50,000 units! These examples really have a way of guiding you towards a really inefficient solution.

It turns out that... this is just a polygon. One with a LOT of edges, but still just a polygon. I can easily figure out the coordinates of all of this (even more trivially than putting it on a grid), and from there there's a few algorithms for figuring out the area. This might be simpler than my part 1 solution was...

uint64_t area = 0;
int j = points.size() - 1;
for (int i = 0; i < points.size(); i++)
{
    // 2x2 matrix determinant
    area += (points[i].first * points[j].second) - (points[j].first * points[i].second);
    j = i;
}
if (area < 0) area *= -1;

// Pick's Formula (to add trench area in)
area = (area / 2) + (trench / 2) + 1;

Time taken: 1 hour 30 minutes

My solutions for today's puzzles