Advent of Code 2020, Day 3 -- Toboggan Trajectory

Dec 3rd, 2020

3 min read

Advent Of Code

Python solutions to Advent of Code 2020, day 3.

My Advent of Code solutions, done in Python. Refactors and solutions in other languages will be added if/when they're done.

Full code for Day 3 can be found on Github.

You can participate in Advent of Code at adventofcode.com/2020

The Day 3 problem can be found at adventofcode.com/2020/day/3

Solution, part 1

Each potential tree encountered will be at location (x, x * 3). Or really, thinking about it on the (x, y) coordinates, (y * 3, y). For every line down you go, you'll want to go right three spaces. (0, 0), (3, 1), (6, 2), etc.

My first thought was to iterate over the lines in the map and increment a variable by 3 each time, and when it got to the max length of the line, modulo it by the line length. This would work, and is a basic form of what I ended up doing.

I decided to make a list of indices, (rows, columns) tuples, that has each point we want to check on the map. For some reason, I ended up calling (rows, columns) (l, i) in my function, I suppose for (line, index)? I'm not sure, I'm on cold medication.

After creating my list of indices, I have a list comprehension mapping over the tree map (slope map?) by rows and columns, and returning the character found at each spot.

Finally, I return the count of "#" characters in the list.

Honestly, I'm pretty proud of my solution, especially since I did it while unable to sleep with a cold.

puzzle_input = open("input.txt", "r")
lines = puzzle_input.readlines()
lines = [line.strip() for line in lines]


# I want to find the index of each point in the array
# that is x * 3 from the previous line.
# Adding indices as (line number, index number) tuple.
# Also, have to modulo by the line length because
# each line repeats infinitely to the right.
def trees_encountered(tree_map):
    line_length = len(tree_map[0])
    input_length = len(tree_map)
    indices = [(x, (x * 3) % line_length) for x in range(0, input_length)]
    trees = [tree_map[l][i] for (l, i) in indices]
    number_of_trees = trees.count("#")
    return number_of_trees


print(trees_encountered(lines))

Solution, part 2

Like yesterday's part 2 solution, today's part 2 required only a bit of modification of part 1 to work. I've added arguments to trees_encountered to account for different (right, down), (x, y), (column, row), whatever you want to call it, coordinates.

Indices need to be multiplied by the amount of "jumps" that are made. The x coordinate was already being multiplied by 3, now we multiply it by the value of "right", and the y coordinate is now multiplied by the value of "down". We also want to divide the range by the value of "down" as well, otherwise we'll get a list of indices that is "down" times too long.

Originally, I was going to use math.ceil to divide the length of the indices (ceil to make sure we make it to the bottom of the slope!), but then I wondered if there was a ceiling division operator in Python like the floor division (//) operator. There isn't, but there is a cool math trick that does floor division with a negated divisor, then negates that division. This is what I'm using here.

Then, I had to add another function that will run trees_encountered for every slope we want to check, then multiply them together. I decided to pass in the slopes as a list of tuples, call trees_encountered while iterating over the list, and then use functools.reduce to return the final product.

from functools import reduce


# Adding arguments for x, y coordinates (right, down).
# Fun little "ceiling division" trick https://stackoverflow.com/a/54585138.
# The y range has to be divided by the "down" amount.
def trees_encountered(tree_map, right, down):
    line_length = len(tree_map[0])
    input_length = len(tree_map)
    indices = [(x * down, (x * right) % line_length) for x in range(0, -(input_length // -down))]
    trees = [tree_map[l][i] for (l, i) in indices]
    number_of_trees = trees.count("#")
    return number_of_trees


# Takes the map of the slope and a list of slope tuples.
# Makes a list comprehension of each of the trees encountered.
# Then returns the product of each slope's trees.
def tree_product(tree_map, slopes):
    trees = [trees_encountered(tree_map, r, d) for (r, d) in slopes]
    return reduce(lambda a, b: a * b, trees)


print(tree_product(lines, [(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)]))

Since I really like my solutions, I don't think I'm going to do any refactoring today. Sure, I could do a bit of cleanup and remove some unnecessary variables, like return trees.count("#") directly instead of putting it into the variable number_of_trees, but that's all minor stuff. Maybe if I find a clever solution on /r/AdventOfCode I'll try to implement it, but for now, this is the best solution I can come up with.

mary.codes