Advent Of Code 2021 – Smoke Basin – Puzzle 9

Hello ! I’m Xavier Jouvenot and here is the 9th part of a long series on Advent Of Code 2021.

For this new post, we are going to solve the problem from the 9th December 2021, named "Smoke Basin". The solution I will propose in C++, but the reasoning can be applied to other languages.

Self promotion: Here are a few social networks where you can follow me and check my work as a programmer and a writer 😉
personal website, Twitter, Dev.to, CodeNewbie, Medium, GitHub

Part 1

The Problem

The full version of this problem can be found directly on the Advent of Code website, I will only describe the essence of the problem here:

Today, we realize that the cave in which we are navigating are lava tubes, some of them being still active and smoke flowing through most of them. To avoid any dangerous situation, we study the height map generated by the submarine which looks like:

2199943210
3987894921
9856789892
8767896789
9899965678

Our first goal is to find the lowest points on this map. A lowest point is a point where all the adjacent location are higher (not counting diagonals). Then, to calculate the risk level of each of them (which has a value of 1 plus the height of the low point) and summing them all.

Solution

First of all, to be able to focus on the problem at hand, I have directly made the input of a matrix of integers, instead of parsing a text or a file. So the input declaration is:

using Input = std::array<std::array<int, 100>, 100>;
constexpr Input input {{
{3,5,6, /*...*/ ,7,6,7},
{2,6,7, /*...*/ ,6,5,6},
/* ... */
{8,7,6, /*...*/ ,3,4,5}
}};

Now that we are all on point with the input we are going to work with, let’s start by implementing some functions we are going to need 🙂

The first thing we need is a function which gives us the heights of the adjacent position to a specific one. By accounting for the border of the map, the number of adjacent position may differ, so we use a std::vector to collect them. This function is fairly straight forward:

std::vector<int> getAdjacentValuesTo(Input input, size_t x_pos, size_t y_pos) {
    std::vector<int> adjacents;

    if(x_pos != 0) { adjacents.emplace_back(input[x_pos-1][y_pos]); }
    if(y_pos != 0) { adjacents.emplace_back(input[x_pos][y_pos-1]); }
    if(x_pos != input.size()-1) { adjacents.emplace_back(input[x_pos+1][y_pos]); }
    if(y_pos != input.front().size()-1) { adjacents.emplace_back(input[x_pos][y_pos+1]); }

    return adjacents;
}

Now that we are able to collect the heights of the adjacent positions, we can identify very simply if a point is a low point or not. By using standard function std::min_element and the previously written function, we can see if there is any height of an adjacent position is lower or not than a specific position.

bool isLowPoint(Input input, size_t x_pos, size_t y_pos) {
    auto adjacents = getAdjacentValuesTo(input, x_pos, y_pos);
    return input[x_pos][y_pos] < *std::min_element(std::begin(adjacents), std::end(adjacents));
}

And that about all the handy functions we need to be able to solve this problem, in our main function. Indeed, all we have now to do is iterate through our matrix and check if the position is a low position. If this is the case, we update a variable sumOfRiskLevels in the correct risk value and we display this variable value at the end of our program:

int main()
{
    auto sumOfRiskLevels{0};
    for(auto i=0; i<input.size(); ++i)
    {
        for(auto j=0; j<input[i].size(); ++j)
        {
            if(isLowPoint(input, i, j))
            {
                sumOfRiskLevels += input[i][j] + 1;
            }
        }
    }
    std::cout << "The solution is: " << sumOfRiskLevels << std::endl;
    return 0;
}

Well this was fairly easy ! Let’s see if this is the case of the second part 😉

Part 2

Problem

The description of this problem not that long (compare to the previous day, for example). We define a basin as a set of position where everything flows downward to a low point. So the location of height 9 don’t count has being in a basin, since they are the border of the basins.

We need to find, in our height map, the 3 largest basins and multiply their size together in order to have the answer of our problem, and so that our submarine knows what areas to avoid.

Solution

Well, at first, I didn’t have any idea on how to solve this problem ! All the solution that came to my mind didn’t satisfy me, and they probably wouldn’t have worked. 😝

And after a little bit of thinking, I finally had a good one: there is probably an algorithm for that ! So I went online look at some of them and found just what I needed: the Flood-fill algorithm.

This is a simple algorithm which can be use to fill an area, without missing any element, while taking borders into account. But first, we need a little Position structure which is going to simplify a lot the code readability:

struct Position
{
    constexpr bool operator==(const Position& other) const { return x == other.x and y == other.y; }

