Advent Of Code 2020 – Day 3 – Toboggan Trajectory

Great job reaching here so far. Finally, we’ve logged in to Toboggan successfully, now we have to travel to the airport through a jungle. The path is not very good and has a lot of trees. So, here comes our next task.

The 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:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

On further reading you will find that the given pattern is repeating.

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

Here’s the task that we have to perform.

You start on the open square (.) in the top-left corner and need to reach the bottom (below the bottom-most row on your map).

The toboggan can only follow a few specific slopes (you opted for a cheaper model that prefers rational numbers); start by counting all the trees you would encounter for the slope right 3, down 1:

From your starting position at the top-left, check the position that is right 3 and down 1. Then, check the position that is right 3 and down 1 from there, and so on until you go past the bottom of the map.

From the start till the end, how many trees will you encounter?

Part One – Count the trees in the path

The idea is to consider the input area as a 2-d plane. Let’s call it frame.

So, to read the input from the file and create a frame, we can use the following logic:

    ifstream day_3_input("inputs/day3.txt");
    string line;

    vector<vector<char>> frame;
    while (getline(day_3_input, line)) {
        vector<char> col;
        for (int j=0; j < line.length(); j++) {
            col.push_back(line[j]);
        }
        frame.push_back(col);
    }

The above code will create a 2d frame for us to work with.

Next, we need to define our trajectory/path through which we will be going through. As we know that toboggan moves one space down and then 3 spaces right, in plotting the same on a graph we get a slope. This slope is our path. So, let’s define a variable slopes. This will contain the slope of our path.

slopes = { {3,1} } // here we move 3 spaces to right and one space down

So far so good. We will see in a minute how the slopes are being used here.

Let’s start our journey with the given slope.

    for (auto slope: slopes) {
        int x = slope[1], y = slope[0];
    }

This above piece of code will give us the path on which we have to walk. So, we now have the code to read the slope from the array and tell us how to move but let’s write a little more code to actually move the toboggan.

    for (auto slope: slopes) {
        int x = slope[1], y = slope[0];
        while (x < frame.size()) {
            y += slope[0];
            x += slope[1];
        }
    }

Now, we are actually moving.

In the above code, we are instructing toboggan to move until we cross the jungle. And at each step, move down by slope[0] and then move straight by slope[1].

But wait, the solution for our problem was not to move the toboggan but also to count the trees that we encounter in our path. So, let’s quickly write some code for that. We’ve done the hard part, it’s just the matter of counting the trees now.

Let’s hire someone to count the trees on the path.

Here we know that whenever we find a # on our path then we have to increment the count. Because # represents a tree.

    for (auto slope: slopes) {
        count = 0;
        int x = slope[1], y = slope[0];
        while (x < frame.size()) {
            if (frame[x][y % frame[x].size()] == '#') count++;
            y += slope[0];
            x += slope[1];
        }
        cout << count << endl;
    }

Let’s run the code and see if we get the correct answer.

Viola!!! Got the right answer.

Let’s move to the part 2 of the problem.

Part 2 – Multiply the total trees encountered on each slope

This part only extends the above problem by adding more slopes. We already wrote the code in a way that is extensible.

The only change that we have to make in the existing code is to add the additional slopes to the vector and maintain the multiplication of all the trees that we encounter at each slope.

Let’s directly jump to the code:

    vector<vector<int>> slopes =  { {1,1}, {3,1}, {5,1}, {7,1}, {1,2} };
    int mul = 1;
    
    for (auto slope: slopes) {
        int count = 0;
        int x = slope[1], y = slope[0];
        while (x < frame.size()) {
            if (frame[x][y % frame[x].size()] == '#') count++;
            y += slope[0];
            x += slope[1];
        }

        cout << count << "," << endl;
        mul *= count;
    }
    

    cout << mul;

Let’s run this code again and see if we get the right answer or not.

Yes, we get the right answer. The above code solves the given problem.

I hope you learned something new from this exercise. Let me know your thoughts in the comments below.