Advent of Code 2020 Day 3 - Solution + Tutorial (TypeScript)

published
All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.


Prerequisites

I assume you've put your puzzle input into an array called map where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const map = [
  "..............#.#.......#......",
  ".....#.#...##...#.#..#..#..#..#",
  ".......##...#..#...........#...",];

Solution

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 3: Toboggan Trajectory

Part 1

This day's puzzle includes a map (your puzzle input) showing open squares (.) and trees (#) at exact integer coordinates. We should move down following a specific pattern, until we go past the bottom of the map. The puzzle says we should go right 3, down 1 and repeat this again and again.

Also, another thing to note: You can't go too far to the right. Whenever we would go past the right side of the map, the pattern of open squares (.) and trees (#) repeats.

The solution to this puzzle is the number of trees we end up on, while following the specific movement pattern of right 3, down 1.

So how do we start? First let's look at the map again:

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

If you've parsed the lines, you should have an array called map. This map can be seen as rows and columns (like a matrix). The row says which line to look at. The line is a string, so we can use the column to access a certain character in the line. The character is either . (open square) or # (tree).

Let's say we want to look at our starting position, the top left open square. That means we are at row 0, column 0. Why 0 you might ask? Well, we are using zero-based indices.

So map[0][0] is our starting position. We choose the first line and then the first character of said line. If we want to move right 3, down 1, we would end up on map[1][3]. Note the reversed notation. We use our map like so map[row][column]. Right 3 means we change the column, down 1 means we change the row.

Let's assign two variables, so we can change the row and column:

let row = 0;
let column = 0;

The next step is to find out, when we can stop moving. We want to move until we reached the last row. So let's just get the maximum value for row.

const rowMax = map.length - 1;

Our map is an array, that contains all the rows. So we can just get the row count and subtract 1. This gives us the last row index.

We also want to know, when we move past the right of the map. Look at your puzzle input. We can see that all lines have the same length. This means each line has the same number of columns. We just have to get the length of the first line and subtract by 1. That gives us the last column index. Like so:

const columnMax = map[row].length - 1;

Ok, we know the last row and the last column. What's next? Well we want to count the trees we end up on. Let's initialize a counter.

let trees = 0;

Let's start moving. We have to move until we are past the bottom of the map. We can use a while-loop here.

while (row < rowMax) {
  //
}

So while our current row is less than our maximum, we can keep on moving. So let's implement the moves. First, move right, 3 times:

column += 3;

We can simply add 3 to the current column. So our position changes when we access it like so map[row][column]. Wait a second! What should we do if we reach the right edge of the map? The puzzle says the map repeats itself for some weird reason. Ok, let's copy the map and ...

NO! There has to be a better way. Well, if the map repeats we could also go past the right and end up on the left side again. Let's think about it. For example, we are at position P.

..##.....P.
#...#...#..
.#....#..#.

Now we want to go 3 steps to the right. If the map repeats it would look like so:

.P##.......
#...#...#..
.#....#..#.

We are back again. This way, we don't have to copy the map, but we have to adjust the current column to respect this case. We can do so: First, check if we even went past the right of the map. Second, adjust the value for the column variable.

if (column > columnMax) {
  column -= columnMax + 1;
}

Okay, that's done. For example: If column is 32 and columnMax is 30. We have to subtract 30 from column and we end up on column 2. However, we also have to subtract 1 more. That is because we have to respect the step from the last column on the right to the first column on the left.

Now let's move down once. So our row changes.

row++;

Easy. Are we done yet? No! We have to check, whether we ended up on a tree. Let's do this! Remember, we can access our map by using the column and the row. Besides, a tree is denoted by a #.

if (map[row][column] === "#") {
  trees++;
}

We simply check if at the current position there is a tree. If yes, we increment our counter trees. If you've paid attention, you should know that we keep looping until we've reached the bottom of the map. After that we can return the trees variable, and we are done.

Here's the full solution:

let row = 0;
let column = 0;

const rowMax = map.length - 1;
const columnMax = map[row].length - 1;

