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:

Copied!
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:

Copied!
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.

Copied!
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

Copied!
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.