Advent of Code 2020 Day 10

Part 1

Part 1 is pretty straightforward. I again leveraged Julia’s excellent vectors (and standard library) to easily calculate and tally up the differences. I’ve been using type annotations more often in function definitions, in addition to helping the compiler it helps me better understand the intended logic, and catch some dumb mistakes.

function differences(v::Vector{T})::Tuple{Int,Int} where (T<:Number)
    a = [0;sort(v)]
    b = [a[2:end];a[end]+3]
    d = b-a
    return sum(d.==1), sum(d.==3)
end

It would be interesting to do some detailed comparisons/benchmarking on sum(d.==1) vs count(x->x==1,d) vs length(filter(x->x==1,d)). I’d expect count() is the most memory-efficient at least, since the other two have to produce intermediate vectors (or do they??).

Part 2

“Surely, there must be an efficient way to count the arrangements.” Now we’re getting into it!

We don’t need to enumerate every possible combination from 0 to N. If we choose some pivot M, we can count the number of ways to get from 0 to M, and multiply that by the number of ways to get from M to N. For example, using the example input:

julia> a'
1×11 LinearAlgebra.Adjoint{Int64,Array{Int64,1}}:
 16  10  15  5  1  11  7  19  6  12  4

(I take the transpose (') to save vertical space here). Let’s sort it:

julia> sa=sort(a)'
1×11 LinearAlgebra.Adjoint{Int64,Array{Int64,1}}:
 1  4  5  6  7  10  11  12  15  16  19

Picking 7 as our pivot, we can see there are four ways to get there from 0 (remember, max step is 3): [0,1,4,5,6,7], [0,1,5,6,7], [0,1,5,7], and [0,1,4,7]. And there are two ways to get from 7 to 22: [7,10,11,12,15,16,19,22] and [7,10,12,15,16,19,22]. 4*2 = 8 QED.

Of course we don’t need to limit ourselves to one pivot, what if we repeated this for every element, but only counted the number of other elements we can reach (since then we can look at each of those in turn, to eventually walk the whole path)?

julia> b=Dict(i=>filter(x->i<x<=i+3,sa) for i in sort(a))
Dict{Int64,Array{Int64,1}} with 11 entries:
  16 => [19]
  11 => [12]
  7  => [10]
  10 => [11, 12]
  19 => Int64[]
  6  => [7]
  4  => [5, 6, 7]
  5  => [6, 7]
  15 => [16]
  12 => [15]
  1  => [4]

This looks promising, now how do we walk it? Recursively seems the most straight-forward…

function walk(a::Dict{Int,Vector{Int}}, n::Int)::Int
    paths = map(x->walk(a,x), a[n])
    length(paths) > 0 ? sum(paths) : 1
end

While this works for the test-cases, it’s too inefficient for the problem to complete in a reasonable time. So we can do better. Maybe I’m thinking about this backwards - instead of asking “where can we go from here” it’s better to ask “how did we get here”?

julia> b=Dict(i=>filter(x->i-3<=x<i,sa) for i in sa)
Dict{Int64,Array{Int64,1}} with 11 entries:
  16 => [15]
  11 => [10]
  7  => [4, 5, 6]
  10 => [7]
  19 => [16]
  6  => [4, 5]
  4  => [1]
  5  => [4]
  15 => [12]
  12 => [10, 11]
  1  => Int64[]

Then we go through each element in order, sum (and save) the paths from each origin (which is now just a lookup).

    for n in sa
        origins[n] = length(b[n]) > 0 ?
            sum([origins[x] for x in b[n]]) : 1
    end

Bingo!

Still a bit of room for optimization, here’s the core logic of my final (?) solution:

    sv=[0;sort(v)]
    origins = Dict{Int,Int}(0=>1)
    for n in sv[2:end]
        origins[n] = sum([origins[x] for x in filter(y->n-3<=y<n, sv)])
    end

1. I prepend sv with zero, our starting point, so it gets included as an origin in the filter. We don’t need the ending point since it’s always one step (three jolts) away.
2. The initial condition 0=>1 needs to be included in origins or the sum() will always be 0, and this lets us get rid of the ternary.
3. Loop over sv[2:end] since we don’t want to include the 0 that was prepended here (there’s nothing before it).
4. Just do the “origin” filtering in the main loop, no need to pre-calculate it.

Extra Credit

Common Lisp

Straighforward re-implementation of my Julia solution. Part 1:

(defun differences (ns)
  (let* ((a (cons 0 (sort (copy-seq ns) #'<)))
         (b (append (rest a) (mapcar (lambda (x) (+ 3 x)) (last a)))))
    (loop for m in a
          for n in b
          collect (- n m))))

(and then filter and multiply). A bit of an oddity is that (last) returns a list, hence the (mapcar ...) intead of (list (+ (last a) 3)) (we need a list for (append)).

Part 2:

(defun arrangements (ns)
  (let ((sv (cons 0 (sort (copy-seq ns) #'<))))
    (loop with origins = (make-array (mapcar #'1+ (last sv)) :initial-element 1)
          for n in (rest sv)
          do (setf (aref origins n)
                   (loop for x in sv
                         when (< (- n 4) x n)
                           sum (aref origins x)))
          finally (return (aref origins (1- (array-dimension origins 0)))))))

Again I rely heavily on (loop) here. It’s really a testament to the power of common lisp (remember, it’s just a macro!). Departing from the Julia solution I used an array instead of a dictionary/hash-table for origins. It probably doesn’t really matter here, with a max gap of three it can’t be very sparse, but then it may not be very dense either. Timing? vOv:

$ julia --load day10.jl --eval '@time main()'
  0.000486 seconds (1.00 k allocations: 156.281 KiB)
$ sbcl --load day10.lisp --eval '(time (main))'
Evaluation took:
  0.001 seconds of real time
  0.000923 seconds of total run time (0.000000 user, 0.000923 system)
  100.00% CPU
  2,391,024 processor cycles
  32,768 bytes consed

Edit: well that Julia timing was a bit misleading… main() was being called in the script, so the --eval call was apparently taking advantage of a lot of cache. Here’s the cold timing:

$ julia --load day10.jl --eval '@time main()'
  0.039977 seconds (25.05 k allocations: 1.309 MiB)

So now the common lisp version is looking a bit better.