# Advent of Code 2020 Day 15

[2020-12-15]

#development #adventofcode #julia

Previous: Advent of Code 2020 Day 14

Next: Advent of Code 2020 Day 16

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

.