Advent of Code 2020 Day 17

Part 1

Today’s problem is an interesting twist on Conway’s Game of Life, which we previously saw in Day 11, although this is closer to AoC 2019 day 24, since it’s an infinitely-expanding universe. I’ll similarly use a three-dimensional array, but instead of expanding it every iteration, since we know (for now) that we only need to do six iterations, I’ll start with it fully allocated (15x15x13) so indices are consistent between iterations.

On my first reading of the examples I’m a bit confused though: it starts 3x3x1

.#.
..#
###

But then after one cycle goes to 3x3x3, instead of 5x5x3 as I’d expect.

z=-1
#..
..#
.#.

z=0
#.#
.##
.#.

z=1
#..
..#
.#.

Manually applying the rules I get this for z=0:

.....
.....
.#.#.
..##.
..#..

Ah “the frame of view follows the active cells in each cycle”, OK, so it’s shifted down to show only the 3x3 region with active cells.

I read through the input twice, first to obtain the input dimensions so I can allocate the array (iter is the number of iterations we’ll perform):

    space = falses(r+iter*2,c+iter*2,1+iter*2)

Then read through a second time, setting the initial state in the array:

    j = iter
    for line in eachline(in)
        j += 1
        for i in 1:c
            space[j,i+iter,iter+1] = line[i] == '#'
        end
    end

The main update logic is straightforward: loop over the cells (noting that Julia stores arrays in column-major order, unlike C or numpy):

    (r, c, l) = size(space)
    new = falses(r,c,l)
    for k in 1:l
        for i in 1:c
            for j in 1:r

Grab the neighbors as a slice, clamped to the array dimensions, and count them, noting that this count will include the cell of interest:

                neighbors = @view space[max(j-1,1):min(j+1,r),
                                        max(i-1,1):min(i+1,c),
                                        max(k-1,1):min(k+1,l)]
                n = count(neighbors)

Then apply rules:

                if space[j,i,k] && n in (3,4)
                    # If a cube is active and exactly 2 or 3 of its neighbors
                    # are also active, the cube remains active. Otherwise, the
                    # cube becomes inactive. NB: n includes itself
                    new[j,i,k] = true
                elseif !space[j,i,k] && n == 3
                    # If a cube is inactive but exactly 3 of its neighbors are
                    # active, the cube becomes active. Otherwise, the cube
                    # remains inactive.
                    new[j,i,k] = true
                end

Part 2

So now we expand to a hypercube. I think Julia will really shine here. I like keeping a single soure file for each day, reusing as much as possible (and updating where needed to support part 2), but in this case I’m just going to copy and expand everything to four dimensions.

    space = falses(r+iter*2,c+iter*2,1+iter*2,1+iter*2)

That’s a lot of nested loops…

    
    (r, c, l, w) = size(space)
    new = falses(r,c,l,w)
    for q in 1:w
        for k in 1:l
            for i in 1:c
                for j in 1:r
                    neighbors = @view space[max(j-1,1):min(j+1,r),
                                            max(i-1,1):min(i+1,c),
                                            max(k-1,1):min(k+1,l),
                                            max(q-1,1):min(q+1,w)]

But hey it works, hooray for first-class multidimensional arrays! I guess the question now is if I want to beat myself up with extra credit in a language that doesn’t have such great array support (so not common lisp either).