Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


2019-12-24 - Planet of Discord

(original .ipynb)

Day 24 puzzle input is a (mine is here) sort of cellular automata system. Part 1 involves running the system until a certain calculation (called "biodiversity") returns a value previously seen. Part 2 involves modifying this to be weirdly recursive in a way that is too complex to summarise in a single sentence (check the linked problem definition).

import functools
import operator

puzzle_input_raw = open("puzzle_input/day24.txt").read()

state = [ 
    [ c for c in line ] for line in puzzle_input_raw.split("\n") if line.strip() 
]

# A bug dies (becoming an empty space) unless there is exactly one bug 
#    adjacent to it.
# An empty space becomes infested with a bug if exactly one or two bugs 
#    are adjacent to it.
def next_cell_value(state, r, c):
    # count the bugs
    bugs = 0
    if r > 0 and state[r-1][c] == "#":
        bugs += 1
    if r < 4 and state[r+1][c] == "#":
        bugs += 1
    if c > 0 and state[r][c-1] == "#":
        bugs += 1
    if c < 4 and state[r][c+1] == "#":
        bugs += 1        
    
    if state[r][c] == "#" and bugs != 1:
        return "."
    
    if state[r][c] == "." and (bugs == 1 or bugs == 2):
        return "#"
    
    return state[r][c]

def advance_state(state):
    new_state = []
    for r, row in enumerate(state):
        new_row = []
        for c, col in enumerate(row):
            new_row.append(next_cell_value(state, r, c))    
        new_state.append(new_row)
        
    return new_state

def calculate_biodiversity(state):
    flattened_state = functools.reduce(operator.iconcat, state, [])
    xxx = [ 2 ** i for i, tile in enumerate(flattened_state) if tile == "#" ]
    
    return sum(xxx)


biodiversities = set()
count = 0

while True:
    biodiversity = calculate_biodiversity(state)
    if biodiversity in biodiversities:
        print(biodiversity)
        break
    else:
        biodiversities.add(biodiversity)
    state = advance_state(state)
    count += 1

from pprint import pprint
print(count)
pprint(state)
19923473
62
[['#', '.', '.', '.', '#'],
 ['.', '.', '.', '.', '#'],
 ['.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.'],
 ['#', '#', '.', '.', '#']]
# part 2 - extra dimensions added, so I rewrote this completely.
#          to reduce likelihood of any errors I made LOTS of tiny
#          little functions that are easy to read and debug even
#          though it makes the solution more verbose.

def count_bugs_parent(grids, l, r, c):
    if l == 0:
        return 0
    parent = grids[l - 1]
    bugs = 0
    
    if c == 0:
        bugs += parent[2][1]
        
    if c == 4:
        bugs += parent[2][3]
    
    if r == 0:
        bugs += parent[1][2]
        
    if r == 4:
        bugs += parent[3][2]
    
    return bugs

def count_bugs_child(grids, l, r, c):
    if l == len(grids) - 1:
        return 0       
    child = grids[l + 1]
    bugs = 0
    
    if r == 2 and c == 1:
        bugs += sum([child[n][0] for n in range(5)])

    if r == 2 and c == 3:
        bugs += sum([child[n][4] for n in range(5)])
    
    if r == 1 and c == 2:
        bugs += sum(child[0])
        
    if r == 3 and c == 2:
        bugs += sum(child[4])        
    
    return bugs

def count_bugs_left(grids, l, r, c):
    if c == 0:
        return 0
    
    return grids[l][r][c-1]

def count_bugs_right(grids, l, r, c):
    if c == 4:
        return 0
    
    return grids[l][r][c+1]

def count_bugs_up(grids, l, r, c):
    if r == 0:
        return 0
    
    return grids[l][r-1][c]

def count_bugs_down(grids, l, r, c):
    if r == 4:
        return 0
    
    return grids[l][r+1][c]

def count_nearby_bugs(grids, l, r, c):
    return sum([
        count_bugs_left(grids, l, r, c),
        count_bugs_right(grids, l, r, c),
        count_bugs_up(grids, l, r, c),
        count_bugs_down(grids, l, r, c),
        count_bugs_parent(grids, l, r, c),
        count_bugs_child(grids, l, r, c)
    ])


def bug_to_int(cell):
    if cell == "#":
        return 1
    return 0

def parse_grid(grid_str):
    return [ 
        [ bug_to_int(c) for c in line ] 
        for line 
        in grid_str.split("\n") 
        if line.strip() 
    ]

def step_cell(grids, l, r, c):
    nearby_bugs = count_nearby_bugs(grids, l, r, c)   

    # center tile doesn't ever change
    if r == 2 and c == 2:
        return 0        
    
    if grids[l][r][c] == 1:
        # A bug dies (becoming an empty space) unless there is exactly one bug 
        #    adjacent to it.
        if nearby_bugs != 1:
            return 0
        return 1
    
    if grids[l][r][c] == 0:
        # An empty space becomes infested with a bug if exactly one or two bugs 
        #    are adjacent to it.
        if (nearby_bugs == 1 or nearby_bugs == 2):
            return 1
        return 0
    
    raise Exception(f"Invalid bug count on cell: {grids[l][r][c]}")

def step_grid(grids, l):
    new_grid = []
    for r, row in enumerate(grids[l]):
        new_row = []
        for c, col in enumerate(row):
            new_row.append(step_cell(grids, l, r, c))    
        new_grid.append(new_row)
    return new_grid

empty_grid_str = """
.....
.....
.....
.....
.....
"""

test_grid_str = """
....#
#..#.
#..##
..#..
#....
"""

def empty_grid():
    return parse_grid(empty_grid_str)

def copy_grid(grid):
    return [
        [ c for c in row]
        for row in grid
    ]

def any_bugs(grid):
    return 0 != sum([sum(row) for row in grid])

def count_bugs(grids):
    # could be a big list comp but ... no
    total = 0
    for grid in grids:
        for row in grid:
            total += sum(row)
    return total

# all_grids = [ empty_grid(), parse_grid(test_grid_str), empty_grid() ]
all_grids = [ empty_grid(), parse_grid(puzzle_input_raw), empty_grid() ]

minutes = 200
while minutes > 0:
    minutes -= 1
    new_all_grids = []
    
    for l, grid in enumerate(all_grids):
        new_all_grids.append(step_grid(all_grids, l))

    if (any_bugs(all_grids[0])):
        new_all_grids.insert(0, empty_grid())
    
    if (any_bugs(all_grids[len(all_grids)-1])):
        new_all_grids.append(empty_grid())    
        
    all_grids = new_all_grids

print(count_bugs(all_grids))
1902