Advent of code: 2020 Day 03

⚠️ SPOILER ALERT
This is a post with my solutions and learnings from the puzzle. Don't continue
reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit adventofcode.com/2020/day/3.

My programming language of choice is python and all examples below are in python.

Key learnings

• Functions and abstraction

Part 1 is solved using the learning from the previous days. Part 2 introduces a new key learning. By asking us to calculate several slopes it forces us to rewrite the code from part 1 and generalize it. This encourages us to create a function for the calculation and use a good code structure.

Puzzle

The puzzle is about counting amount of trees you'll encounter if you travel through a "forest" in a straight line. The input is a map over the forest where # is a tree and . is an open space.

Note:
The map is repeating horizontally. In this puzzle you can see it as returning to the left side once you reach the right edge of the map.

Example input:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....

Part 1

The angle you should travel in is described as a slope of right 3 and down 1. The answer is how many trees you'll hit if you traverse the map in this slope.

A visual representation of the puzzle:

Parse input

First step is to save the input in a local file and parse it in python:

# Open the input file
inputfile = open('03.input', 'r')

# Parse lines
data = [x.strip() for x in inputfile.readlines()]

Solution

def part1(data):
    x = 0                             # X is current column
    total = 0                         # Count of trees
    map_width = len(data[0])
    map_height = len(data)
    for y in range(map_height):       # Iterate each row
        if data[y][x] == '#':         # Use x,y as coordinates to check for tree
            total += 1                # Count if tree
        x = (x + 3) % map_width       # Jump 3 steps right (modulus to keep within map)
    return total

print "Solution part 1: %d" % part1(data)

Part 2

The second puzzle has the same input. Now you have to try multiple slopes:

• Right 1, down 1
• Right 3, down 1
• Right 5, down 1
• Right 7, down 1
• Right 1, down 2

The answer is product of multiplying amount of trees encountered in the above slopes.

Solution

In this stage you'll realize it's easier to refactor your code into a function with the slope as parameter.

The last slope with down 2 forces us to use both columns and rows skipped as parameters to your function.

def part2(data):
    def traverse(right, down):              # Define a function for generalizing
        x = 0
        total = 0
        for i in range(len(data)):
            if i % down != 0:               # Skip rows according to "down"-variable
                continue
            if data[i][x] == '#':
                total += 1
            x = (x + right) % len(data[0])  # Use right-parameter
        return total

    # Use function to get values for each slope
    return traverse(1,1) * traverse(3,1) * traverse(5,1) * traverse(7,1) * traverse(1,2)

Alternative solutions

Functional style

A more functional approach would be:

def part1(data):
    def encountered((idx, row)):
      x_position = (idx * 3) % len(row)
      return row[x_position] == '#'

    trees_encountered = filter(encountered, enumerate(data))
    return len(trees_encountered)

def part2(data):
    def traverse(right, down):
      # Filter out jumped rows
      def filter_row((idx, row)):
        return idx % down == 0
      rows_hit = filter(filter_row, enumerate(data))

      # Filter out rows where we encounter a tree
      def encountered((idx, row)):
        x_position = (idx * right) % len(row)
        return row[x_position] == '#'
      trees_encountered = filter(encountered, rows_hit)

      return len(trees_encountered)

    return traverse(1,1) * traverse(3,1) * traverse(5,1) * traverse(7,1) * traverse(1,2)

List comprehensions

Python has a nice feature of list comprehensions. Once you get used to the syntax it is easy to follow. Though a lot happens in one row, so be careful to not overuse so that it gets hard to grasp.

def part2(data):
    def traverse(right, down):
      # Filter out jumped rows
      rows_hit = [
        row
        for idx, row
        in enumerate(data)
        if idx % down == 0
      ]

      # Filter out rows where we encounter a tree
      trees_encountered = [
        idx
        for idx, row
        in enumerate(rows_hit)
        if row[(idx * right) % len(row)] == '#'
      ]
      return len(trees_encountered)

    return traverse(1,1) * traverse(3,1) * traverse(5,1) * traverse(7,1) * traverse(1,2)

Thanks for reading!

I hope these solutions were helpful for you. Just ask if anything was hard to grasp.

Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/03.py