Advent of Code 2021 - Day 5

Day 5: Hydrothermal Venture

Useful Links

‹›

Concepts and Packages Demonstrated

NumPy Dataclass Regular Expressions (regex)classes decorator

NamedTupleCounterpropertymaxgeneratoryieldlambda

Problem Intro

I’ve written two solutions for this problem.

Solution #1 - First, leveraging Numpy
Solution #2 - Secondly, a bit more basic

We’re told there’s a field of hydrothermal vents on the ocean floor. They produce dangerous plumes that we need to avoid. The vents occur in lines. Our input data describes the lines of vents, with each line in the format x1,y1 -> x2,y2. I.e. the (x,y) points that represent the two ends of each line. Here’s some sample input:

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

Part 1

We’re told the vent lines can overlap. Overlapping points are more dangerious. Only considering orthogonal lines (i.e. horizontal and vertical), at how many points do at least two lines overlap?

Solution #1

Here we’re going to use NumPy.

Setup

import logging
import os
import time
import re
from dataclasses import dataclass
import numpy as np

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%Y-%m-%d %H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(level=logging.INFO)

The notable inclusions here are the imports for regular expressions (re), dataclasses, and Numpy.

Solving the Problem

First, we create our Line dataclass:

@dataclass
class Line:
    """ A vertical, horizontal or diagonal line. """
    x1: int
    y1: int
    x2: int
    y2: int
    
    @property
    def is_orthogonal(self) -> bool:
        """ I.e. whether horizontal or vertical line.
        If both x are the same, then horizontal.
        If both y are the same, then vertical. """
        return self.x1 == self.x2 or self.y1 == self.y2

    @property
    def diagonal_down(self) -> bool:
        """ Determine if the diagonal line increases in both x and y axes.
        If it increases in one axis but decreases in the other, then it slopes up. """
        assert not self.is_orthogonal, "Must be diagonal"
        return self.x1 - self.x2 == self.y1 - self.y2

    @property    
    def min_x(self) -> int:
        return min(self.x1, self.x2) 
    
    @property
    def min_y(self) -> int:
        return min(self.y1, self.y2)

    @property
    def max_x(self) -> int:
        return max(self.x1, self.x2)

    @property
    def max_y(self) -> int:
        return max(self.y1, self.y2)

Here we’re using a class to represent Line objects. Python supports object-oriented programming, and consequently allows us create objects. An object is a way to describe something that has properties (attributes) and behviours (methods). A class is like a blueprint, allowing us to create instances of a given type of object. In this case, we’ve created a Line class, allowing us to create individual instances of Line. I.e. each Line is an instance.

We’re also using the dataclass decorator, which tells Python that we want the Line object to be treated as dataclass. This reduces the amount of basic implementation we need to write in the class. E.g. we can simply define the x1, y1, x2 and y2 properties, but we don’t need to write any code to initialise these variables. Note that when we create a Line, we should pass in the variables in the order we’ve defined in them in the dataclass. That’s how dataclasses work! For example:

a_line = Line(x1, y1, x2, y2)

Here’s things that instances of this class knows how to do:

It can tell if it represents a line that is horizontal or vertical. It does this by comparing the two ends. If the two ends have the same x coordinate, then the line must be vertical. If the two ends have the same y coordinate, then the line must be horizontal.
It can tell if it a diagonal line that slopes downwards. (More on this later.)
It can return the minimum/maximum x values of the two ends, and the minimum/maximum y values of the two ends.

Now we can process the input data:

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    data = f.read().splitlines()
    
logger.debug("\n%s", "\n".join(str(vent) for vent in vents))

def process_data(data: list[str]) -> list[Line]:
    """ Parse data of format x1,y1 -> x2,y2 """
    lines = []
    for line in data:
        # get non-overlapping matching groups
        x1, y1, x2, y2 = map(int, re.findall(r"(\d+),(\d+) -> (\d+),(\d+)", line)[0])
        lines.append(Line(x1, y1, x2, y2))
            
    return lines

