This post includes solutions!
In todays puzzle we use
- map iterators Each and Each Left
- the While iterator to implement a binary search
- the Do iterator
We can represent crab positions as an integer vector.
cp:161204271214 / crab positions
The distance from cp to any position x is simply abs cp-x. A brute-force solution calculates the fuel cost to all possible destinations.
q)abscp-\:til1+maxcp161514131211109876543210101234567891011121314152101234567891011121314012345678910111213141516432101234567891011122101234567891011121314765432101234567891012345678910111213141521012345678910111213141413121110987654321012
Each column corresponds to a candidate destination.
q)sumabscp-\:til1+maxcp / fuel costs494137394145495359657177838995103111
And finds the smallest.
q)minsumabscp-\:til1+maxcp37
But we notice that the destination costs follow a smooth curve. Once we move past the optimum destination (2) the fuel costs rise steadily. We could stop searching as soon as the fuel cost begins to rise again.
A binary search of the solution space should converge quickly on the minimum, without calculating the fuel cost for every possible destination.
Moreover there are clusters of crabs in some positions. We need only calculate the fuel cost for each distinct position, then weight it by the number of crabs there.
Count the crabs at each position:
q)showcd:counteachgroupcp / crab distribution16|11|22|30|14|17|114|1
Calculate fuel cost for destination y in distribution x.
q)fc1:{sum(valuex)*absy-keyx}[cd;] / Part 1 fuel cost of destination q)fc12 / fuel cost of moving to 237
Now well use fc1 to search the solution space of til 1+max cd. Calculate the fuel cost at the halfway point and its neighbor. According to which cost is higher, drop half the solution space.
We start with a binary-search function. It evaluates a function at two adjacent values in the middle of a range and returns the upper or lower half of the range.
q)showfrd:(min;max)@\:key cd / full range of possible destinations016q)fc1each01+floormedfrd5965
The gradient is up so thats a go-left we want the lower part of the range (0,16).
q).[<]fc1each01+floormedfrd1b
If the midpoint is m we want 0,m. Had the gradient been down, wed want m,16.
q)?[;r;m]1not\.[<]fc1each01+m:floormedfrd08
Note the use of 1 not\. The form 1 f\x is a handy functional equivalent of (x;f x). We use the result with Vector Conditional ?[;r;m] to get one half of the range.
This can all be expressed as a binary-search function.
q)bs:{?[;y;m]1not\.[<]xeach01+m:floormedy} / halve range y with fn xq)bs[fc1]01608
We can wrap this with a short list function that narrows the range until we are happy to evaluate every point in it: say, no more than 5 points.
We can use the While iterator with a simple test function {neg[x]>.[-]y}[n;].
q)sl:{[n;f;r]{neg[x]>.[-]y}[n;]bs[f;]/r} / short listq)sl[5;fc1;]01604
The last expression above could have been written sl[5;fc1;0 16], but I wrote it as the unary projection of sl[5;fc1;] because the result 0 4 is a version of the third argument 0 16, so writing it as a projection helps the reader see a range transformed into another range. (You might also think of the first two arguments as constraints, options, or parameters; and the third argument as data.)
q)rng:{x+til y-x-1}. / range
q)minfceachrngsl[fc1;5;]01637
On my machine this is about 30× faster on the full puzzle data than the naive algorithm.
Part 2
In Part 2 all that changes is the fuel-cost calculation. Each distance has a multiplier.
fm:sumstil1+maxcpfc2:{sum(valuex)*fmabsy-keyx}[cd;] / fuel cost of moving to position y
The difference between the two fuel-cost functions is so small its worth making it an argument.
fc:{sum(valuex)*yabsz-keyx}[cd;;] / Part 2 fuel cost of moving to position z
This makes the projection fc a binary; its first argument is the fuel multiplier. For Part 1 that can be the Identity operator ::. Note here the use of an important q principle: functions, lists and dictionaries are all mappings from one domain to another. The syntax permits us to use either a function or a list as the first argument of fc.
Our complete solution:
cd:counteachgroupvaluefirstread0`:day7.txt / crab distributionfrd:(min;max)@\:keycd / full range of destinationsfc:{sum(valuex)*yabsz-keyx}[cd;;] / fuel cost of moving to position zbs:{?[;y;m]1not\.[<]xeach01+m:floormedy} / halve range y with fn xsl:{[f;n;r]{neg[x]>.[-]y}[n;]bs[f;]/r} / short list
rng:{x+til y-x-1}. / rangea[`$"7-1"]:minfc[::]eachrngsl[fc[::];5;]frdfm:sumstil1+maxfrda[`$"7-2"]:minfc[fm]eachrngsl[fc[fm];5;]frd