let trees = 0;

while (row < rowMax) {
  column += 3;

  if (column > columnMax) {
    column -= columnMax + 1;
  }

  row++;

  if (map[row][column] === "#") {
    trees++;
  }
}

return trees;

Hurray!

Part 2

Part 2 of this puzzle is pretty similar to the first one. Our implementation will need a few adjustments, but it should be easy after you've done part 1.

Now we have multiple movement patterns. For each movement pattern we should check, how many trees we are ending up on.

These are the given patterns:

Right 1, down 1.
Right 3, down 1. (This is the one we've already used in part 1.)
Right 5, down 1.
Right 7, down 1.
Right 1, down 2.

We can translate these into an array of arrays. Let's do it:

const patterns = [
  [1, 1],
  [3, 1],
  [5, 1],
  [7, 1],
  [1, 2],
];

Each array item is an array itself. Basically it boils down to [right, down].

Now let's take a look at our implementation for the movement from part 1 again.

column += 3;

if (column > columnMax) {
  column -= columnMax + 1;
}

row++;

Instead of hard-coding the values 3 and 1 for right and down, we can use variables here.

column += right;

if (column > columnMax) {
  column -= columnMax + 1;
}

row += down;

Now we check the tree count for each movement pattern. Let's transform each pattern so that we have an array containing the tree counts for each movement pattern. Therefore, we can use the Array#map method.

patterns.map(([right, down]) => {
  //
})

Notice the right and down parameter? We can use array destructuring. The above is roughly equal to the following:

patterns.map((pattern) => {
  const [right, down] = pattern;
})

// AND ROUGHLY EQUAL TO

patterns.map((pattern) => {
  const right = pattern[0];
  const down = pattern[1];
})

Now we can use our adjusted implementation from part 1 to get the tree counts per movement pattern.

const treeCounts = patterns
  .map(([right, down]) => {
    let row = 0;
    let column = 0;

    const rowMax = map.length - 1;
    const columnMax = map[row].length - 1;

    let trees = 0;

    while (row < rowMax) {
      column += right;

      if (column > columnMax) {
        column -= columnMax + 1;
      }

      row += down;

      if (map[row][column] === "#") {
        trees++;
      }
    }

    return trees;
});

The above implementation returns an array containing the tree counts for each pattern. Our puzzle solution is the product of the single tree counts. We can use the Array#reduce method to reduce an array to a single value. That's nice, because we want to multiply each other and get a single number.

Let's do it:

return treeCounts
  .reduce((previousValue, currentValue) => {
    return previousValue * currentValue;
  });

We did it. We have solved the puzzle. Let's combine everything to get our full solution:

const patterns = [
  [1, 1],
  [3, 1],
  [5, 1],
  [7, 1],
  [1, 2],
];

return patterns
  .map(([right, down]) => {
    let row = 0;
    let column = 0;

    const rowMax = map.length - 1;
    const columnMax = map[row].length - 1;

    let trees = 0;
    while (row < rowMax) {
      column += right;

      if (column > columnMax) {
        column -= columnMax + 1;
      }

      row += down;

      if (map[row][column] === "#") {
        trees++;
      }
    }

    return trees;
  })
  .reduce((previousValue, currentValue) => {
    return previousValue * currentValue;
  });

Notice how I used method chaining. I did not introduce a treeCounts variable in the full solution. Instead, I've used the return value from the Array#map method and directly returned the value from the Array#reduce method.

Conclusion

It starts to get a bit more difficult. Maybe. It depends. Some puzzles you may find easier than someone else. I hope you have learned something. Maybe array destructuring was new for you. Or you didn't think of using the map like a matrix. Even if you are more experienced, I hope it's interesting to how other developers tackle this problem.

As always, I'd not claim this solution is efficient or the best in any way. It solves the puzzle and that's enough, I'd say.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!


If you like my content and you want to see more, please follow me on Twitter!
Questions, feedback or just wanna chat? Come and join my Discord!

You May Also Be Interested in the Following Posts

All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.