As usual, we read in the input file, and use splitlines() to split the data into a list, where each item in the list is one line of the input data. We then pass this list of str to our process_data() function. This function uses regular expression parsing to read each line of data.

In the regular express (\d+),(\d+) -> (\d+),(\d+), each (\d+) identifies one or more consecutive digits. Hence, the first pair of (\d+) are used to get one end (x1,y1) of any given line, and the second pair of (\d+) are used to the other end (x2,y2) of the line.

So, we retrieve these four ‘groups’, which get returned as strings. As we’ve done before, we then use map() to convert of these to an int. Finally, we use these four int values to create a new Line, for each row of the input data. We store these lines in a list, and return it.

This line just allows us to print the lines in a nice readable format, i.e. by adding a newline between line of output:

logger.debug("\n".join(str(vent) for vent in vents))

With the sample data, the output from the above line looks something like this:

2022-01-09 20:55:47.397:DEBUG:__main__:
Line(x1=0, y1=9, x2=5, y2=9)
Line(x1=8, y1=0, x2=0, y2=8)
Line(x1=9, y1=4, x2=3, y2=4)
Line(x1=2, y1=2, x2=2, y2=1)
Line(x1=7, y1=0, x2=7, y2=4)
...

The following code:

Determines the maximum x and y values of the field of vents.
Creates a 2D numpy array, with the row length and number of rows given by the max_x and max_y respectively.
Initialises every value in the numpy array to 0. This represents our vent count at each (x,y) location.
Iterates through each of our lines, and for each, passes in the y range and x range for our line, and increments the vent count for the resulting line in the numpy array.
Finally, we use numpy to count all the points in the field where the integer value is >= 2.

    # Get the bottom right coordinate of our x,y field
    max_x = max(vents, key=lambda line: line.max_x).max_x
    max_y = max(vents, key=lambda line: line.max_y).max_y

    field = np.zeros(shape=(max_y+1, max_x+1), dtype=np.int8)   # Initialise field(y, x)
    
    # Part 1: Count how many vents there are at each location, 
    # counting only horizontal and vertical vent lines
    for line in vents:
        if line.is_orthogonal:
            field[line.min_y:line.max_y+1, line.min_x:line.max_x+1] += 1
    
    logger.debug("\n%s", field)
    
    dangerous_vents = np.count_nonzero(field >= 2)
    logger.info("Part 1 dangerous vents: %d", dangerous_vents)

That’s part 1 done!

Part 2

Now we’re told we also need to consider diagonal lines.

# Part 2: Now add diagonal vent lines
for line in vents:
    if not line.is_orthogonal: # diagonal
        for i in range(line.max_y-line.min_y+1):    # length of the line (x len = y len)
            if line.diagonal_down:
                field[line.min_y+i, line.min_x+i] += 1
            else:   # diagonal up
                field[line.max_y-i, line.min_x+i] += 1

dangerous_vents = (field >= 2).sum()    # alternative to count_nonzero
logger.info("Part 2 dangerous vents: %d", dangerous_vents)    

If our line is not orthogonal, then we know it must be diagonal. Our class determines if the diagonal line is sloping down or sloping up by assessing if x1 - x2 == y1 - y2. With diagonal lines, the vertical distance will always be equal to the horizontal distance, i.e. this will always be true: abs(x1-x2) == abs(y1-y2)

But if the line is sloping down, then both sides will be of equal magnitude and both will be negative values. But if the line is sloping upwards, the left side will be negative, whilst the right will be positive.

Once we know this, we step through each coordinate in the line, incrementing the x by 1 each time, and either incrementing the y, if diagonal down, or decrementing y, if diagonal up. For each position position in the numpy array, we increment the vent counter.

And that’s part 2 done.

Output:

