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
9899965678
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?
# Python imports
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Tuple
import numpy as np
# Paths to data
testpath = Path("day09_test.txt")
datapath = Path("day09_data.txt")
def load_input(fpath: Path) -> np.array:
"""Return heightmap as numpy array
:param fpath: Path to data file
"""
data = []
with fpath.open("r") as ifh:
for line in [_.strip() for _ in ifh.readlines() if len(_.strip())]:
data.append([int(_) for _ in list(line)])
return np.array(data)
We approach this in an obvious way: check each position in the array to see if it's a minimum with respect to its neighbours.
We choose to produce a Boolean mask, with True values when an element in the array is a minimum. Then we can use this to identify minimum locations, minimum values, and so on.
def get_neighbours(arr: np.array, pos: Tuple[int, int]) -> Generator:
"""Returns generator of neighbour positions in array
:param arr: heightmap array
:param pos: (y, x) co-ordinate in array
"""
posy, posx = pos
ymax, xmax = arr.shape
return ((y, x) for (y, x) in
[(posy + 1, posx), (posy - 1, posx),
(posy, posx - 1), (posy, posx + 1)]
if (ymax > y >= 0 and xmax > x >= 0))
def get_neighbourvals(arr: np.array, pos: Tuple[int, int]) -> Generator:
"""Returns generator of neighbouring values to position in array
:param arr: heightmap array
:param pos: (y, x) co-ordinate in array
"""
return (arr[posy, posx] for (posy, posx) in get_neighbours(arr, pos))
def is_min(arr: np.array, pos: Tuple[int, int]) -> bool:
"""Returns True if position is a minimum value wrt neighbours
:param arr: heightmap array
:param pos: (y, x) co-ordinate in array
"""
return arr[pos[0], pos[1]] < min(get_neighbourvals(arr, pos))
def get_min_mask(arr: np.array) -> np.array:
"""Returns a Boolean mask of minimum values in array
:param arr: heightmap array
Values are true where the element is a minimum
"""
mask = []
for posy in range(arr.shape[0]):
row = []
for posx in range(arr.shape[1]):
pos = (posy, posx)
row.append(is_min(arr, pos))
mask.append(row)
return np.array(mask)
With the test data:
data = load_input(testpath)
mask = get_min_mask(data)
sum(data[mask] + 1) # Sum (value + 1) for each True location in the mask
15
And with the puzzle data:
data = load_input(datapath)
mask = get_min_mask(data)
sum(data[mask] + 1) # Sum (value + 1) for each True location in the mask
558
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:
2199943210
3987894921
9856789892
8767896789
9899965678
The top-right basin, size 9:
2199943210
3987894921
9856789892
8767896789
9899965678
The middle basin, size 14:
2199943210
3987894921
9856789892
8767896789
9899965678
The bottom-right basin, size 9:
2199943210
3987894921
9856789892
8767896789
9899965678
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?
Here, we need to identify members of a basin, and then count the number of elements in that basin.
First, we calculate each basin by starting at the minimum points we found above, and finding its neighbours. These will either be bounds (with a value of 9), or basin elements (everything else). We hold the basin elements in a stack, popping them off one at a time to check their neighbours; we don't check neighbours we know to be in the candidate stack, already in the basin, or in the known bounds. The stack runs out when we've exhausted all possible basin members and their bounds.
def get_basin(arr: np.array, pos: Tuple[int, int]) -> List[Tuple[int, int]]:
"""Returns list of positions in the basin containing the position
:param arr: heightmap array
:param pos: (y, x) co-ordinate in array
"""
basin = [] # basin positions we've seen
bounds = [] # boundary positions we've seen
candidates = [pos] # basin positions whose neighbours we need to check
# When we've exhausted the candidate list, we've seen
# all possible basin elements (and their boundaries)
while len(candidates):
cnd = candidates.pop() # test next basin element
nbrs = get_neighbours(arr, cnd)
for nbr in nbrs:
if arr[nbr[0], nbr[1]] == 9: # is boundary
if nbr not in bounds: # not already seen
bounds.append(nbr) # add to bounds
elif nbr not in basin: # is unchecked basin element
if nbr not in candidates: # is not in wait list
candidates.append(nbr) # add to wait list
basin.append(cnd) # add current basin element to checked list
return basin
def get_basin_sizes(arr: np.array) -> List[int]:
"""Returns sorted list of basin sizes in passed array
:param arr: numpy heightmap
"""
mask = get_min_mask(data) # mask of minimum heights
basinvals = [] # holds basin sizes
# Get the basin elements for each minimum point in the mask,
# count the number of elements, and add that to the list
for (ypos, xpos) in np.transpose(mask.nonzero()):
basinvals.append(len(get_basin(arr, (ypos, xpos))))
return sorted(basinvals, reverse=True)
With the test data:
data = load_input(testpath)
np.prod(get_basin_sizes(data)[:3]) # product of three largest basin sizes
1134
And with the puzzle data:
data = load_input(datapath)
np.prod(get_basin_sizes(data)[:3]) # product of three largest basin sizes
882942