December 12, 2020

Advent of Code 2020 Day 3 Solution

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other. — AdventOfCode.com

For this puzzle, we're given a map of # and .. # matches a tree and . matches an open square. The input looks something like this:

1..##.......
2#...#...#..
3.#....#..#.
4..#.#...#.#
5.#...##..#.
6..#.##.....
7.#.#.#....#
8.#........#
9#.##...#...
10#...##....#
11.#..#...#.#

The given input is only the pattern for the whole map. The same pattern repeats to the right many times:

1..##.........##.........##.........##.........##.........##....... --->
2#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
3.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
4..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
5.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
6..#.##.......#.##.......#.##.......#.##.......#.##.......#.##..... --->
7.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
8.#........#.#........#.#........#.#........#.#........#.#........#
9#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
10#...##....##...##....##...##....##...##....##...##....##...##....#
11.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.# --->

Part I

Problem: If we start at the top-left corner and move down the map with the slope down: 1, right: 3 how many trees do we encounter in our path?

Solution: We're going to use the given slope to traverse the map and count the number of # characters.

1const input = `
2..##.......
3#...#...#..
4.#....#..#.
5..#.#...#.#
6.#...##..#.
7..#.##.....
8.#.#.#....#
9.#........#
10#.##...#...
11#...##....#
12.#..#...#.#
13`.trim();
14
15const lines = input.split("\n");
16
17function part1() {
18 let treeCount = 0;
19 let col = 0;
20
21 for (const line of lines) {
22 // At some point we're going to get past the initial pattern
23 // and need to modulo the col by line length to get the current
24 // character
25 const index = col % line.length;
26 const currentChar = line[index];
27 if (currentChar === "#") treeCount++;
28 col += 3;
29 }
30
31 return treeCount;
32}

Complexity: This code runs in linear time and constant space.

Part II

Prolem: We're given a few differnet slopes. After counting the encoutered trees for each slope, we need to multiply them together to solve this puzzle.

Solution: Using our solution for Part I, we can make a function that can accept a slope and give us a tree count. We can then use that function to get the tree counts for every slope and mulitply the results together.

The slopes are:

  • Right 1, down 1
  • Right 3, down 1
  • Right 5, down 1
  • Right 7, down 1
  • Right 1, down 2
1type Slope = {
2 right: number;
3 down: number;
4};
5
6function countTrees(lines: string[], slope: Slope) {
7 let treeCount = 0;
8 let right = slope.right;
9
10 for (let down = slope.down; down < lines.length; down += slope.down) {
11 const col = right % line.length;
12 const currentChar = line[col];
13 if (currentChar === "#") treeCount++;
14 }
15
16 return treeCount;
17}
18
19function part2() {
20 const slopes: Slope[] = [
21 { right: 1, down: 1 },
22 { right: 3, down: 1 },
23 { right: 5, down: 1 },
24 { right: 7, down: 1 },
25 { right: 1, down: 2 },
26 ];
27
28 return slopes
29 .map((slope) => countTrees(lines, slope))
30 .reduce((acc, count) => acc * count);
31}

Complexity: Time complexity is O(n*m) where n is the number of lines and m is the number of slopes we have to loop through and space complexity remains constant.