Advent of Code: Year 2020, Day 17
Today was almost exactly like day 11 except with more dimensions. If you remember from day 11, the Raku solution was so slow that I had to write a Python solution (with the same logic) to get it to finish in a reasonable amount of time. Because of the similarities between today’s problem and that one, I only wrote a Python solution today.
The Problem
Part 1
The elves back at the North Pole call us about a mysterious phenomenon they are witnessing called Conway Cubes occurring in a pocket dimension.
The pocket dimension consists of an infinite 3D grid. At each (x, y, z)
coordinate there exists a cube in an active (#
) or inactive (.
) state. Every cycle in the phenomenon all the cubes simultaneously look at their 26 neighbors (9 above, 9 below, 8 in-plane) and they change based on the following rules:
- If a cube is active and exactly 2 or 3 of its neighbors are also active, the cube remains active. Otherwise, the cube becomes inactive.
- If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive.
Our input is a 2D grid where the top-left position corresponding to coordinate (0,0,0)
with some active and some inactive cubes. After 6 cycles of the pattern listed above, how many cubes in the space are active?
Solution
See below for explanation and any implementation-specific comments.
from collections import defaultdict
from itertools import product
import sys
def neighbors(coordinates):
for diff in product([-1, 0, 1], repeat=len(coordinates)): # [1]
yield tuple(coordinate + diff[i] for i, coordinate in enumerate(coordinates))
def conway_cubes(initial):
space = defaultdict(lambda: '.') # [2]
for x, line in enumerate(initial):
for y, state in enumerate(line):
cube = (x, y, 0)
space[cube] = state
for _ in range(6):
active = defaultdict(int) # [3]
for cube in space:
if space[cube] == ".":
continue
for neighbor in neighbors(cube):
# We count active cubes with active neighbors so we can
# activate/deactivate following as necessary in the next loop
active[neighbor] += 1 if neighbor != cube else 0
for cube, active_neighbors in active.items():
if space[cube] == "#" and active_neighbors not in (2, 3):
space[cube] = "."
elif space[cube] == "." and active_neighbors == 3:
space[cube] = "#"
return sum(state == "#" for state in space.values())
if __name__ == '__main__':
initial = [line.strip() for line in open(sys.argv[1]).readlines()]
print(conway_cubes(initial))
This runs as such:
$ python day17.py input.txt
137
Explanation
The logic here is pretty simple:
- We have an infinite grid called
space
and we set our initial values in the(x, y, 0)
plane. - For 6 cycles we iterate through the cubes focusing first on active cubes (since the rules apply to active neighbors).
- Within each cycle we do a second loop to look at our neighbors
- If a cube is active and fewer than 2 or greater than 3 neighbors are inactive, it becomes inactive.
- If a cube is inactive and exactly 3 neighbors are active, it becomes active.
- After 6 cycles of this, we simply sum up the active cubes.
Specific Comments
product
is a Python 3.8+ function that is basically the equivalent of Raku’sX
operator. In this case, therepeat
param means to use the same inputrepeat
times. So ifrepeat=3
, in this case, it would be the same as[-1, 0, 1] X [-1, 0, 1] X [-1, 0, 1]
.- A
defaultdict
is a great data structure for an infinite grid. Basically, the key tospace
will be a tuple of coordinates, and the value will either be a period or a hash. Since it is adefaultdict
, if we reference a key that does not exist, it creates it and fills it in with the default value ('.'
). - We also use a
defaultdict
to track our active cubes, with the default being anint
. This will create new items with the default being0
(defaultdict
accepts a function, not a value, which is why we can’t just specify0
).
Part 2
Turns out the pocket dimension is actually four dimensional. Our input now represents the plane (x, y, 0, 0)
. How many cubes are active after 6 cycles in 4D?
Solution
See below for explanation and any implementation-specific comments.
from collections import defaultdict
from itertools import product
import sys
def neighbors(coordinates):
for diff in product([-1, 0, 1], repeat=len(coordinates)):
yield tuple(coordinate + diff[i] for i, coordinate in enumerate(coordinates))
def conway_cubes(initial, dimensions):
space = defaultdict(lambda: '.')
padding = (0,) * (dimensions - 2)
for x, line in enumerate(initial):
for y, state in enumerate(line):
cube = (x, y) + padding
space[cube] = state
for _ in range(6):
active = defaultdict(int)
for cube in space:
if space[cube] == ".":
continue
for neighbor in neighbors(cube):
# We count active cubes with active neighbors so we can
# activate/deactivate following as necessary in the next loop
active[neighbor] += 1 if neighbor != cube else 0
for cube, active_neighbors in active.items():
if space[cube] == "#" and active_neighbors not in (2, 3):
space[cube] = "."
elif space[cube] == "." and active_neighbors == 3:
space[cube] = "#"
return sum(state == "#" for state in space.values())
if __name__ == '__main__':
initial = [line.strip() for line in open(sys.argv[1]).readlines()]
print(f'Part 1: {conway_cubes(initial, dimensions=3)}')
print(f'Part 2: {conway_cubes(initial, dimensions=4)}')
This runs as such:
$ python day17.py input.txt
Part 1: 237
Part 2: 2448
Explanation
The changes here are so small, you may not even notice them:
conway_cubes
now accepts a dimension argument- We have a dynamic
padding
variable that adds either 1 or 2 zeros to the supplied(x, y)
coordinates (rather than hard-coding as we did in part one). - We run both parts (CLIs are much easier in Raku, so I don’t bother in Python)
That’s it!
Specific Comments
No specific comments to add because the code barely changed. Luckily the code was generalized enough to handle the new dimension.
Final Thoughts
I didn’t write a Raku solution, but I wonder how fast (or slow) if I wrote one with the same logic. Maybe I will go back and compare one of these days!