Dazbo's Advent of Code solutions, written in Python

ClassesmapcomprehensionssetsBFS / Flood FillMatplotlib

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
```

**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
`Cube`

class that stores the`x,y,z`

coordinate of a given cube in the droplet. The`Cube`

can return coordinates of any adjacent cubes that our connected to our cube’s faces; i.e. excluding any “diagonals”. - Create a
`Droplet`

class 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
`set`

of 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!

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.

- Part of an
- 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.

- For each

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.

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
```

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`

,`z`

bounds. - 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: