Advent of Code 2020, day 3

Programming Advent of Code, programming, puzzle

It’s day 3 already! As before, all my solutions are available on https://git.sr.ht/~schnouki/advent-of-code.

Today we’ll talk about toboggan trajectories!1 In typical AoC fashion, our input is a map in ASCII art. What’s important to us is its size and the position of the trees… So we’ll parse this input and store just that: the width and height of the map, and the coordinates of all trees as a set of (x, y) tuples.

from dataclasses import dataclass
from typing import Set, Tuple

Coord = Tuple[int, int]

@dataclass
class Map:
    w: int
    h: int
    trees: Set[Coord]

    def add_line(self, line: str):
        w = len(line)
        if self.w == 0:
            self.w = w
        elif self.w != w:
            raise ValueError()

        for x in range(w):
            if line[x] == "#":
                self.trees.add((x, self.h))
        self.h += 1

data = Map(0, 0, set())
for line in raw_data.splitlines():
    data.add_line(line)
    return data

Part 1

We need to count trees on a trajectory with a given slope. Basically, go right, go down, and if there’s a tree at this position, increment a counter. As the map “repeats” horizontally, we calculate horizontal coordinates modulo the map width.

We end up with this very simple and generic method for our Map dataclass:

@dataclass
class Map:
    ...

    def count_trees(self, right: int, down: int) -> int:
        n = 0
        x = 0
        for y in range(down, self.h, down):
            x = (x + right) % self.w
            if (x, y) in self.trees:
                n += 1
        return n

...
print(data.count_trees(3, 1))

That’s it. 0.04 ms.

Part 2

Same things, but with several different slops, and we must multiply the results together. Easy enough, thanks to that generic count_trees() method!

slopes = ((1, 1),
          (3, 1),
          (5, 1),
          (7, 1),
          (1, 2))
res = 1
for right, down in slopes:
    res *= data.count_trees(right, down)
print(res)

And we’re done. 0.16 ms.


  1. What a weird sentence to write. ↩︎