Part one is messy and not very interesting. We want to find the position closest to all of a set of points using a simple 1-D Euclidean distance metric and compute their total distance from that point. As far as we know, the points we’re given are just a random set of integers, so there’s no formal way to show that such a unique minimum-total-distance position exists.
What is a bit interesting is that all the solutions I’ve seen are some form of brute-force approach—enumerate every possible position (i.e. those in the interval between the maximum and minimum of the input positions), compute the total distance to that point, then take the minimum of those results. It occurred to me immediately that the median of the input set should be a good bet; sure enough, this works, and is only as expensive as sorting the input list.
total_distance : [ℕ] → ℕ
total_distance ns = sum (distances (median ns) ns)
distances a = list (distance a)
distance a b = |a - b|
total_distance can be reformulated as a catamorphism via type functor fusion, but meh; the Scheme version includes this fusion.
Again, I have no proof that this is the unique solution. We have to trust the AoC solution validator, which is annoying to me.
All that changes here is the fuel-usage function, which is now nonlinear and distinct from the distance. Since each unit of movement costs one more fuel than the last, we have
fuel a b = let n = distance a b in (n * (n + 1)) / 2
using a familiar formula. We seek the (unique?) point p such that
Σ fuel a p
p ∈ S
is minimized.