day 11

did someone say cellular automata?? i've been interested in them ever since i heard about conway's game of life (RIP John Conway), so i had the conceptual background for today's puzzle at least

both parts start off with reading in the seats and turning these into a list of lists (...i think that's how you're generally meant to implement arrays in python anyway). i'm getting more used to list comprehension, and applying list() to a string gives a list of the individual characters in that string which was super helpful!

i got the size of the array for identifying when you're out of bounds later, and also counted the number of seats in the first instance (this isn't really needed, it just helped for debugging since i had a maximum possible number of seats). i also set up two variables to record the current step (just for intermediate outputs) and the number of occupied seats (when the board stabilises, this value is our answer).

# input
with open('11.txt', 'r') as file:
    input = file.read()
# turn the input into a list, one element is one row of seats
input_list = list(input.split('\n'))
# turn each row into a list, so plane_seats has a list of lists
plane_seats = [list(row) for row in input_list]
# get size of array
row_len = len(plane_seats[0]) # row length
num_row = len(plane_seats) # number of rows
# get number of seats
num_seats = 0
for i in range(0, row_len):
    for j in range(0, num_row):
        if plane_seats[j][i] == 'L':
            num_seats += 1
# just gonna display the step
step = 0
# and the number of seats occupied
num_occ = 0

