How to solve Advent of Code 2021 – Day 5 [Python]

Confused? Check out my Day 1 post to read all about Advent of Code here: https://galaxyinferno.com/how-to-solve-advent-of-code-2021-day-1/

GitHub

https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2021

This is where I will upload all of my Python Notebooks where I solve the challenges. I’m solving them on Google Colab, because that allows me to just quickly throw something together in the Browser on any machine I’m on. Since I’m lazy, that’s my go-to for quick and small projects. Otherwise I code in VSCode 🙂

Day 5 Puzzle

Here is the challenge, if you want to read the full puzzle: https://adventofcode.com/2021/day/5

On Day 5 we are trying to avoid hydrothermal vents on the ocean floor, about which we are given information in the following form:

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

Each line describes a start and end point on a coordinate-grid like: x1,y1 -> x2,y2. The points at the end of these lines (x2, y2) are included.

Part 1

We need to keep track of these lines and then find out on how many points in the grid, there is high danger, classified as having two or more vents/lines there. In programming terms this means, we create a grid and increase the counter of each coordinate when we know a line passes through this point. Then we can read off how many entries with a value bigger or equal to 2 there are.

First, we read in the lines from a text file called file_name as always. Then we create the grid.

Processing one line: Honestly one of the hardest parts of this day was reading in the coordinates from the text file. This might be because I have a lot of experience with puzzle/problem solving and little experience in processing text files :D Anyways, after a lot of thinking, I did end up using regular expressions (imported with the re module), even though reading anything with regular expressions is super ugly and unintuitive:

re.sub('[^0-9]', ' ', line).split()

This replaces everything except for 0-9 (so digits) with a whitespace. Afterwards the string '0,9 -> 5,9' is just '0 9 5 9', which can then be split into ['0', '9', '5', '9'].

Using this, we loop through all lines and find the maximum x and y coordinates, which we use to create a numpy array with that size (adding 1, because the biggest index is inclusive, which means it needs to appear on the board and with 0-indexing we need an array size of the biggest entry+1). Another thing to keep in mind is that y is the row index and x is the column index if you want to compare your grid to the one on the Advent Of Code website.

with open(file_name, 'r') as f:
    lines = f.readlines()
    lines = [entry.strip() for entry in lines]

max_x = 0
max_y = 0
for line in lines:
    x1, y1, x2, y2 = [int(entry)
                      for entry in re.sub('[^0-9]', ' ', line).split()]
    max_x = max(max_x, x1, x2)
    max_y = max(max_y, y1, y2)

print('max x', max_x, 'max y', max_y)
grid = np.zeros((max_y+1, max_x+1), dtype=int)

Part 1 is now fairly easy, we just enter all horizontal and vertical lines by simply looping through the one dimension that changes. To ensure that we can always increase the varying value, we start at the minimum and go up to the maximum (because in the text file the first entry could be bigger than the second, which would ruin our loop):

def enter_line(grid, x1, y1, x2, y2):
    if x1 == x2:
        for y in range(min(y1, y2), max(y1, y2)+1):
            grid[y, x1] += 1
    if y1 == y2:
        for x in range(min(x1, x2), max(x1, x2)+1):
            grid[y1, x] += 1

for line in lines:
    x1, y1, x2, y2 = [int(entry) for entry in re.sub('[^0-9]', ' ', line).split()]
    enter_line(grid, x1, y1, x2, y2)
print('score', (grid >= 2).sum())

At the end we compare the grid with 2 and use the .sum() function to count the True entries, because True equals 1 and summing those up is the equivalent of counting.

Part 2

Of course it was too good to be true to only consider the horizontal and vertical lines... So now we also need to consider diagonal lines. Thankfully, we are assured that there are only diagonal lines with a 45 degree angle, which means we will always change the x and y value by exactly 1 for each step. The only question is if we are going up or down in each direction. We save this direction in step_x and step_y and then we're good to loop through the line length (which we can determine through the x or y coordinates because both are equally far apart):

def enter_line_extended(grid, x1, y1, x2, y2):
    if x1 == x2:
        for y in range(min(y1, y2), max(y1, y2)+1):
            grid[y, x1] += 1
        return
    if y1 == y2:
        for x in range(min(x1, x2), max(x1, x2)+1):
            grid[y1, x] += 1
        return
    # I guess all lines here have to be diagonal
    line_length = abs(x1-x2)+1
    step_x = 1 if x2-x1 > 0 else -1
    step_y = 1 if y2-y1 > 0 else -1
    for i in range(line_length):
        new_x = x1 + i*step_x
        new_y = y1 + i*step_y
        grid[new_y, new_x] += 1

The rest of the code stays the same, we just use this updated enter_line_extended function now.

Conclusion

This took embarrassingly long, because I kept having issues where my line was off by one and then my grid was flipped because I had assumed that x was the row index and so on. But in the end it worked out and I practiced my regular expression skills :D