# Advent of Code 2020 Day 13

[2020-12-13]

#development #adventofcode #julia

Previous: Advent of Code 2020 Day 12

Next: Advent of Code 2020 Day 14

## Part 1

For parsing the input I’m going to try Chain.jl, which offers a nice macro for applying a chain of operations, with a bit more flexibility than pipelines (namely, when mixing operations that need the chained arguments first and last).

```
buses = @chain readline(io) begin
split(_, ",")
filter(x->x!="x",_)
map(x->parse(Int,x),_)
end
```

We could do some iteration here (and I suspect for part 2 we may have to), but for now some basic arithmetic will suffice:

```
nextarrivals(after::Int, buses::Vector{Int})::Vector{Int} =
map(x->ceil(after/x)*x-after, buses)
```

## Part 2

“However, with so many bus IDs in your list, surely the actual earliest
timestamp will be larger than 100000000000000!” OK no iteration then. Linear
algebra maybe? Let’s examine test case `17,x,13,19`

:

```
17x = t
13y = t+2
19z = t+3
```

where x, y, and z are the number of routes each bus has run (numbers we don’t care about). Four unknowns in three equations, but we do have another constraint: x, y, and z need to be integers. So going to swing back to iteration: iterate over the longest bus route (z in this example), and then solve for the others.

```
for z in 1:...
t = 19z-3
if integer?(t/17) && integer?((t+2)/13)
break
```

Conveniently Julia includes an `isinteger()`

function already. First we need to
change the input parsing from filtering out `x`

, since we now need to know
position in the list too. I’ll just have it output `-1`

instead, which I’ll then
filter out in `part1()`

.

```
buses = @chain readline(io) begin
split(_, ",")
map(x->x=="x" ? -1 : parse(Int,x),_)
end
buses = filter(x->x>0, buses)
```

Maybe this would instead be a good use for
missing? To calculate the
number of routes for each bus for a given timestamp I’ll create an array of
anonymous functions, that returns `missing`

for the wildcard routes:

```
nroutes(i::Int, interval::Int) = interval>0 ? t->(t+i)/interval : missing
fs = skipmissing([nroutes(i-1, buses[i]) for i in 1:length(buses)])
```

Then find the bus with the longest route, iterate on its routes, and find the timestamp where all known route functions return integers.

```
m = maximum(buses)
mt = findfirst(x->x==m, buses)-1
t(r) = r*m-mt
r = 1
while true
rs = map(f->f(t(r)), fs)
if all(isinteger, rs)
break
end
r += 1
end
```

Well, this works fine for all the test cases, but as I feared doesn’t complete
for the problem. Peeking at the problem input I notice that the max route length
is pretty small (under one thousand), so the savings of iterating by it instead
of `t`

isn’t all that great, so this method was doomed to failure (maybe I
should have looked at that first…).

So what next? Modular arithmetic? Interestingly it looks like all the bus numbers are prime, what are the implications of that? Aha, following the previous link I found Chinese remainder theorem, which looks promising, since we can restate the example as

```
t ≡ 0 (mod 17)
t ≡ -2 (mod 13)
t ≡ -3 (mod 19)
```

which fits the general form. I don’t totally understand the methods described for computations, so instead I’m just going to use the nice formulation on Rosetta Code. Cheating? Maybe, but I’m just happy to figure out what theorem to use. And there’s still some plumbing to write…

```
ns = filter(x->x>0, buses)
as = [1-i for i in filter(x->buses[x]>0, 1:length(buses))]
```