Python
I spent way too long optimizing this solution from ~20s to <1s
# Build grid as list of integers (bitmask for each row)
def build_grid(data: str) -> list[int]:
grid = []
for line in data.splitlines():
row = 0
for j, cell in enumerate(line):
if cell == '#':
row |= (1 << j)
grid.append(row)
return grid
# Compute next step of the grid while counting new active cells
# Highly optimized using bitwise operations
def compute_next_step(grid: list[int], m, n):
next_grid = []
new_active_cells = 0
mask = (1 << n) - 1 # mask to keep only n bits
for i in range(m):
row_above = grid[i-1] if i > 0 else 0
row_below = grid[i+1] if i < m - 1 else 0
# Neighbors are diagonal: (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)
n_above = (row_above << 1) ^ (row_above >> 1) # above neighbors are odd parity
n_below = (row_below << 1) ^ (row_below >> 1) # below neighbors are odd parity
# total active neighbors are odd parity
neighbors_xor = n_above ^ n_below
# the rules say a cell becomes active if:
# - it is currently active, and has an odd number of active neighbors
# - it is currently inactive, and has an even number of active neighbors
# this is equivalent to having an even number of (active neighbors + itself)
# For single bit, equivalent to: ~(self ^ neighbors_xor) & 1
# self ^ neighbors_xor = 0 if both are even or both are odd (desired case)
# so we negate it to get 1 in desired case
# and we apply mask to keep only n bits
# This is all done in parallel for the entire row using bitwise operations
next_row = ~(grid[i] ^ neighbors_xor) & mask
next_grid.append(next_row)
new_active_cells += next_row.bit_count()
return next_grid, new_active_cells
# Simulate for given rounds and return total active cells
def part1(data: str, rounds = 10):
grid = build_grid(data)
m, n = len(grid), data.index('\n')
total_active = 0
for _ in range(rounds):
next_grid, new_active_cells = compute_next_step(grid, m, n)
total_active += new_active_cells
grid = next_grid
return total_active
assert (t := part1(""".#.##.
##..#.
..##.#
.#.##.
.###..
###.##""")) == 200, f"Expected 200 but got {t}"
# part 2 is just part 1 with more rounds
from functools import partial
part2 = partial(part1, rounds=2025)
# Match 8x8 pattern with center of 34x34 grid
def match_pattern(next_grid, pattern_grid):
for i in range(8):
# skip first 13 rows and shift right by 13 to align with pattern
if ((next_grid[i+13] >> 13) & 0xFF) != pattern_grid[i]:
return False
return True
def part3(pattern: str):
pattern_grid = build_grid(pattern)
grid_size = 34
rounds = 1000000000
grid = [0] * grid_size # we start with an empty 34x34 grid
seen = set() # grids we have seen
cumu_matches_for_round = [0] # cumulative matches for each round in the cycle
cumu_matches = 0 # current cumulative matches
# Simulate until we find a cycle or reach the rounds limit
round = 1
while round <= rounds:
next_grid, next_actives = compute_next_step(grid, grid_size, grid_size)
# get current state and check for cycles
state = tuple(next_grid)
if state in seen:
break
else:
seen.add(state)
# check for pattern match and update cumulative matches
if match_pattern(next_grid, pattern_grid):
cumu_matches += next_actives
# store cumulative matches from the start to this round
cumu_matches_for_round.append(cumu_matches)
# update variables for next round
grid = next_grid
round += 1
# the length of the cycle is round - 1 since we break AFTER detecting a cycle (cycle + 1)
cycle_len = round - 1
# the number of full cycles we can fit in rounds
full_cycles = rounds // cycle_len
# the total matches from full cycles
matches = full_cycles * cumu_matches
# the remaining rounds after full cycles
matches += cumu_matches_for_round[rounds % cycle_len]
return matches
assert (t := part3("""#......#
..#..#..
.##..##.
...##...
...##...
.##..##.
..#..#..
#......#""")) == 278388552, f"Expected 278388552 but got {t}"
Yeah I've got the DSU algorithm ingrained because of the number of the times I had to practice it for coding rounds. I didn't need to do path compression and union by rank either but might as well.