2020-12-17 - Conway Cubes
(original .ipynb)
Day 17 input is a 2D plane showing active ("#") and inactive (".") cubes (mine is here) which is part of an infinite 3D grid. There are rules like Conway's "game of life" which determine how each of these cubes changes over time (becomes active/inactive). Part 1 involves running this over 6 iterations. Part 2 involves running this over 6 interations in four dimensions. I wish I had time to make a visualization of this, I think it could be cool.
puzzle_input_str = open("puzzle_input/day17.txt", "r").read()
test_input_str = """.#.
..#
###"""
def parse_input_str(input_str):
return [
[
[ c for c in s ]
for s
in input_str.split("\n")
]
]
def generate_neighbour_deltas():
for dz in vals:
for dy in vals:
for dx in vals:
if dz == 0 and dy == 0 and dx == 0:
continue
yield (dz, dy, dx)
neighbour_deltas = [d for d in generate_neighbour_deltas()]
def is_active(cube):
return cube == "#"
def is_inactive(cube):
return cube == "." # needed?
# we'll check if we should "grow" the grid at the start of each step
# if there's any "active" cubes at the extremities, we'll do it
def should_grow_grid(grid):
# check min z
for row in grid[0]:
if any(is_active(col) for col in row):
return True
# check max z
max_z = len(grid)-1
for row in grid[max_z]:
if any(is_active(col) for col in row):
return True
# check min y
for plane in grid:
if any(is_active(col) for col in plane[0]):
return True
# check max y
for plane in grid:
max_row = len(plane) - 1
if any(is_active(col) for col in plane[max_row]):
return True
# check min x
for plane in grid:
if any(is_active(row[0]) for row in grid):
return True
# check max x
for plane in grid:
max_x = len(plane[0][0]) - 1
if any(is_active(row[0]) for row in grid):
return True
return False
def empty_plane(len_y, len_x):
return [
["." for x in range(len_y)]
for y
in range(len_y)
]
def grow_grid(grid):
len_z = len(grid)
len_y = len(grid[0])
len_x = len(grid[0][0])
# grow in z - meaning add a new plane to front and back
grid.insert(0, empty_plane(len_y, len_x))
grid.append(empty_plane(len_y, len_x))
# grow in y - meaning add a new row at top and bottom of each plane
for p in range(len(grid)):
grid[p].insert(0, ["." for x in range(len_y)])
grid[p].append(["." for x in range(len_y)])
# grow in x - meaning add a new empty col at start and end of each row in each row of each plane
for p in range(len(grid)):
for r in range(len(grid[p])):
grid[p][r].insert(0, ".")
grid[p][r].append(".")
def get_cube(grid, z, y, x):
if z >= 0 and z < len(grid):
if y >= 0 and y < len(grid[z]):
if x >= 0 and x < len(grid[z][y]):
return grid[z][y][x]
return "."
def get_neighbours(grid, z, y, x):
return [
get_cube(grid, (dz+z), (dy+y), (dx+x))
for dz,dy,dx
in neighbour_deltas
]
def next_value(grid, z, y, x):
cube = get_cube(grid, z, y, x)
num_active_neighbours = sum(1 for neighbour in get_neighbours(grid, z, y, x) if is_active(neighbour))
# 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 is_active(cube):
if (num_active_neighbours == 2 or num_active_neighbours == 3):
return "#"
else:
return "."
# If a cube is inactive but exactly 3 of its neighbors are active, the
# cube becomes active. Otherwise, the cube remains inactive.
if is_inactive(cube):
if num_active_neighbours == 3:
return "#"
else:
return "."
# TODO remove once we confirm I've not fucked this up
raise Exception("Should not happen!!!")
def count_active(grid):
active = 0
for plane in grid:
for row in plane:
for col in row:
if is_active(col):
active += 1
return active
def solve(input_str, cycles=6):
grid = parse_input_str(input_str)
while cycles > 0:
new_grid = []
if should_grow_grid(grid):
grow_grid(grid)
for z, plane in enumerate(grid):
new_plane = []
for y, row in enumerate(plane):
new_row = []
for x, col in enumerate(row):
new_row.append(next_value(grid, z, y, x))
new_plane.append(new_row)
new_grid.append(new_plane)
assert len(grid) == len(new_grid)
assert len(grid[0]) == len(new_grid[0])
assert len(grid[0][0]) == len(new_grid[0][0])
grid = new_grid
cycles -= 1
return count_active(grid)
assert 112 == solve(test_input_str)
print(solve(puzzle_input_str))
286
puzzle_input_str = open("puzzle_input/day17.txt", "r").read()
test_input_str = """.#.
..#
###"""
def parse_input_str(input_str):
return [
[
[ c for c in s ]
for s
in input_str.split("\n")
]
]
def generate_neighbour_deltas_4d():
for dw in vals:
for dz in vals:
for dy in vals:
for dx in vals:
if dw == 0 and dz == 0 and dy == 0 and dx == 0:
continue
yield (dw, dz, dy, dx)
neighbour_deltas = [d for d in generate_neighbour_deltas_4d()]
# we'll check if we should "grow" the grid at the start of each step
# if there's any "active" cubes at the extremities, we'll do it
def should_grow_grid_4d(grid):
for dimension in grid:
if should_grow_grid(dimension):
return True
return False
def create_grid(len_z, len_y, len_x):
return [
empty_plane(len_y, len_x)
for z
in range(len_z)
]
def grow_grid_4d(grid):
len_z = len(grid[0])
len_y = len(grid[0][0])
len_x = len(grid[0][0][0])
new_grid = [create_grid(len_z, len_y, len_x)] + grid + [create_grid(len_z, len_y, len_x)]
for g in new_grid:
grow_grid(g)
return new_grid
def get_cube_4d(grid, w, z, y, x):
if w >= 0 and w < len(grid):
return get_cube(grid[w], z, y, x)
return "."
def get_neighbours_4d(grid, w, z, y, x):
return (
get_cube_4d(grid, w+dw, z+dz, y+dy, x+dx)
for dw, dz, dy, dx
in generate_neighbour_deltas_4d()
)
def next_value_4d(grid, w, z, y, x):
cube = get_cube_4d(grid, w, z, y, x)
num_active_neighbours = sum(1 for neighbour in get_neighbours_4d(grid, w, z, y, x) if is_active(neighbour))
# 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 is_active(cube):
if (num_active_neighbours == 2 or num_active_neighbours == 3):
return "#"
else:
return "."
# If a cube is inactive but exactly 3 of its neighbors are active, the
# cube becomes active. Otherwise, the cube remains inactive.
if is_inactive(cube):
if num_active_neighbours == 3:
return "#"
else:
return "."
# TODO remove once we confirm I've not fucked this up
raise Exception("Should not happen!!!")
def solve_4d(input_str, cycles = 6):
grid = [parse_input_str(input_str)]
pprint(grid)
print()
while cycles > 0:
new_grid = []
if should_grow_grid_4d(grid):
grid = grow_grid_4d(grid)
for w, dimension in enumerate(grid):
new_dimension = []
for z, plane in enumerate(dimension):
new_plane = []
for y, row in enumerate(plane):
new_row = []
for x, col in enumerate(row):
new_row.append(next_value_4d(grid, w, z, y, x))
new_plane.append(new_row)
new_dimension.append(new_plane)
new_grid.append(new_dimension)
assert len(grid) == len(new_grid)
assert len(grid[0]) == len(new_grid[0])
assert len(grid[0][0]) == len(new_grid[0][0])
assert len(grid[0][0][0]) == len(new_grid[0][0][0])
grid = new_grid
cycles -= 1
return sum(count_active(dimension) for dimension in grid)
assert 848 == solve_4d(test_input_str)
print(solve_4d(puzzle_input_str))
[[[['.', '#', '.'], ['.', '.', '#'], ['#', '#', '#']]]] [[[['#', '#', '#', '#', '.', '.', '.', '#'], ['.', '.', '.', '.', '.', '.', '#', '.'], ['#', '.', '.', '#', '.', '#', '#', '.'], ['.', '#', '.', '.', '.', '#', '.', '#'], ['.', '.', '#', '#', '#', '.', '#', '.'], ['#', '#', '.', '#', '#', '#', '.', '.'], ['.', '#', '.', '.', '.', '#', '#', '#'], ['.', '#', '#', '.', '.', '.', '.', '#']]]] 960