Advent of Code 2020 Day 11

Part 1

Alright, a Conway’s Game of Life/cellular automata problem. Also see AoC 2019 day 24, which I happened to do just a week ago (finally!) in Julia. May as well leverage that code…

I immediately hit a bit of a problem, I used a BitArray for that, while this is a trinary state (empty seat, filled seat, floor). An enum may be handy here, let’s see how Julia’s @enum macro works.

@enum Ferry empty filled floor

Trying to construct an array of Enums is a bit more complicated, since zeros() etc. don’t work. Comprehension it is!

board = [floor for j in 1:rows, i in 1:cols]

Logic is simple: loop over board, count neighbors, and update. I leverage Julia’s views to concisely grab the neighbors (without copying!) and count the filled seats:

v = @view board[max(j-1,1):min(j+1,r), max(i-1,1):min(i+1,c)]
n = count(x->x==filled, v)

I do, however, make a new copy of the board with each update, rather than trying to juggle two boards for instance. So I won’t win any allocation prizes.

Part 2

Is there a clever way to do this? My first thought was an overlay filter, but no, since we need to actually “walk” away from the seat to find the first seat, filled or not. I’ll at least take advantage of Julia’s array slicing, e.g.:

up(board, j, i) = j==1 ? Ferry[] : board[j-1:-1:1, i]
upright(board, j, i) = j==1 || i==size(board,2) ? Ferry[] :
    [board[j-x,i+x] for x in 1:min(j-1, size(board,2)-i)]

Then it’s just a reduce() call to walk through and find the first seat.

firstfilled(v:Vector{Ferry})::Bool = reduce((x,y)->x==floor ? y : x, v; init=floor) == filled

Do this for every direction, and we get the number of occupied seats:

n = [up,upright,right,downright,down,downleft,left,upleft] .|> f->firstfilled(f(board,j,i)) |> sum

Admittedly this solution gets a bit ugly. Maybe there’s some clever topological math we can use instead?