Photo by Any Lane from Pexels

I’m participating in the Advent of Code 2021. Here’s my solutions for Day 9 - Smoke Basin.

Problem 1

In the Puzzles for Day 9, we’re evaluating the low points of a 100x100 grid where each point represents a height with a value of 0 (lowest) to 9. The risk level of a point is 1 + it’s height. We need to find the sum of the risk levels of all the lowest points on the grid.

Solution

All my solutions are written in C#. You can find all my solutions in my Git repo.

To solve this problem, we’ll look at each point and compare it to the points above, below, left and right of it (ignore diagonals). If a point is lower than the 2 to 4 points around it, we will add its risk value to the total.

using System.Text;

Console.WriteLine("Advent of Code 2021");
Console.WriteLine("Day 9 - Puzzle 1");

//Solution logic goes here

//Load input array
string[] lines = System.IO.File.ReadAllLines("input.txt");
var grid = new int[100, 100];
for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        grid[i, j] = Convert.ToInt32(lines[i].Substring(j, 1));
    }
}

var total = 0;
for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        var lowest = true;
        //check left
        if (i > 0 && grid[i, j] >= grid[i - 1, j])
        {
            lowest = false;
        }

        //check above
        if (lowest && j > 0 && grid[i, j] >= grid[i, j - 1])
        {
            lowest = false;
        }

        //check below
        if (lowest && j < 99 && grid[i, j] >= grid[i, j + 1])
        {
            lowest = false;
        }

        //check right
        if (lowest && i < 99 && grid[i, j] >= grid[i + 1, j])
        {
            lowest = false;
        }

        if (lowest) total += grid[i, j] + 1;
    }
}


Console.WriteLine($"Total sum of low points: {total}");

//Stop and wait for enter before exiting
Console.ReadLine();

The answer is: 514

Problem 2

collect all the lowest points from problem 1. Then, for each one we’ll need to examine the points around it, building a list of points that are higher and higher until we find all the points that would flow down into that lowest point.

Solution

I decided it was time to get a little fancier in my solution. So I built a class to represent the basin and to collect in it the lowest point and a function to find all the points that would flow down into it. I did this by iterating through the points, starting with the base point. For each point, I would check the points around it. If it was higher than the current point, but not 9, I added it to my points and added that point to the list to be evaluated. I kept circling through that until I found no more higher points.

Console.WriteLine("Advent of Code 2021");
Console.WriteLine("Day 9 - Puzzle 2");

//Solution logic goes here

//Load input array
string[] lines = System.IO.File.ReadAllLines("input.txt");
var grid = new int[100, 100];
for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        grid[i, j] = Convert.ToInt32(lines[i].Substring(j, 1));
    }
}

var basins = new List<Basin>();
var total = 0;
for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        var pt = new List<Points>();
        var lowest = Checker.CheckThePoint(grid, i, j);

        if (lowest)
        {
            var basin = new Basin()
            {
                PointX = i,
                PointY = j,
                BasinPoints = new List<Points>()
            };

            basins.Add(basin);
        }
    }
}

foreach (var basin in basins)
{
    basin.CheckPoints(grid);
}

var subset = basins.OrderByDescending(x => x.BasinPoints.Count).Take(3).ToList();
total = subset[0].BasinPoints.Count * subset[1].BasinPoints.Count * subset[2].BasinPoints.Count;

Console.WriteLine($"Total sum of low points: {total}");

//Stop and wait for enter before exiting
Console.ReadLine();

public struct Points
{
    public int x;
    public int y;
}

public static class Checker { 
    public static bool CheckThePoint(int[,] grid, int i, int j)
    {
        var lowest = true;
        //check left
        if (i > 0 && grid[i, j] >= grid[i - 1, j])
        {
            lowest = false;
        }

        //check above
        if (lowest && j > 0 && grid[i, j] >= grid[i, j - 1])
        {
            lowest = false;
        }

        //check below
        if (lowest && j < 99 && grid[i, j] >= grid[i, j + 1])
        {
            lowest = false;
        }

        //check right
        if (lowest && i < 99 && grid[i, j] >= grid[i + 1, j])
        {
            lowest = false;
        }

        return lowest;
    }
}

public class Basin
{
    public int PointX;
    public int PointY;
    public List<Points> BasinPoints;

    public void CheckPoints(int[,] grid)
    {
        var pointsToCheck = new List<Points>() { new Points() { x = PointX, y = PointY } };


        while (pointsToCheck.Any())
        {
            var count = pointsToCheck.Count();
            for(int a = count-1; a>= 0; a--)
            {
                var point = pointsToCheck[a];
               
                if (grid[point.x, point.y] < 9 && !BasinPoints.Contains(point))
                {
                    BasinPoints.Add(point);

                    //check left
                    if (point.x > 0 && grid[point.x, point.y] < grid[point.x - 1, point.y])
                    {
                        pointsToCheck.Add(new Points() { x = point.x - 1, y = point.y });
                    }

                    //check above
                    if (point.y > 0 && grid[point.x, point.y] < grid[point.x, point.y - 1])
                    {
                        pointsToCheck.Add(new Points() { x = point.x, y = point.y - 1 });
                    }

                    //check below
                    if (point.y < 99 && grid[point.x, point.y] < grid[point.x, point.y + 1])
                    {
                        pointsToCheck.Add(new Points() { x = point.x, y = point.y + 1 });
                    }

                    //check right
                    if (point.x < 99 && grid[point.x, point.y] < grid[point.x + 1, point.y])
                    {
                        pointsToCheck.Add(new Points() { x = point.x + 1, y = point.y });
                    }

                }
                    pointsToCheck.Remove(point);
            }
        }
    }
}

The answer is: 1103130