Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 18
Useful Links
Concepts and Packages Demonstrated
ClassesmapcomprehensionssetsBFS / Flood FillMatplotlib
Page Navigation
Problem Intro
In today’s puzzle, we’re told that the volcano is erupting and lava droplets are falling into a pond. We’re examining the surface area of a lava droplet. Our input data is a set of x,y,z coordinates the represent 1x1x1 cubes that make up the lava droplet. The data looks like this:
2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
Part 1
What is the surface area of your scanned lava droplet?
We need to count the cube faces that are not connected to any other cubes.
My strategy:
- Create a
Cubeclass that stores thex,y,zcoordinate of a given cube in the droplet. TheCubecan return coordinates of any adjacent cubes that our connected to our cube’s faces; i.e. excluding any “diagonals”. - Create a
Dropletclass that stores all the cubes of our droplet and knows how to return the total surface area of the cubes it contains.
Here’s the Cube class:
@dataclass(frozen=True)
class Cube():
""" Cube with three dimensions and knows how to return Cube locations at adjacent faces. """
x: int
y: int
z: int
# To generate deltas only for faces, we need two of three dims to be 0
ADJ_DELTAS = [(dx,dy,dz) for dx in range(-1, 1+1)
for dy in range(-1, 1+1)
for dz in range(-1, 1+1)
if (dx, dy, dz).count(0) == 2]
def adjacent(self):
return {Cube(self.x+dx, self.y+dy, self.z+dz) for dx, dy, dz in Cube.ADJ_DELTAS}
As usual, I’m using a dataclass to remove the need for boilerplate code. The cool bit here is how the class determines all the locations of adjacent cubes. If we were to simply return all coordinates within 1 unit of our cube, we would end up with 27 new cubes, i.e. a 3x3x3 cube, containing our original cube in the middle. But to return only cubes that are adjacent to a face of our original cube, we only want cube locations where the two of the coordinates are the same as our original cube, and where the third coordinate is 1 away from our original cube. As you would expect, there are only 6 such cubes, since a cube only has 6 faces. I.e.
ADJ_DELTAS = [(dx,dy,dz) for dx in range(-1, 1+1)
for dy in range(-1, 1+1)
for dz in range(-1, 1+1)
if (dx, dy, dz).count(0) == 2]
print(len(ADJ_DELTAS))
print(ADJ_DELTAS)
Output:
6
[(-1, 0, 0), (0, -1, 0), (0, 0, -1), (0, 0, 1), (0, 1, 0), (1, 0, 0)]
The adjacent() method simply takes these six coordinate deltas, and creates six new cubes from them. It returns these six cubes as a set.
Now we can read in our input data, which is trivial to do:
def parse_cubes(data: list[str]) -> set[Cube]:
cubes = set()
for line in data:
coords = tuple(map(int, line.split(",")))
cubes.add(Cube(*coords))
return cubes
For each row, I split at the comma to give us three numerical values. I use map() to convert each of these values to an int.
Let’s now look at the Droplet class:
@dataclass
class Droplet():
""" Droplet is a volume of 1x1x1 cubes """
ADJACENT_FACES = 6
filled_cubes: set[Cube]
def __post_init__(self) -> None:
self._all_surface_area: int = 0 # surface area, internal+external
self._calculate_values()
@property
def all_surface_area(self):
return self._all_surface_area
def __repr__(self) -> str:
return (f"Droplet(filled_cubes={len(self.filled_cubes)})")
def _calculate_values(self):
""" Determine total surface area of all filled positions """
for filled_cube in self.filled_cubes:
self._all_surface_area += Droplet.ADJACENT_FACES - len(self.filled_cubes & filled_cube.adjacent())
As you can see, this is pretty simple. Note that this is once again a dataclass, and as a result, I don’t want to override the __init__() method that dataclass provides for us. Instead, I’ve overridden the __post_init__() method, which allows us to do some initialisation after the implicit __init__() has run. For Part 1, all we do here is call the _calculate_values() method. This method:
- Iterates through every filled cube in the droplet. (I.e. our input data.)
- For each one, determine its adjacent cubes and return the intersection of these adjacent cubes with our
setof filled cubes. Whenever this intersection occurs, this particular face has an adjacent cube and can’t be counted towards the total surface area. The total surface area for any given cube is 6, so we subtract the intersection count from 6 to give us the number of exposed faces for this cube.
That part was easy!
Part 2
This part is not so easy!
Now we’re told that our droplet contains one or more internal empty volumes that have no route to the surface of the droplet. We’re told that we need to exclude the surface area of these internal volumes from our calculation.
What is the exterior surface area of your scanned lava droplet?
Here, we define external surface area as any cube faces that are exposed to empty space that is not part of sealed internal volume.
The tricky part is how we determine if an “empty” cube (i.e. any location that is not part of our input data) has a path to the “outside” or not.
Here’s my strategy:
- Find all adjacent cubes to our _filled” cubes. These are either:
- Part of an internal pocket. If we flood fill a pocket, it will have a nearby boundary.
- Part of path to the outside. If we flood fill, we will eventually reach a cube beyond all the droplet bounds.
- To solve:
- For each filled cube, get its adjacent cubes.
- Perform a Breadth-First Search (BFS) from each adacent, if the adjacent cube is empty space.
- If the BFS only leads to filled cubes, then all paths are blocked, so this cube is internal.
- If the BFS leads to cubes that our outside of our bounds, then this cube has a path to the outside. Thus, this cube counts as external.
- Store all paths to cache the BFS.
- Only increment the surface area count every time we find an adjacent location that has a path out, i.e. only for cubes that are external.
Here’s our modified Droplet class:
@dataclass
class Droplet():
""" Droplet is a volume of 1x1x1 cubes """
ADJACENT_FACES = 6
filled_cubes: set[Cube]
def __post_init__(self) -> None:
# Store max bounds, so we can tell if we've followed a path beyond the perimeter
self._min_x = self._min_y = self._min_z = 0
self._max_x = self._max_y = self._max_z = 0
self._all_surface_area: int = 0 # surface area, internal+external
self._calculate_values()
@property
def all_surface_area(self):
return self._all_surface_area
def __repr__(self) -> str:
return (f"Droplet(filled_cubes={len(self.filled_cubes)})")
def _calculate_values(self):
""" Determine:
- Total surface area of all filled positions
- Outer boundaries (min/max x/y/z values) for the droplet.
"""
for filled_cube in self.filled_cubes:
self._all_surface_area += Droplet.ADJACENT_FACES - len(self.filled_cubes & filled_cube.adjacent())
self._min_x = min(filled_cube.x, self._min_x)
self._min_y = min(filled_cube.y, self._min_y)
self._min_z = min(filled_cube.z, self._min_z)
self._max_x = max(filled_cube.x, self._max_x)
self._max_y = max(filled_cube.y, self._max_y)
self._max_z = max(filled_cube.z, self._max_z)
def get_external_surface_area(self) -> int:
""" Determine surface area of all cubes that can reach the outside. """
cubes_to_outside = set() # cache cubes we have already identified a path to outside for
no_path_to_outside = set() # store all internal empty
surfaces_to_outside = 0
# Loop through the cubes and find any that can reach outside
for cube in self.filled_cubes:
for adjacent in cube.adjacent(): # for each adjacent...
if self._has_path_to_outside(adjacent, cubes_to_outside, no_path_to_outside):
cubes_to_outside.add(adjacent)
surfaces_to_outside += 1
else:
no_path_to_outside.add(adjacent)
return surfaces_to_outside
def _has_path_to_outside(self, cube: Cube,
cubes_to_outside: set[Cube],
no_path_to_outside: set[Cube]) -> bool:
""" Perform BFS to flood fill from this empty cube.
Param cubes_to_outside is to cache cubes we've seen before, that we know have a path.
Param internal_cubues is to cache cubes we've seen before, that are internal. """
frontier = deque([cube])
explored = {cube}
while frontier:
current_cube = frontier.popleft() # FIFO for BFS
# Check caches
if current_cube in cubes_to_outside:
return True # We've got out from here before
if current_cube in no_path_to_outside:
continue # This cube doesn't have a path, so no point checking its neighbours
if current_cube in self.filled_cubes:
continue # This path is blocked
# Check if we've followed a path outside of the bounds
if current_cube.x > self._max_x or current_cube.y > self._max_y or current_cube.z > self._max_z:
return True
if current_cube.x < self._min_x or current_cube.y < self._min_y or current_cube.z < self._min_z:
return True
# We want to look at all neighbours of this empty space
for neighbour in current_cube.adjacent():
if neighbour not in explored:
frontier.append(neighbour)
explored.add(neighbour)
return False
The implementation of the BFS is standard, and we’ve covered this before. The only other thing worth noting here is how we define the bounds that we use to determine if our BFS has reached “outside”. To set these bounds, we simply measure the minimum and maximum values of each of x, y, and z, from our set of filled cubes. If our BFS ever reaches a cube where any of the cube coordinates are beyond these boundaries, then we know we’ve reached “empty space” outside of the perimeter of our droplet.
Results
Here’s the final code:
from __future__ import annotations
from collections import deque
from dataclasses import dataclass
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Cube():
""" Cube with three dimensions and knows how to return Cube locations at adjacent faces. """
x: int
y: int
z: int
# To generate deltas only for faces, we need two of three dims to be 0
ADJ_DELTAS = [(dx,dy,dz) for dx in range(-1, 1+1)
for dy in range(-1, 1+1)
for dz in range(-1, 1+1)
if (dx, dy, dz).count(0) == 2]
def adjacent(self):
return {Cube(self.x+dx, self.y+dy, self.z+dz) for dx, dy, dz in Cube.ADJ_DELTAS}
@dataclass
class Droplet():
""" Droplet is a volume of 1x1x1 cubes """
ADJACENT_FACES = 6
filled_cubes: set[Cube]
def __post_init__(self) -> None:
# Store max bounds, so we can tell if we've followed a path beyond the perimeter
self._min_x = self._min_y = self._min_z = 0
self._max_x = self._max_y = self._max_z = 0
self._all_surface_area: int = 0 # surface area, internal+external
self._calculate_values()
@property
def all_surface_area(self):
return self._all_surface_area
def __repr__(self) -> str:
return (f"Droplet(filled_cubes={len(self.filled_cubes)})")
def _calculate_values(self):
""" Determine:
- Total surface area of all filled positions
- Outer boundaries (min/max x/y/z values) for the droplet.
"""
for filled_cube in self.filled_cubes:
self._all_surface_area += Droplet.ADJACENT_FACES - len(self.filled_cubes & filled_cube.adjacent())
self._min_x = min(filled_cube.x, self._min_x)
self._min_y = min(filled_cube.y, self._min_y)
self._min_z = min(filled_cube.z, self._min_z)
self._max_x = max(filled_cube.x, self._max_x)
self._max_y = max(filled_cube.y, self._max_y)
self._max_z = max(filled_cube.z, self._max_z)
def get_external_surface_area(self) -> int:
""" Determine surface area of all cubes that can reach the outside. """
cubes_to_outside = set() # cache cubes we have already identified a path to outside for
no_path_to_outside = set() # store all internal empty
surfaces_to_outside = 0
# Loop through the cubes and find any that can reach outside
for cube in self.filled_cubes:
for adjacent in cube.adjacent(): # for each adjacent...
if self._has_path_to_outside(adjacent, cubes_to_outside, no_path_to_outside):
cubes_to_outside.add(adjacent)
surfaces_to_outside += 1
else:
no_path_to_outside.add(adjacent)
return surfaces_to_outside
def _has_path_to_outside(self, cube: Cube,
cubes_to_outside: set[Cube],
no_path_to_outside: set[Cube]) -> bool:
""" Perform BFS to flood fill from this empty cube.
Param cubes_to_outside is to cache cubes we've seen before, that we know have a path.
Param internal_cubues is to cache cubes we've seen before, that are internal. """
frontier = deque([cube])
explored = {cube}
while frontier:
current_cube = frontier.popleft() # FIFO for BFS
# Check caches
if current_cube in cubes_to_outside:
return True # We've got out from here before
if current_cube in no_path_to_outside:
continue # This cube doesn't have a path, so no point checking its neighbours
if current_cube in self.filled_cubes:
continue # This path is blocked
# Check if we've followed a path outside of the bounds
if current_cube.x > self._max_x or current_cube.y > self._max_y or current_cube.z > self._max_z:
return True
if current_cube.x < self._min_x or current_cube.y < self._min_y or current_cube.z < self._min_z:
return True
# We want to look at all neighbours of this empty space
for neighbour in current_cube.adjacent():
if neighbour not in explored:
frontier.append(neighbour)
explored.add(neighbour)
return False
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
droplet = Droplet(parse_cubes(data))
print(droplet)
# Part 1
print(f"Part 1: all surface area={droplet.all_surface_area}")
# Part 2
external_faces = droplet.get_external_surface_area()
print(f"Part 2: external surface area={external_faces}")
def parse_cubes(data: list[str]) -> set[Cube]:
cubes = set()
for line in data:
coords = tuple(map(int, line.split(",")))
cubes.add(Cube(*coords))
return cubes
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
Output:
Droplet(filled_cubes=2830)
Part 1: all surface area=4320
Part 2: external surface area=2456
Execution time: 5.5206 seconds
Visualisation
Finally, let’s render an image of our droplet using Matplotlib. We just need to add this method to our Droplet class:
def vis(self):
""" Render a visualisation of our droplet """
axes = [self._max_x+1, self._max_y+1, self._max_z+1] # set bounds
grid = np.zeros(axes, dtype=np.int8) # Initialise 3d grid to empty
for point in self.filled_cubes: # set our array to filled for all filled cubes
grid[point.x, point.y, point.z] = 1
facecolors = np.where(grid==1, 'red', 'black')
# Plot figure
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.voxels(grid, facecolors=facecolors, edgecolors="grey", alpha=0.3)
ax.set_aspect('equal')
plt.axis("off")
plt.show()
All we’re doing here is:
- Generating a NumPy ndarray with the appropriate
x,y,zbounds. - Set all the values in the ndarray to 0 using
np.zeros. - For any location where we have a “filled” cube, set the value in the ndarray to 1.
- Set the colour to red for these filled cubes.
- Render the plot using voxels, i.e. a built-in Matplotlib method for plotting 1x1x1 cubes.
And the image rendered looks like this:
