Advent of Code 2020 Day 24

Part 1

In college I did some work on the design and modeling of nuclear reactors using hexagonal fuel elements; there I found it best to represent the hexagonal map as a rectangular array by shifting each row. For example:

1 2 3 X
 4 5 6
X 7 8 9

would be represented as:

1 2 3
4 5 6
7 8 9

with each row shifted by ½ the pitch. Or, in terms of the problem, the neighbors for element 5 (at row j and column i) are:

e  -> 6 -> (j  , i+1)
se -> 8 -> (j+1, i)
sw -> 7 -> (j+1, i-1)
w  -> 4 -> (j  , i-1)
nw -> 2 -> (j-1, i)
ne -> 3 -> (j-1, i+1)

We can encode this into a function to convert a tile string into an index:

    j, i = 0,0
    c = 1
    while c <= length(dir)
        if dir[c] == 'e'
            i += 1
            c += 1
        elseif dir[c] == 'w'
            i -= 1
            c += 1
        elseif dir[c] == 's'
            j += 1
            if dir[c+1] == 'w'
                i -= 1
            end
            c += 2
        elseif dir[c] == 'n'
            j -= 1
            if dir[c+1] == 'e'
                i += 1
            end
            c += 2
        else
            @error "unexpected direction $(dir[c]) at $c"
        end
    end

For part 1 we don’t actually need an array, a set or dictionary would suffice, but I’m going to guess we’ll need it for part 2, so I’ll go ahead and do it now. So then how do we size the destination array, and where do we start for the reference tile? I suppose we just need to run through the instructions twice, first counting the min and max i and j.

function extents(io::IO)::Tuple{Int,Int,Int,Int}
    j0, j1, i0, i1 = 0,0,0,0
    for line in eachline(io)
        j, i = tile(line)
        j0 = j < j0 ? j : j0
        j1 = j > j1 ? j : j1
        i0 = i < i0 ? i : i0
        i1 = j > i1 ? i : i1
    end
    return j0, j1, i0, i1
end

I’ll create a struct to store the mapping array and the min and max coordinates, and create methods to handle the mapping for us:

struct Floor
    map::BitArray{2}
    mj::Int
    mi::Int
end
Base.getindex(f::Floor, j::Int64, i::Int64) = f.map[j-f.mj+1, i-f.mi+1]
Base.setindex!(f::Floor, v::Bool, j::Int64, i::Int64) = f.map[j-f.mj+1, i-f.mi+1]=v

So then we need to call extents(), allocate the array (including padding for the axes), then loop through each line, flipping each tile:

function makefloor(io::IO)::Floor
    j0, j1, i0, i1 = extents(io)
    f = Floor(falses(j1-j0+2, i1-i0+1), j0, i0)
    seek(io,0)
    for line in eachline(io)
        j,i = tile(line)
        f[j,i] = !f[j,i]
    end
    return f
end

Part 2

Seems Game of Life is a recurring theme this year, hexagonal is a nice twist. Should be fairly simple, since I already created an array (phew!). We can’t take a nice slice to count the neighbors, since there’s only six; i.e. we don’t want to include the Xs:

X 2 3
4 X 6
7 8 X

However, since it’s everything except the diagonal we can easily create a filter:

julia> [i!=j for j in 1:3, i in 1:3]
3×3 Array{Bool,2}:
 0  1  1
 1  0  1
 1  1  0

And then counting neighbors and applying the rules is pretty straighforward:

            n=count(f.map[j-1:j+1, i-1:i+1][neighbors])
            if (f.map[j,i] && n in 1:2) ||
                (!f.map[j,i] && n == 2)
                g.map[j,i] = true
            end

I’ll oversize the array so I don’t need to deal with bounds checking (this doesn’t impact part 1, so I can just change it in makefloor()).

    f = Floor(falses(j1-j0+3, i1-i0+3), j0-1, i0-1)

Why aren’t my test cases working? Oh, oops, I overlooked/forgot about this bit at the beginning: “The lobby is large enough to fit whatever pattern might need to appear there.” So I may need to increase the size of the map; the simplest apprach is to increase it every iteration - we’re only doing 100 iterations, right?

    g = Floor(falses(r+2,c+2), f.mj-1, f.mi-1)