--- Day 16: Energize ---

December 16

Listening to: Low Poly Breaks [DISC. 4] // Nostalgic Video Game Drum and Bass Mix to chill out to


This seems like an interesting sort of breadth-first search. Basically, keep queuing up tiles/directions to check out, splitting on splitters, until no more beams move. It would probably make more sense to track the results seprately rather than mutating the input.

struct BeamStep { int x, y; char dir; };

vector<string> room;
vector<vector<bool>> energized;
queue<BeamStep> queue;

while (!queue.empty())
{
    auto step = queue.front(); queue.pop();

    // Ignore if it would go off of the grid
    if (step.x < 0 || step.x >= room.size() || step.y < 0 || step.y >= room[0].size()) continue;
    energized[step.x][step.y] = true;

    int nextX = step.x, nextY = step.y;
    char nextDir = step.dir;
    switch (room[step.x][step.y])
    {
        case '.':
            switch (step.dir)
            {
                case 'u': nextX -= 1; break;
                case 'd': nextX += 1; break;
                case 'l': nextY -= 1; break;
                case 'r': nextY += 1; break;
            }
            queue.push(BeamStep{ nextX, nextY, step.dir });
            continue;

        case '\\': // reflect logic
        case '/': // reflect logic
        case '-': // split logic
        case '|': // split logic
    }
}

This works... but it never finishes on the example input. Running it for a bit while visualizing it, I'm realizing that it has an infinite loops. It's just going around in a big circle around the room!

Simply marking which tiles have been visited isn't enough. I need to mark which direction the beam was facing so I don't repeat it.

struct Dir
{
    bool u, d, l, r;
    bool energized() { return u || d || l || r; }
};

vector<vector<Dir>> energized;

// ...

switch (step.dir)
{
    case 'u': if (energized[step.x][step.y].u) continue; energized[step.x][step.y].u = true; break;
    case 'd': if (energized[step.x][step.y].d) continue; energized[step.x][step.y].d = true; break;
    case 'l': if (energized[step.x][step.y].l) continue; energized[step.x][step.y].l = true; break;
    case 'r': if (energized[step.x][step.y].r) continue; energized[step.x][step.y].r = true; break;
}

I know, kinda ugly to one-line it like that. But it helps to reduce copy-paste errors by having it all aligned like that. And this works to get rid of the loops!


This makes sense; check every direction you can start from, and get the greatest output of it all. Not a big deal, just run this again for every edge tile. Just pop the main logic of this into a function, run it for all of the edge tiles, and return the greatest result.

int maxEnergized = 0;

// Top & Bottom
for (int i = 0; i < room[0].size(); i++)
{
   maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{0, i, 'd'}));
   maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{(int)room.size()-1, i, 'u'}));
}

// Left & Right
for (int i = 0; i < room.size(); i++)
{
   maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{i, 0, 'r'}));
   maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{i, (int)room[0].size()-1, 'r'}));
}

Time taken: 1 hour

My solutions for today's puzzles