    size_t x{0}, y{0};
};

The operator== will come handy for some standard C++ functions use.

And now, we are ready to implement a version of the Flood-fill algorithm, in order to find the size of the basin. Let’s look at the code and explain it after:

void basinExploration(const Input& input, std::vector<Position>& alreadyVisitedPosition, const Position& currentPosition)
{
    if(std::any_of(std::begin(alreadyVisitedPosition), std::end(alreadyVisitedPosition), [&currentPosition](const auto& position){ return position == currentPosition; })
       or input[currentPosition.x][currentPosition.y] == 9)
    {
        return;
    }
    alreadyVisitedPosition.push_back(currentPosition);

    if(currentPosition.x != 0) { basinExploration(input, alreadyVisitedPosition, {currentPosition.x-1, currentPosition.y}); }
    if(currentPosition.y != 0) { basinExploration(input, alreadyVisitedPosition, {currentPosition.x, currentPosition.y-1}); }
    if(currentPosition.x != input.size()-1) { basinExploration(input, alreadyVisitedPosition, {currentPosition.x+1, currentPosition.y}); }
    if(currentPosition.y != input.front().size()-1) { basinExploration(input, alreadyVisitedPosition, {currentPosition.x, currentPosition.y+1}); }
}

So, you may already have understood by looking at the code, this is a recursive version of the algorithm, meaning that this function will call itself in order to achieve it’s purpose. In this function, we start by checking if we already have visited the currentPosition, or if the current position is a border (meaning its height is 9), if this is the case, there is nothing to do, so we return directly.

If we are actually in a new position never visited before, we add this new position in the array of alreadyVisitedPosition. And finally we call this function on each adjacent position to the current one.

I have to say that it was amazingly simple to right write and is one of the first try I one-shot an implementation ! I was so surprise that I made it work on the first try ! 😂

But, we are not done yet ! We still need to write a little bit of code! First, we need to actually get the size of the basin, which is trivial using out basinExploration function:

int getBasinSize(const Input& input, const Position& lowPointPosition)
{
    std::vector<Position> alreadyVisitedPosition;
    basinExploration(input, alreadyVisitedPosition, {lowPointPosition.x, lowPointPosition.y});
    return alreadyVisitedPosition.size();
}

Since the alreadyVisitedPosition contains all the positions in the basin, then its size is the information that we needed.

And now, all we have left, is the main function:

int main()
{
    std::vector<int> basinSizes;
    for(size_t i=0; i<input.size(); ++i)
    {
        for(size_t j=0; j<input[i].size(); ++j)
        {
            if(isLowPoint(input, i, j))
            {
                basinSizes.emplace_back(getBasinSize(input, {i, j}));
            }
        }
    }

    std::sort(std::begin(basinSizes), std::end(basinSizes));
    const auto result = basinSizes[basinSizes.size() - 1] * basinSizes[basinSizes.size() - 2] * basinSizes[basinSizes.size() - 3];
    std::cout << "The solution is: " << result << std::endl;
    return 0;
}

In here, we start with the for loops by collecting the basin size, and to avoid to count one basin twice, we only run the search on the low point of the basin. Once all the basin sizes have been collected, we sort them, and multiply the 3 highest of them, the ones at the end of the array of basin sizes.

And voilà 🙂

Other Solutions

As usual, after solving the problem, I went on the Advent Of Code subreddit to see how some other people have solved this day problem, and, this time I mainly find some great visualizations of the part 2 (the Flood-fill algorithm is so satisfying to watch working 😍), but very few articles or video about this day"s problem!

So today, I only going to mention this article, by Paolo Galeone which is a very interesting one where he solves the problem using Tensorflow and Python !

And I am also giving you 3 nice visualization of the part 2, since they are so nice to watch:

• First one is by @asymmetricia
• The second one, with the low points discovery, by urny
• And the last one by AIforce

Conclusion

You can note that the solutions written in this post, don’t include all the sources to make running programs, but only the interesting part of the sources to solve this problem. If you want to see the programs from end to end, you can go on my GitHub account, explore the full solution, add comments or ask questions if you want to, on the platform you read this article, it will also help me improve the quality of my articles.

Thank you all for reading this article, And until my next article, have a splendid day 😉

Interesting links

• Flood-fill algorithm
• constexpr documentation
• std::array documentation
• std::vector documentation
• std::min_element documentation
• std::any_of documentation
• lambda documentation
• Advent of Code – Day 9
• 10xlearner website, Twitter, Dev.to, CodeNewbie, Medium, GitHub