Advent of Code 2020: Day 3

, 7 min read
advent of code 2020

Part 1

Today we continue from the Toboggan house where we left off yesterday,

With the toboggan login problems resolved, you set off toward the airport. While travel by toboggan might be easy, it’s certainly not safe: there’s very minimal steering, and the area is covered in trees. You’ll need to see which angles will take you near the fewest trees.

Due to the local geology, trees in this area only grow on exact integer coordinates in a grid. You make a map (your puzzle input) of the open squares (.) and trees (#) you can see. For example:

..##....... ..##....... [repeated] #...#...#.. #...#...#.. [repeated] .#....#..#. .#....#..#. [repeated] ..#.#...#.# ..#.#...#.# [repeated] .#...##..#. .#...##..#. [repeated] ..#.##..... ..#.##..... [repeated] .#.#.#....# .#.#.#....# [repeated] .#........# .#........# [repeated] #.##...#... #.##...#... [repeated] #...##....# #...##....# [repeated] .#..#...#.# .#..#...#.# [repeated]

These aren’t the only trees, though; due to something you read about once involving arboreal genetics and biome stability, the same pattern repeats to the right many times.

You start on the top-left corner and need to reach the bottom. The toboggan can only follow a few specific slopes; begin by counting all the trees you would encounter for the slope right 3, down 1:

Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?

You can read the full text here.

This is much more like it, an input which I can ingest easily with C++. In summary, we have been given a map of the hill which we need to toboggan down. The #’s represent trees and the .’s represent open spaces. We need to head down the hill and count how many trees we may face, along any given path.

My initial thoughts are that I want to generate a vector of vectors, which is mostly equivalent to a multi-dimensional array (if you are more familiar with those).

This will allow me to easily query coordinates of my input, for example,

1
2
3
mymap[0][0] = "." // Top row, first element
mymap[1][0] = "#" // Second row down, first element
mymap[0][1] = "." // Top row, second element

with the map loaded into a data structure like this, we’re almost halfway through solving this problem. To achieve this we’re using the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
std::vector<std::vector<char>> mymap;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
    std::vector<char> row;
    for(int i=0; i<line.size(); i++)
        row.push_back(line[i]);
    mymap.push_back(row);
}
myfile.close();

We start by defining a vector of vector’s which store char’s. We then loop through the file reading in each line and generating a new row.

We can test that the code has been ingested correctly by displaying our map to screen,

1
2
3
4
5
6
/* Checking input read correctly */
for(auto &r : mymap){
    for(auto c : r)
        std::cout << c;
    std::cout << std::endl;
}

We do this by looping through every row in our map, and for each row, we loop through every column, outputting the value.

All we need to do now is send the toboggan down the hill and see how many trees it hits. We’re going to do this with a while loop. The logic is “while the toboggan hasn’t reached the bottom, take another step and check for trees”. The only complication to this process is that our map repeats in the x-axis. For the example input, there are only 11 steps in the x-axis, once you step past the end, you go back to the beginning. These are called periodic boundary conditions. Fortunately, there are tricks for dealing with those:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int trees = 0;
std::pair<int, int> loc = {0, 0};
std::pair<int, int> dir = {1, 3};
while(loc.first < mymap.size()){
    // Did we meet a tree?
    if (mymap[loc.first][loc.second] == '#') trees++;
    // Step along in the direction we have been given
    loc.first += dir.first;
    loc.second += dir.second;
    // This enforces periodic boundary conditions along the x-axis
    loc.second %= mymap[0].size();
}

The last part of the above code is where we apply our periodic magic. We’re using the modulo operator. The modulo operator returns the remainder, consider the following examples,

1
2
3
10 % 7 = 3,  (10/7 == 1, remainder 3)
7 % 7 = 0,  (7/7 == 1, remainder 0)
4 % 7 = 4,  (4/7 == 0, remainder 4)

Applying this to our problem, if our x-position gets larger than 11, then the modulo operator will wrap us back around to the beginning. Awesome!

All we have to do now is run the code and output the number of trees that we meet to get our first ⭐

The full code can be found on github

Part 2

Time to check the rest of the slopes - you need to minimise the probability of a sudden arboreal stop, after all.

Determine the number of trees you would encounter if, for each of the following slopes, you start at the top-left corner and traverse the map all the way to the bottom:

1
2
3
4
5
    Right 1, down 1.
    Right 3, down 1. (This is the slope we already checked.)
    Right 5, down 1.
    Right 7, down 1.
    Right 1, down 2.

What do you get if you multiply together the number of trees encountered on each of the listed slopes?

You can read the full text here.

Part 2 was very kind today. We just have to repeat the same process as before but with different directions. We can put the code in a for loop. It would have been really nice if we’d written part 1 as a function that takes the direction as an input; but, alas we did not.

The modified code is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
std::vector<std::pair<int, int>> dirs = {
    {1, 1}, {1, 3}, {1, 5}, {1, 7}, {2, 1}
};
for (auto dir : dirs){
    // Reset location and number of trees
    int trees = 0;
    std::pair<int, int> loc = {0, 0};
    // While we haven't reached the bottom
    while(loc.first < mymap.size()){
        ...
    }
    ans2 *= trees;
}

We start by making a vector of directions to check. We then loop over each direction and repeat the same process as before. Submit answer 2, and now we have both stars: ⭐⭐!

The full code can be found on github

Reflections

I thoroughly enjoyed today’s puzzle. The input wasn’t too hard to deal with, and part 2 followed on quite neatly from part 1.

Algorithmically, there were very few optimisations possible today. The time complexity of our solution scales as O(N * M), where N is the height of the input and M is the number of columns. The space complexity is also O(N * M), e.g. the map loaded into memory. The reason that the time complexity scales with M is the file read, in our solution above we read the whole file into memory, every row and every column. However, the number of columns is irrelevant in the main algorithm as we check a single value per row, per direction.

I’ve also assumed the map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

I think the optimal solution is to first generate a vector of points that we visit for each direction. We can then do a sparse read where we just loop through lines in the file reading in single values. This gives the whole solution a O(N * K) time and space complexity, where N is the height of the input and K is the number of directions that we consider.

See you again tomorrow!

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts