[Advent of Code 2021] Day 9

Part 1

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:

Each 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_.

Find all of the low points on your heightmap. What is the sum of the risk levels of all low points on your heightmap?

Proposed solution: iterate through the height-map and check all adjacent locations – if it is a low point, add it's risk level to the total

Time complexity: O(n)

Space complexity: O(1)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

heightmap = {}
for y, line in enumerate(file_input):
    for x, val in enumerate(line):
        heightmap[x,y] = int(val)

total = 0
for (x, y), val in heightmap.items():
    low = True
    for dx in [-1,1]:
        if (x + dx, y) in heightmap and heightmap[x+dx,y] <= val:
            low = False
    for dy in [-1,1]:
        if (x, y + dy) in heightmap and heightmap[x,y+dy] <= val:
            low = False
    if low:
        total += 1 + val

print("Risk Level: " + str(total))

We keep an extra data structure but we could make this O(1) extra space

❯ python3 solution9.py input9
Risk Level: 560

Piece of cake

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.

The top-left basin, size 3:

The top-right basin, size 9:

The middle basin, size 14:

The bottom-right basin, size 9:

Find the three largest basins and multiply their sizes together. In the above example, this is 9 * 14 * 9 = _1134_.

What do you get if you multiply together the sizes of the three largest basins?

Proposed solution: iterate through every position in the height-map (this will be the start position) – skip if value is 9 (not basin) or already visited (track all of these); do depth-first search for the current basin and its size for each starting position; when current basin is traversed, push result onto heap

Time complexity: O(n)

Space complexity: O(n)

Appending the new logic to part 1:

from collections import deque
from functools import reduce
import heapq

...

basin_queue = deque()
visited = set()
largest_basins = []
for (x, y), val in heightmap.items():
    if val == 9 or (x, y) in visited:
        continue
    basin_queue.clear()
    basin_queue.append((x,y))
    basin_length = 0
    while len(basin_queue) != 0:
        x1, y1 = basin_queue.pop()
        if (x1, y1) in visited:
            continue
        basin_length += 1
        visited.add((x1,y1))
        for dx in [-1,1]:
            check = (x1 + dx, y1)
            if check in heightmap and heightmap[check] != 9:
                basin_queue.append(check)
        for dy in [-1,1]:
            check = (x1, y1 + dy)
            if check in heightmap and heightmap[check] != 9:
                basin_queue.append(check)
    heapq.heappush(largest_basins, basin_length)

largest = reduce(lambda x, y: x * y, heapq.nlargest(3, largest_basins))
print("Risk Level: " + str(total))
print("Largest Basins: " + str(largest))

Depth-first search for basins

Breaking this down, iterate through the starting positions. Every time this hits a position that is part of a basin (not 9) and not visited yet, it will traverse through the entire basin and will populate the size in the heap.

basin_queue = deque()
visited = set()
largest_basins = []
for (x, y), val in heightmap.items():
    if val == 9 or (x, y) in visited:
        continue

Iterate through starting positions skipping non-basins and already visited

basin_queue is cleared each time and is the stack (yes, poorly named for its usage) that keeps track of the remaining vertices of the search. I don't think the .clear() is necessary since it should be empty every time that line is reached. Append the starting position and search!

    basin_queue.clear()
    basin_queue.append((x,y))
    basin_length = 0
    while len(basin_queue) != 0:
        x1, y1 = basin_queue.pop()
        if (x1, y1) in visited:
            continue
        basin_length += 1
        visited.add((x1,y1))

DFS loop tracking basin size and visited

Search involves adding all adjacent vertices (no diagonals) that are not visited and part of the basin. Check for visited above are probably not necessary here since it shouldn't reach this point if the start position (and its corresponding basin) were all visited.

        for dx in [-1,1]:
            check = (x1 + dx, y1)
            if check in heightmap and heightmap[check] != 9:
                basin_queue.append(check)
        for dy in [-1,1]:
            check = (x1, y1 + dy)
            if check in heightmap and heightmap[check] != 9:
                basin_queue.append(check)

DFS - add all adjacent vertices to stack

Using a heap to track the sizes of the basin makes it really simple to get the nlargest which we need to multiply all together. We could have used math.prod here but I tried it with reduce instead.

    heapq.heappush(largest_basins, basin_length)

largest = reduce(lambda x, y: x * y, heapq.nlargest(3, largest_basins))

DFS - track basin sizes after each basin DFS and reduce after all are done

This solution is O(n) time complexity. We don't need to include edges/vertices in the complexity notation because every vertex has at most 4 edges (all non-diagonal adjacent locations) so this can be considered constant – or as part of the vertices since they scale at the same rate. Also, if we did not keep track of already visited vertices, we would end up with an O(nⁿ) solution so this is important and why we need the extra O(n) space complexity.

❯ python3 solution9.py input9
Risk Level: 560
Largest Basins: 959136

Fast :)

[Advent of Code 2021] Day 9 | Smoke Basin

Part 1

Part 2