Advent of Code 2020 Day 15

Part 1

I thought about using a Dict, but then the bookeeping gets pretty complex; since we’re only looking for the 2020th number there’s no reason to not just keep the whole sequence in memory, and use findprev() to look back.

function next(ns)
    p=findprev(x->x==ns[end], ns, length(ns)-1)
    isnothing(p) ? 0 : length(ns)-p
end

Then we just need to allocate a vector, initialize it with the starting numbers, then loop through to 2020.

function nth(seed, n)
    ns = Vector{Int}(undef, n)
    for i in 1:length(seed)
        ns[i] = seed[i]
    end
    for i in length(seed)+1:n
        ns[i] = next(@view ns[1:i-1])
    end
    ns[end]
end

This could be written more concisely with a single loop, with a test inside the loop, but since the seed is so short we’re doing a lot of unecessary tests. Not that it matters here.

Part 2

As I figured, now we need to go much futher, so now I’ll probably have to do that bookeeping I evaded in part 1. It will still take a while to go through all those iterations, maybe there is a clever way to do this?

This probably isn’t the cleverest approach, but using a dictionary to track “last time n was spoken” does indeed work in a reasonable time. The next() function is straightforward, with the caveat that ns cannot have already been updated with the last number.

function next(ns, lasti, lastn)
    haskey(ns, lastn) ? lasti-ns[lastn] : 0
end

So this makes nth() a bit more complex, and I “cheat” a bit by essentially skipping the lookup for first non-seed number, instead saying the next number is 0 and going from there.

function nth(seed, n)
    ns = Dict{Int,Int}()
    for i in 1:length(seed)
        ns[seed[i]] = i
    end
    lastn = seed[end]
    nextn = 0
    for i in length(seed)+1:n
        lastn = nextn
        nextn = next(ns, i, lastn)
        ns[lastn] = i
    end
    lastn
end

So it’s bascially working one step ahead, hence returning lastn.