2022-01-09 21:15:05.769:INFO:__main__:  Part 1 dangerous vents: 6841
2022-01-09 21:15:06.175:INFO:__main__:  Part 2 dangerous vents: 19258
2022-01-09 21:15:06.176:INFO:__main__:  Execution time: 0.4127 seconds

Solution #2

I decided to write a solution that goes back to basics.

Setup

Similar to before:

from collections import Counter
import logging
import os
import time
import re
from dataclasses import dataclass
from typing import Iterator, NamedTuple

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%Y-%m-%d %H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(level=logging.INFO)

In this case, we’re not using numpy, but we are including the Counter and NamedTuple.

Solving the Problem

First we create a NamedTuple called Point:

class Point(NamedTuple):
    x: int
    y: int

NamedTuple is quite similar to Dataclass. It creates named instances of a tuple, but has the advantage that we can refer to the tuple attributes by name, rather than simply by index.

some_point = (3,5) # a regular tuple
some_point[0] # x coord
some_point[1] # y coord

some_point = Point(3,5) # using our NamedTuple
some_point.x # x coord
some_point.y # y cord

The we create a Line dataclass as before, but with some minor tweaks:

@dataclass
class Line:
    """ A vertical, horizontal or diagonal line. 
    Able to yield all points between p1 and p2, inclusive. """
    p1: Point
    p2: Point
    
    @property
    def is_orthogonal(self) -> bool:
        """ I.e. whether horizontal or vertical line.
        If both x are the same, then horizontal.
        If both y are the same, then vertical. """
        return self.p1.x == self.p2.x or self.p1.y == self.p2.y

    @property
    def diagonal_down(self) -> bool:
        """ Determine if the diagonal line increases in both x and y axes.
        If it increases in one axis but decreases in the other, then it slopes up. """
        assert not self.is_orthogonal, "Must be diagonal"
        return self.p1.x - self.p2.x == self.p1.y - self.p2.y
    
    def points(self) -> Iterator[Point]:
        """ Yield every point from the start of the line (p1) to the end of the line (p2). """
        dx = 0 if self.p2.x == self.p1.x else 1 if self.p2.x > self.p1.x else -1
        dy = 0 if self.p2.y == self.p1.y else 1 if self.p2.y > self.p1.y else -1
        
        point = self.p1
        while point != self.p2:
            yield point
            point = Point(point.x + dx, point.y + dy)
            
        assert point == self.p2
        yield point # the end point

Firstly, since we have our NamedTuple for Point, we can just store two points for each line, rather than storing the x1, x2, y1 and y2 attributes. (It’s the same data… It’s just that using the Point attributes is easier to understand.)

The logic for checking if lines are orthogonal or diagonal down/up are basically the same as before, except using Point references.

The most significant change is that we now have a generator that knows how to yield every Point between the first point and the last point of the line. It does this by determining the delta in x and y for each successive point on the line, depending on whether the line is vertical, horizontal, or diagonal. E.g. if the line is vertical, then dx will always be 0 and dy will always be 1. It stores the latest point, and adds the dx and dy to this point, with every yielding of the next point.

Note that yield works a bit like a return statement, but the method retains its state between each yield execution.

We then read in the data exactly as before.

Part 1 is then solved using this code:

# Part 1: Count how many vents there are at each location
vents_counter = Counter()
for line in vents:
    if line.is_orthogonal:  # only include orthogonal lines
        for point in line.points():
            vents_counter[point] += 1

dangerous_vents = sum(1 for point, count in vents_counter.items() if count >= 2)
logger.info("Part 1 dangerous vents: %d", dangerous_vents)

The code works by:

Setting up a new Counter.
Iterating through each Line. If the line is orthononal, we yield each point on the line, store the point in the counter, and increment the vent count at each point.

For part 2, the code is identical, except we no longer need to check if the line is orthogonal.

# Part 2
vents_counter = Counter()    
for line in vents:
    for point in line.points():
        vents_counter[point] += 1

Onwards!

‹›