as with the usual cellular automata,  the rules given are applied to all seats simultaneously, so you either need to keep two arrays (one for the current board and one for the next), or add in extra states to combine the current state and next state. i decided to implement it as the latter, so in addition to the given states (. for floor, L for empty seat, # for occupied seat), i added two extra states:

• E = currently empty, will become occupied on the next step
• O = currently occupied, will become empty on the next step

for part a, both of the rules given concern the adjacent seats, so i wrote a function giving a list of the states of the adjacent seats (only trying to access the value if it's not the seat in the middle and the coordinates are in range):

# get adjacent seats (removing ones with coords out of range)
def get_adj(i: int, j: int):
    adj_seats = []
    for ia in [i-1, i, i+1]:
        for ja in [j-1, j, j+1]:
            if (ia >= 0 and ia < row_len) and (ja >= 0 and ja < num_row): # in range
                if not (ia == i and ja == j): # and not the middle seat
                    adj_seats.append(plane_seats[ja][ia])
    return adj_seats

we then have a loop that continues indefinitely, breaking if it goes through a full step and the board has not changed - this is implemented by a variable has_changed, which is set to false at the start of each step, and set to true if a seat's state changes.

the two rules we have are

• if the seat is empty (L or E), and if there are no occupied seats (# or O) next to it, then the seat will become occupied (O)
• if the seat is occupied (# or O), and if we find at least four occupied seats (# or O) next to it, then the seat will become empty (E)

after iterating over the entire array, we break this while loop if no changes have been made since num_occ now has the number of occupied seats, and we hit the print statement on the last row of this section; otherwise, we iterate over the array again to change every E to a # (empty to occupied) and every O to an L (occupied to empty), altering num_occ as needed, and then go to the next step in the while loop.

while 1:
    # track if a change was made at each step
    has_changed = False
    print('starting step ' + str(step) + '. seats occupied: ' + str(num_occ) + ' of ' + str(num_seats), end='\r', flush=True)
    for i in range(0, row_len):
        for j in range(0, num_row):
            # get state of current seat
            seat = plane_seats[j][i]
            # get states of adjacent seats
            adj_seats = get_adj(i,j)
            # L = currently empty, next state undetermined
            # # = currently occupied, next state undetermined
            # E = currently empty, will become occupied
            # O = currently occupied, will become empty
            # empty + no occupied next to it => occupied
            if seat in ['L', 'E']:
                if not ('#' in adj_seats or 'O' in adj_seats):
                    plane_seats[j][i] = 'E'
                    has_changed = True
            # occupied + four or more occupied next to it => empty
            if seat in ['#', 'O']:
                occ = 0
                for adj_seat in adj_seats:
                    if adj_seat in ['#', 'O']:
                        occ += 1
                    if occ == 4:
                        plane_seats[j][i] = 'O'
                        has_changed = True
                        break
            # o/w no change
    # if no changes, we are done
    if not has_changed:
        break
    # o/w increase step and move to next stage (E -> #, O -> L)
    step += 1
    for i in range(0, row_len):
        for j in range(0, num_row):
            # get state of current seat
            seat = plane_seats[j][i]
            # see if it should go empty to occupied
            if seat == 'E':
                plane_seats[j][i] = '#'
                num_occ += 1
            # see if it should go occupied to empty
            if seat == 'O':
                plane_seats[j][i] = 'L'
                num_occ -= 1
            # if it's . (floor), L, or #, no change
print('(part a) final number of seats occupied: ' + str(num_occ) + ' of ' + str(num_seats))

for part b, we instead need to look at the first seat we can see in any direction. there isn't really any need to do anything fancy to get the list of directions (as offsets per step), so i just hard-coded these:

dirs = [(-1,-1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

i then wrote a function to get the number of occupied seats visible from a given seat's coordinates. we start off by getting the offset for the direction we head in each time we take a step, and start a while loop that runs until we hit a seat or go out of the range:

• if we're out of range, break the loop
• if we're on the floor (.), take another step in that direction
• if we're on an empty seat, break the loop (add 0 to nov)
• if we're on an occupied seat, add 1 to nov and then break the loop

# get Number of Occupied Visible seats
def get_nov(i: int, j: int):
    nov = 0
    for dir in dirs:
        # get i-offset and j-offset
        io = dir[0]
        jo = dir[1]
        while 1:
            if i + io < 0 or i + io >= row_len or j + jo < 0 or j + jo >= num_row: # not in range
                break # we went too far
            if plane_seats[j + jo][i + io] == '.':
                # the spot in that direction is the floor
                # take another step in that direction
                io += dir[0]
                jo += dir[1]
            elif plane_seats[j + jo][i + io] in ['L', 'E']:
                # the first seat you see is empty
                # go to next dir
                break
            elif plane_seats[j + jo][i + io] in ['#', 'O']:
                # the first seat you see is occupied
                # add one to nov then go to next dir
                nov += 1
                break
    return nov

as in part a, we now do another loop continuing indefinitely, which will break when there is no change to the board. our two new rules depend on the seat's current state and the output of get_nov() for that seat:

• if the seat is empty (L or E), and you can see no occupied seats (# or O) from it, then the seat will become occupied (O)
• if the seat is occupied (# or O), and if we can see at least five occupied seats (# or O) from it, then the seat will become empty (E)

the additional temporary states change as before (E -> #, O -> L) before the next step

while 1:
    # track if a change was made at each step
    has_changed = False
    print('starting step ' + str(step) + '. seats occupied: ' + str(num_occ) + ' of ' + str(num_seats), end='\r', flush=True)
    for i in range(0, row_len):
        for j in range(0, num_row):
            # get state of current seat
            seat = plane_seats[j][i]
            # empty + sees no occupied => occupied
            if seat in ['L', 'E']:
                if get_nov(i,j) == 0:
                    plane_seats[j][i] = 'E'
                    has_changed = True
            # occupied + five or more occupied in vision => empty
            if seat in ['#', 'O']:
                if get_nov(i,j) >= 5:
                    plane_seats[j][i] = 'O'
                    has_changed = True
            # o/w no change
    # if no changes, we are done
    if not has_changed:
        break
    # o/w increase step and move to next stage (E -> #, O -> L)
    step += 1
    for i in range(0, row_len):
        for j in range(0, num_row):
            # get state of current seat
            seat = plane_seats[j][i]
            # see if it should go empty to occupied
            if seat == 'E':
                plane_seats[j][i] = '#'
                num_occ += 1
            # see if it should go occupied to empty
            if seat == 'O':
                plane_seats[j][i] = 'L'
                num_occ -= 1
            # if it's . (floor), L, or #, no change
print('(part b) final number of seats occupied: ' + str(num_occ) + ' of ' + str(num_seats))