Advent of Code 2020 Day 13

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))]