Advent of Code - 2021
This is a solution to Day 9 of Advent of Code 2021.
Day 9 - Smoke Basin
These caves seem to be lava tubes. Parts are even still volcanically active; small hydrothermal vents release smoke into the caves that slowly settles like rain.
If you can model how the smoke flows through the caves, you might be able to avoid it and be that much safer. The submarine generates a heightmap of the floor of the nearby caves for you (your puzzle input).
Smoke flows to the lowest point of the area it's in. For example, consider the following heightmap:
2199943210 3987894921 9856789892 8767896789 9899965678Each number corresponds to the height of a particular location, where 9 is the highest and 0 is the lowest a location can be.
Your first goal is to find the low points - the locations that are lower than any of its adjacent locations. Most locations have four adjacent locations (up, down, left, and right); locations on the edge or corner of the map have three or two adjacent locations, respectively. (Diagonal locations do not count as adjacent.)
In the above example, there are four low points, all highlighted: two are in the first row (a 1 and a 0), one is in the third row (a 5), and one is in the bottom row (also a 5). All other locations on the heightmap have some lower adjacent location, and so are not low points.
The risk level of a low point is 1 plus its height. In the above example, the risk levels of the low points are 2, 1, 6, and 6. The sum of the risk levels of all low points in the heightmap is therefore 15.
Finally a easy-to-understand, short description! I'm excited.
I recently mentored a junior with a similar kind of problem (for a completely different problem domain, bitmap rendering) so this seems fun.
from utils import read_input
def transformer(input_line):
return [int(num) for num in list(input_line)]
heightmap = read_input(9, transformer)
Part 1
Find all of the low points on your heightmap. What is the sum of the risk levels of all low points on your heightmap?
First mistake I made that caused a bit of trouble in part 2, even though it somehow gave me the right result here, was that I didn't realize diagonal neighbors didn't count.
So originally I had all the (up to) 8 neighbors counted.
For a more simplified solution, I wrote out all 4 neighbor positions and then depending on the corner cases (top, bottom, left and right), removed once that are not part of the heightmap.
Itertools
Today's Python library spotlight goes to itertools which contains a selection of methods that generate iterators.
Here we use product which takes two iterables and returns a cartesian product of those. It's very handy for generating (i,j) coordinates:
import itertools
itertools.product([1,2], [3,4])
##[(1, 3), (1, 4), (2, 3), (2, 4)]
Other great tools from itertools are permutations and combinations. Both take a list (or any other iterable) and an integer as parameters and generate iterables. permutations creates all combinations of length provided and combinations does the same but in sorted order (for example, considering (1,2) and (2,1) as same.
import itertools
letters = ['A', 'B', 'C']
itertools.permutations(letters, 2)
##[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
itertools.combinations(letters, 2)
##[('A', 'B'), ('A', 'C'), ('B', 'C')]
One of the newest additions to the library in Python 3.10 is pairwise which is basically a two-item window function (a three-item window function would have been handy in puzzle for day 1).
import itertools
itertools.pairwise([1,2,3,4])
##[(1, 2), (2, 3), (3, 4)]
import itertools
def find_neighbors(heightmap, indices):
i, j = indices
all_neighbors = [
(i, j+1),
(i, j-1),
(i-1, j),
(i+1, j)
]
top = i == 0
bottom = i == len(heightmap) - 1
left = j == 0
right = j == len(heightmap[i]) - 1
# Remove impossible indices (out of bounds)
if top: all_neighbors.remove((i-1, j))
if bottom: all_neighbors.remove((i+1, j))
if left: all_neighbors.remove((i, j-1))
if right: all_neighbors.remove((i, j+1))
return all_neighbors
def find_low_points(heightmap):
low_points = []
i_len = len(heightmap)
j_len = len(heightmap[0])
for (i,j) in itertools.product(range(i_len), range(j_len)):
neighbors = find_neighbors(heightmap, (i, j))
height = heightmap[i][j]
if all(heightmap[n][m] > height for n, m in neighbors):
low_points.append((i, j))
return low_points
low_points = find_low_points(heightmap)
result = sum([heightmap[i][j] + 1 for i,j in low_points])
print(f'Solution: {result}')
assert result == 545 # For refactoring
Solution: 545
Part 2
Next, you need to find the largest basins so you know what areas are most important to avoid.
A basin is all locations that eventually flow downward to a single low point. Therefore, every low point has a basin, although some basins are very small. Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.
The size of a basin is the number of locations within the basin, including the low point. The example above has four basins.
Editor's note: these basins don't show up in my markdown.
The top-left basin, size 3:
2199943210 3987894921 9856789892 8767896789 9899965678The top-right basin, size 9:
2199943210 3987894921 9856789892 8767896789 9899965678The middle basin, size 14:
2199943210 3987894921 9856789892 8767896789 9899965678The bottom-right basin, size 9:
2199943210 3987894921 9856789892 8767896789 9899965678Find the three largest basins and multiply their sizes together. In the above example, this is
9 * 14 * 9 = 1134.
This one was really hard for me. I was running in circles for hours trying to figure this one out and eventually I got so much help from Vilho and Erno (thanks guys!) that this was 99% their solution and 1% me trying to write it down.
It uses breadth-first search algorithm to find basins and to calculate their areas. Not my strongest expertise, I think this was probably the first time I've implemented such a solution. Even when I was told kinda how to solve it, I still struggled to get the pieces in right order.
def calculate_basin_area(coords, heightmap, visited):
(i, j) = coords
if visited[i][j]:
return 0
visited[i][j] = True
if heightmap[i][j] == 9: # By definition, values of 9 are not part of any basins
return 0
area = 1
neighbors = find_neighbors(heightmap, (i, j))
for (m, n) in neighbors:
area += calculate_basin_area((m, n), heightmap, visited)
return area
What do you get if you multiply together the sizes of the three largest basins?
Here we find all the low points using the solution from Part 1.
Then for each of those, we find the area of the basin they belong to and collect those in a list basins.
Finally, to get the product of three largest, we sort descending (sorted(basins, reverse=True)), pick three ([:3]) and then calculate their product.
low_points = find_low_points(heightmap)
visited = [[None for _ in range(len(heightmap[i]))] for i in range(len(heightmap))]
basins = []
for (i, j) in low_points:
basins.append(calculate_basin_area((i,j), heightmap, visited))
three_largest = sorted(basins, reverse=True)[:3]
result = three_largest[0] * three_largest[1] * three_largest[2]
print(f'Solution: {result}')
assert result == 950600
Solution: 950600
Wrap up
Usually around this point, after the first week, the solutions get more math and data structure trivia heavy and my toolbox as a generic web developer starts to run out. Even when I kinda know which structures and algorithms could be usable, my ability to implement them with practical results is very limited.
The good part is, those things rarely matter at work unless working with math-heavy sub sections of software development. As a web developer, you can get along very well with pretty much the very basics of understanding algorithm complexity and choosing between lists, sets and dictionaries, and avoiding nested loops.
Let's see if Day 10 is where my journey stops or if there's still some fun stuff to do.