## 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`.