Advent Of Code 2021

It's Day 11, time to deal with flashing octopuses. We have found a neatly organized gang of octopuses, they're forming a grid of 10x10. Each octopus has an energy level, which is our input. It looks like this:

The energy levels are a number between 0 and 9. The octopus lifecycle is made up of steps. For each step, this happens:

First, the energy level of each octopus increases by 1.
Then, any octopus with an energy level greater than 9 flashes. This increases the energy level of all adjacent octopuses by 1, including octopuses that are diagonally adjacent. If this causes an octopus to have an energy level greater than 9, it also flashes. This process continues as long as new octopuses keep having their energy level increased beyond 9. (An octopus can only flash at most once per step.)
Finally, any octopus that flashed during this step has its energy level set to 0, as it used all of its energy to flash.

With this in mind, we are going to calculate the total number of flashes that has occured after 100 steps. We'll be using an old, not so dear, friend called recursion here. I always confuse myself a little when dealing with recursion, but it does solve this problem.

We start of by modelling our grid like this:

var input = File.ReadAllLines("input.txt");
var octopuses = new Dictionary<(int, int), int>();

var maxCol = 0;
var rowCount = 0;
foreach (var row in input)
{
    var colCount = 0;
    foreach (var o in row)
    {
        octopuses.Add((rowCount, colCount), o.ToInt());
        colCount++;
    }
    rowCount++;
    maxCol = colCount - 1;
}

var maxRow = rowCount - 1;

Each octopus is represented by a point in the grid, and an energy level.

For Part 1, we need to go through each step, check if any octopuses are flashing. If they are, keep track of those that has flashed and check if they have any neighbours that are also flashing as a result of the first octopus flash. Finally, reset all that has flashed to 0 energy, and count the number of flashes per step.

private static void Part1(Dictionary<(int, int), int> octopuses, int maxRow, int maxCol)
{
    var steps = 100;
    var totalFlashCount = 0;


    for (int i = 0; i < steps; i++)
    {
        var hasFlashed = new HashSet<(int, int)>();

        octopuses = octopuses.ToDictionary(o => o.Key, o => o.Value + 1);

        var flashing = octopuses.Where(x => x.Value > 9).ToDictionary(x => x.Key, x => x.Value);
        hasFlashed.UnionWith(flashing.Select(x => x.Key));

        foreach (var octo in flashing)
        {
            Flash(octopuses, octo.Key, maxRow, maxCol, hasFlashed);
        }

        foreach (var point in hasFlashed)
        {
            octopuses[point] = 0;
        }

        totalFlashCount += hasFlashed.Count();
    }

    Console.WriteLine($"Part 1: {totalFlashCount}");
}

Our recursive Flash() method looks like this:

private static void Flash(Dictionary<(int, int), int> allOctos, (int, int) flashingOctoPoint, int maxRow, int maxCol, HashSet<(int, int)> hasFlashed)
{
    var adjacent = GetAdjacentPoints(flashingOctoPoint, maxRow, maxCol);

    foreach (var point in adjacent)
    {
        allOctos[point] = allOctos[point] + 1;
        if (allOctos[point] > 9 && !hasFlashed.Contains(point))
        {
            hasFlashed.Add(point);
            Flash(allOctos, point, maxRow, maxCol, hasFlashed);
        }
    }
}

Here we find the adjacent octopuses, raise their energy level by 1, if they are now over 9 and hasn't already flashed, they will flash and we'll have to check it's adjacent octopuses, and so on..

To get the adjacent points, we can simple create a HashSet of all the adjacent points, and then remove those that are out of bounds before we return it.

private static HashSet<(int, int)> GetAdjacentPoints((int, int) sourcePoint, int maxRow, int maxCol)
{
    var adjacent = new HashSet<(int, int)>
    {
        (sourcePoint.Item1 -1, sourcePoint.Item2 -1),
        (sourcePoint.Item1 -1, sourcePoint.Item2),
        (sourcePoint.Item1 -1, sourcePoint.Item2 +1),
        (sourcePoint.Item1, sourcePoint.Item2 +1),
        (sourcePoint.Item1 +1, sourcePoint.Item2 +1),
        (sourcePoint.Item1 +1, sourcePoint.Item2),
        (sourcePoint.Item1+1, sourcePoint.Item2 -1),
        (sourcePoint.Item1, sourcePoint.Item2 -1),
    };

    adjacent.RemoveWhere(x => x.Item1 < 0 || x.Item2 < 0 || x.Item1 > maxRow || x.Item2 > maxCol);
    return adjacent;
}

Part 2 is really similar to Part 1, but instead of finding out what has happend during 100 steps we are going to find out at which step all the octopuses are flashing at the same time, for the first time.

It is basically the same solution, but instead of looping through 100 steps we keep looping until we're at a step where the amount of octopuses that flashed during a step is equal to the total amount of octopuses.

private static void Part2(Dictionary<(int, int), int> octopuses, int maxRow, int maxCol)
{
    var lastStep = 0;
    var stepFlashCount = 0;

    while(stepFlashCount < octopuses.Count)
    {
        lastStep++;
        var hasFlashed = new HashSet<(int, int)>();

        octopuses = octopuses.ToDictionary(o => o.Key, o => o.Value + 1);

        var flashing = octopuses.Where(x => x.Value > 9).ToDictionary(x => x.Key, x => x.Value);
        hasFlashed.UnionWith(flashing.Select(x => x.Key));

        foreach (var octo in flashing)
        {
            Flash(octopuses, octo.Key, maxRow, maxCol, hasFlashed);
        }

        foreach (var point in hasFlashed)
        {
            octopuses[point] = 0;
        }

        stepFlashCount = hasFlashed.Count();
    }

    Console.WriteLine($"Part 2: {lastStep}");
}

Markestedt

Markestedt

Advent Of Code 2021 - Day 11