Advent of Code - 2021

This is a solution to Day 5 of Advent of Code 2021.

Day 5 - Hydrothermal Venture

You come across a field of hydrothermal vents on the ocean floor! These vents constantly produce large, opaque clouds, so it would be best to avoid them if possible.

They tend to form in lines; the submarine helpfully produces a list of nearby lines of vents (your puzzle input) for you to review. For example:

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Each line of vents is given as a line segment in the format x1,y1 -> x2,y2 where x1,y1 are the coordinates of one end the line segment and x2,y2 are the coordinates of the other end. These line segments include the points at both ends. In other words:

An entry like 1,1 -> 1,3 covers points 1,1, 1,2, and 1,3.
An entry like 9,7 -> 7,7 covers points 9,7, 8,7, and 7,7.
For now, only consider horizontal and vertical lines: lines where either x1 = x2 or y1 = y2.

So, the horizontal and vertical lines from the above list would produce the following diagram:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

In this diagram, the top left corner is 0,0 and the bottom right corner is 9,9. Each position is shown as the number of lines which cover that point or . if no line covers that point. The top-left pair of 1s, for example, comes from 2,2 -> 2,1; the very bottom row is formed by the overlapping lines 0,9 -> 5,9 and 0,9 -> 2,9.

To avoid the most dangerous areas, you need to determine the number of points where at least two lines overlap. In the above example, this is anywhere in the diagram with a 2 or larger - a total of 5 points.

Read data

Once again, we have a custom input format so we need a custom transformer function to convert an input like

102,578 -> 363,317

into a namedtuple like

Line(x1=102, y1=578, x2=363, y2=317)

from utils import read_input
from collections import namedtuple


Line = namedtuple('Line', ['x1', 'y1', 'x2', 'y2'])

def transformer(input_line):
    coordinates = [coords.split(',') for coords in input_line.strip().split(' -> ')]
    line = Line(
        x1=int(coordinates[0][0]),
        y1=int(coordinates[0][1]),
        x2=int(coordinates[1][0]),
        y2=int(coordinates[1][1])
    )
    return line


lines = read_input(5, transformer)

Part 1 & Part 2

This solution covers both parts since the change was so small (allowing diagonal, 45-degree lines).

To solve the puzzle, we need to calculate all the points in all the lines, then calculate how many times each point exists in all those lines and finally count the ones with two or more occurrences of those points.

Each line is identified by its starting position (x1, y1) and its end position (x2, y2).

For horizontal lines, we find all the points in line by increasing or decreasing the y value from y1 to y2 by one at the time and creating new points on every iteration, keeping the x value the same.

For vertical lines, we do the same but changing x and keeping y the same.

Python's range function is nice since it allows us to define the direction with step parameter: a positive step will increase from start to end and negative step will decrease from start to end.

In Part 2 of the puzzle, we also need to take into account the diagonal lines that are exactly 45 degrees. In our coordinate system, that means x and y need to increase or decrease one unit at the time.

expand_all_lines loops over all the lines we have and finds all the individual points for those lines.

def expand_line(line, allow_diagonal=False):
    """
    Expands line from its start and end coordinates to include all points within the line.

    `allow_diagonal: bool` if False, skips lines that are diagonal (part 1)
    """
    points = []

    if line.x1 == line.x2: # Vertical lines
        direction = -1 if line.y1 > line.y2 else 1
        for point in range(line.y1, line.y2 + 1 * direction, direction):
            points.append((line.x1, point))

    elif line.y1 == line.y2: # Horizontal lines
        direction = -1 if line.x1 > line.x2 else 1
        for point in range(line.x1, line.x2 + 1 * direction, direction):
            points.append((point, line.y1))

    elif allow_diagonal: # Diagonal lines
        x_delta = 1 if line.x1 < line.x2 else -1
        y_delta = 1 if line.y1 < line.y2 else -1
        x,y = line.x1, line.y1
        while x != line.x2 and y != line.y2:
            points.append((x,y))
            x += x_delta
            y += y_delta
        points.append((x,y))

    return points


def expand_all_lines(lines, allow_diagonal=False):
    points = []
    for line in lines:
        points += expand_line(line, allow_diagonal)
    return points

Once we have all of our points in a list, we can use standard library's collections.Counter class to create a dictionary where each key is a point and the value is how many times that point exists.

With a filter function how_many_at_least, we filter out all the points that only exists once and count the rest.

from collections import Counter


def count_visits(points):
    return Counter(points)


def how_many_at_least(counts, threshold=2):
    filtered = [point for point in counts if counts[point] >= threshold]
    return len(filtered)

Sometimes Advent of Code gives these nice puzzles where you can reuse the same functions and flow from one part to another, just adding a allow_diagonal flag to second part to get the more complex result.

# Part 1:
expanded_points = expand_all_lines(lines)
counts = count_visits(expanded_points)
part1_result = how_many_at_least(counts)
assert part1_result == 4728 # For refactoring
print(f'Solution, part 1: {part1_result}')

expanded_points = expand_all_lines(lines, allow_diagonal=True)
counts = count_visits(expanded_points)
part2_result = how_many_at_least(counts)

assert part2_result == 17717 # For refactoring
print(f'Solution, part 2: {part2_result}')

Solution, part 1: 4728

Solution, part 2: 17717

Wrap up

Geometry isn't my strongest suit so today I had to pick up my pen and notebook to draw some lines in the coordinate system to see how I'm able to create the points, especially for the four possible diagonal cases (top-left to bottom-right, top-right to bottom-left, bottom-left to top-right and bottom-right to top-left).

The example input and the grid output in the description helped a lot. During the development, I even had a draw function that drew the 10x10 grid with the example input to see which cases my functions were missing:

def draw(counts):
    for y in range(10):
        for x in range(10):
            print(counts.get((x,y), '.'), end='')
        print()

I didn't leave it in the code since it's only feasible for very small grids (and this one even hardcoded to be 10x10).

One of the challenging things with Advent of Code is that due to the large inputs and the only output being a single number or string, it's sometimes really difficult to debug the intermediate steps.

I find Advent of Code's examples and test cases in the puzzles very well made and it's been rare case when those haven't helped me find the missing piece.

10/10 stars for the first week of December in the bag!