2020-12-24 - Lobby Layout
(original .ipynb)
Day 24 input is a sequence of paths through a hexagonal grid (mine is here) representing the tile pattern of a floor (once the end of each path is reached the tile color is flipped). Part 1 involves interpreting these paths and determining how many end up being black. Part 2 involves playing this repeatedly with a few cellular-automata/game-of-life type rules that govern how the tiles change over time.
from collections import defaultdict
from pprint import pprint
test_input_str = """sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse
nwnwneseeswswnenewneswwnewseswneseene
swweswneswnenwsewnwneneseenw
eesenwseswswnenwswnwnwsewwnwsene
sewnenenenesenwsewnenwwwse
wenwwweseeeweswwwnwwe
wsweesenenewnwwnwsenewsenwwsesesenwne
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
enesenwswwswneneswsenwnewswseenwsese
wnwnesenesenenwwnenwsewesewsesesew
nenewswnwewswnenesenwnesewesw
eneswnwswnwsenenwnwnwwseeswneewsenese
neswnwewnwnwseenwseesewsenwsweewe
wseweeenwnesenwwwswnew"""
puzzle_input_str = open("puzzle_input/day24.txt", "r").read()
def parse_input_line(input_line_str):
input_line = [c for c in input_line_str]
instructions = []
previous = None
while len(input_line) > 0:
current = input_line.pop(0)
if current == "n" or current == "s":
previous = current
elif current == "e":
if previous:
current = previous + current
previous = None
elif current == "w":
if previous:
current = previous + current
previous = None
if not previous:
instructions.append(current)
return instructions
def next_row(row, direction):
if direction == "ne" or direction == "nw":
return row - 1
elif direction == "se" or direction == "sw":
return row + 1
elif direction == "e" or direction == "w":
return row
def next_col(row, col, direction):
even_row = row % 2 == 0
if direction == "ne":
if even_row:
return col
else:
return col + 1
elif direction == "nw":
if even_row:
return col - 1
else:
return col
elif direction == "se":
if even_row:
return col
else:
return col + 1
elif direction == "sw":
if even_row:
return col - 1
else:
return col
elif direction == "e":
return col + 1
elif direction == "w":
return col - 1
else:
raise Exception(f"Invalid instruction {instruction}")
def map_floor_pattern(input_str):
all_flip_sequences = [parse_input_line(input_line) for input_line in input_str.split("\n")]
floor_pattern_map = defaultdict(lambda:True)
for flip_sequence in all_flip_sequences:
row = 0
col = 0
for instruction in flip_sequence:
row = next_row(row, instruction)
col = next_col(row, col, instruction)
coord = (row, col)
floor_pattern_map[coord] = not floor_pattern_map[coord]
return floor_pattern_map
def count_black_tiles(floor_pattern_map):
number_black = 0
for coord in floor_pattern_map:
if not floor_pattern_map[coord]:
number_black += 1
return number_black
def part1(input_str):
floor_pattern_map = map_floor_pattern(input_str)
return count_black_tiles(floor_pattern_map)
assert 1 == part1("nwwswee")
assert 10 == part1(test_input_str)
print(part1(puzzle_input_str))
459
%%time
# ^^ adding this to show my solution is s-l-o-w
import math
directions = ["ne", "nw", "se", "sw", "e", "w"]
def get_neighbours(grid, row, col):
neighbour_coords = [
(next_row(row, direction), next_col(row, col, direction))
for direction
in directions
]
max_row = len(grid)
max_col = len(grid[0])
neighbours = []
for direction in directions:
r = next_row(row, direction)
c = next_col(row, col, direction)
if r < 0 or r >= max_row or c < 0 or c >= max_col:
continue
neighbours.append(grid[r][c])
return neighbours
def generate_grid(rows, cols):
grid = []
for r in range(rows + 1):
grid.append([True for c in range(cols + 1)])
return grid
def grid_from_map(floor_pattern_map):
min_row, min_col = math.inf, math.inf
max_row, max_col = -math.inf, -math.inf
for row, col in floor_pattern_map:
if row < min_row:
min_row = row
elif row > max_row:
max_row = row
if col < min_col:
min_col = col
elif col > max_col:
max_col = col
# our grid will be (max_row - min_row) rows and (max_col - min_col) columns
grid = generate_grid(
max_row - min_row,
max_col - min_col
)
# now set all appropriate vals
for coord in floor_pattern_map:
row, col = coord
adjusted_row = row - min_row
adjusted_col = col - min_col
grid[adjusted_row][adjusted_col] = floor_pattern_map[coord]
return grid
def create_empty_row(grid):
return [True] + [True for tile in grid[0]] + [True]
def extend_row(row, grow_left, grow_right):
new_row = []
if grow_left:
new_row.append(True)
new_row += row
if grow_right:
new_row.append(True)
return new_row
def maybe_grow_grid(grid):
grow_up = any(grid[0])
grow_down = any(grid[-1])
grow_left = any([row[0] for row in grid])
grow_right = any([row[-1] for row in grid])
if not any([grow_up, grow_down, grow_left, grow_right]):
return grid
new_grid = []
if grow_up:
new_grid.append(create_empty_row(grid))
new_grid.append(create_empty_row(grid))
new_grid += [extend_row(row, grow_left, grow_right) for row in grid]
if grow_down:
new_grid.append(create_empty_row(grid))
new_grid.append(create_empty_row(grid))
return new_grid
def step(grid):
new_grid = []
for r, row in enumerate(grid):
new_row = []
for c, tile in enumerate(row):
neighbours = get_neighbours(grid, r, c)
black_neighbours = sum(1 for n in neighbours if not n)
# Any white tile with exactly 2 black tiles immediately adjacent to it is flipped to black.
if tile and black_neighbours == 2:
tile = False
# Any black tile with zero or more than 2 black tiles immediately adjacent to it is flipped to white.
elif (not tile) and (black_neighbours > 2 or black_neighbours == 0):
tile = True
new_row.append(tile)
new_grid.append(new_row)
return new_grid
def count_black_grid_tiles(grid):
count = 0
for row in grid:
for tile in row:
if not tile:
count += 1
return count
def part2(input_str, generations):
floor_pattern_map = map_floor_pattern(input_str)
floor_grid = grid_from_map(floor_pattern_map)
while generations > 0:
floor_grid = step(maybe_grow_grid(floor_grid))
generations -= 1
return count_black_grid_tiles(floor_grid)
assert 2208 == part2(test_input_str, 100)
part2(puzzle_input_str, 100)
CPU times: user 1min 7s, sys: 139 ms, total: 1min 7s Wall time: 1min 9s
4150