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

Today we’ll talk about toboggan trajectories1 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]

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():
    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:

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)

And we’re done. 0.16 ms.

  1. What a weird sentence to write. ↩︎