Advent of Code 2021

This was a tricky one, for me. Day 9 of Advent of Code is probably the one that I've struggled with the most, this far. Especially Part 2, which we'll get to later.

Part 1

For Part 1, we need to find the different low points in a heightmap, with 0 being the lowest possible value, and 9 being the highest. For example, the input can look like this:

We need to find the points that are lower than all of its adjacent points. Adjacent in this case is limited to horizontal and vertical, so no diagonal neighbours counts here. In the example above, there are 4 low points as illustrated below.

#1#######0
##########
##5#######
##########
######5###

We start by getting our input and transforming it into a format we can use:

var input = await File.ReadAllLinesAsync("input.txt");
var points = new Dictionary<(int Row, int Col), int>();

var rowNumber = 0;
foreach (var row in input)
{
    var colNumber = 0;
    foreach (var number in row.ToList())
    {
        points.Add((rowNumber, colNumber), number.ToInt());
        colNumber++;
    }

    rowNumber++;
}

var maxRow = points.Keys.Max(p => p.Row);
var maxCol = points.Keys.Max(p => p.Col);

I create a Dictionary with a tuple containing Row and Column number as key and with the height value as value. I also store the max Row and Column numbers for future use. This will be used in Part 2 aswell.

To answer Part 1 we need to find all the low points, calculate their individual risk level and sum those risk levels. The risk level of a low point is the low points height + 1.

My solution relies on a bunch of extension- and helpermethods. In the end, we will be able to do this:

var lowPoints = points.Where(point => point.GetAdjacentPoints(points, maxCol, maxRow).IsLowPoint(point)).ToList();
var answerPart1 = lowPoints.Select(point => point.Value + 1).Sum();

That looks simple, but all the magic is happening in GetAdjacentPoints() and IsLowPoint(). Let's take a look at those methods:

public static Dictionary<(int Row, int Col), int> GetAdjacentPoints(
    this KeyValuePair<(int Row, int Col), int> point, Dictionary<(int Row, int Col), int> allPoints, int maxCol,
    int maxRow)
{
    var adjacentPoints = new Dictionary<(int, int), int>();
    var directionsToAdd = new List<Directions>();

    if (point.Key.Row > 0)
    {
        directionsToAdd.Add(Directions.Up);
    }

    if (point.Key.Row < maxRow)
    {
        directionsToAdd.Add(Directions.Down);
    }

    if (point.Key.Col > 0)
    {
        directionsToAdd.Add(Directions.Left);
    }

    if (point.Key.Col < maxCol)
    {
        directionsToAdd.Add(Directions.Right);
    }

    foreach (var direction in directionsToAdd)
    {
        var key = GetAdjacentKey(point.Key, direction);
        adjacentPoints.AddIfExistsIn(allPoints, key);
    }

    return adjacentPoints;
}

In short, we take a source point, a collection of all possible points, some boundary values and return the points that are valid adjacent points to the source point. Here we have two more helper methods, GetAdjacentKey() and AddIfExistsIn().

private static (int, int) GetAdjacentKey((int Row, int Col) source, Directions direction)
{
    switch (direction)
    {
        case Directions.Up:
            return (source.Row - 1, source.Col);
        case Directions.Down:
            return (source.Row + 1, source.Col);
        case Directions.Right:
            return (source.Row, source.Col + 1);
        case Directions.Left:
            return (source.Row, source.Col - 1);
        default:
            throw new ArgumentOutOfRangeException(nameof(direction), direction, null);
    }
}

private static void AddIfExistsIn(this Dictionary<(int Row, int Col), int> dic, Dictionary<(int Row, int Col), int> source,
    (int Row, int Col) key)
{
    if (source.TryGetValue(key, out var val))
    {
        dic.Add(key, val);
    }
}

They are not very complicated, and are just there to make the code easier to read and understand. They're there to make it easier to get the key of the potential adjacent point, and to make sure it is a valid point.

So now we have our adjacent points, let's find out if our point is the low point:

public static bool IsLowPoint(this Dictionary<(int Row, int Col), int> d, KeyValuePair<(int Row, int Col),
    int> point)
{
    if (point.Value == 9)
    {
        return false;
    }

    return d.All(ap => ap.Value > point.Value);
}

This is again, quite simple if you think about it. If our point has a value of 9, the highest possible value, it can't be a low point. Otherwise, just compare the point values to all the adjacent values. If all adjacent values are higher, our point is the lowest.

With all that in place, we can do what I mentioned earlier to get the answer:

var lowPoints = points.Where(point => point.GetAdjacentPoints(points, maxCol, maxRow).IsLowPoint(point)).ToList();
var answerPart1 = lowPoints.Select(point => point.Value + 1).Sum();

Part 2

We use the same setup as we did in Part 1, with our dictionary of points and corresponding height values.

Now, I quote the description for Part 2, since I don't seem to be able to explain it myself in a way that is clear:

Next, you need to find the largest basins so you know what areas are most important to avoid.

A basin is all locations that eventually flow downward to a single low point. Therefore, every low point has a basin, although some basins are very small. Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.

So, my take on this is that I start from a low point, and work my way out to the adjacent points, until I reach a 9 or the boundary of the height map. When the basin can't grow anymore, we count the number of points in the basin and add those to a list. When we've done this for all our low points, we sort the list and take the top 3 basins (the largest basins), and multiply the sizes to get our final answer.

At first, this looks similar to Part 1:

var basinCounts = lowPoints.Select(point => GetValidAdjacentPointsCount(point, points, maxRow, maxCol)).ToList();
var answerPart2 = basinCounts.OrderByDescending(count => count).Take(3).Aggregate((a, b) => a * b);

But, lets take a look at whats going on in GetValidAdjacentPointsCount():

private static int GetValidAdjacentPointsCount(KeyValuePair<(int Row, int Col), int> sourcePoint, Dictionary<(int Row, int Col), int> allPoints, int maxRow, int maxCol)
{
    var validPoints = 1;

    var adjacentPoints = sourcePoint
        .GetAdjacentPoints(allPoints, maxCol, maxRow)
        .Where(x => x.Value != 9)
        .ToList();

    allPoints.Remove(sourcePoint.Key);

    if (!adjacentPoints.Any()) return validPoints;
    foreach (var point in adjacentPoints.Where(adjacentPoint => allPoints.ContainsKey(adjacentPoint.Key)))
    {
        validPoints += GetValidAdjacentPointsCount(point, allPoints, maxRow, maxCol);
    }

    return validPoints;
}

We use our old friend GetAdjacentPoints() to find all adjacent points to the current point. We filter out the 9s, since they are not supposed to be part of a basin. We also remove the current point from the dictionary of all points after we've fetched it's neighbours. Since each point can only be part of 1 basin, this works. After that we use recursion to travel along the adjacent points and counting the valid neighbours of each point. Sooner or later, we have no more valid points to travel to, and the total count of valid points will be returned.

Then, it's just a matter of finding the 3 largest basin and multiplying their values to get the answer.

These solutions are a bit messier than I would like, but they work and I've tried to make them as readable as possible. Although I'm 100% sure there are alot more elegant solutions to this problem out there.

Advent of Code 2021 - Day 9

Part 1

Part 2