December 12, 2020

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.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.# --->`

**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();1415const lines = input.split("\n");1617function part1() {18 let treeCount = 0;19 let col = 0;2021 for (const line of lines) {22 // At some point we're going to get past the initial pattern23 // and need to modulo the col by line length to get the current24 // character25 const index = col % line.length;26 const currentChar = line[index];27 if (currentChar === "#") treeCount++;28 col += 3;29 }3031 return treeCount;32}`

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

**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};56function countTrees(lines: string[], slope: Slope) {7 let treeCount = 0;8 let right = slope.right;910 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 }1516 return treeCount;17}1819function 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 ];2728 return slopes29 .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.