--- AOC Day 7: The Treachery of Whales ---

A giant whale has decided your submarine is its next meal, and it’s much faster than you are. There’s nowhere to run!

Suddenly, a swarm of crabs (each in its own tiny submarine - it’s too deep for them otherwise) zooms in to rescue you! They seem to be preparing to blast a hole in the ocean floor; sensors indicate a massive underground cave system just beyond where they’re aiming!

The crab submarines all need to be aligned before they’ll have enough power to blast a large enough hole for your submarine to get through. However, it doesn’t look like they’ll be aligned before the whale catches you! Maybe you can help?

There’s one major catch - crab submarines can only move horizontally.

You quickly make a list of the horizontal position of each crab (your puzzle input). Crab submarines have limited fuel, so you need to find a way to make all of their horizontal positions match while requiring them to spend as little fuel as possible.

For example, consider the following horizontal positions:

16,1,2,0,4,2,7,1,2,14

This means there’s a crab with horizontal position 16, a crab with horizontal position 1, and so on.

Each change of 1 step in horizontal position of a single crab costs 1 fuel. You could choose any horizontal position to align them all on, but the one that costs the least fuel is horizontal position 2:

  • Move from 16 to 214 fuel
  • Move from 1 to 21 fuel
  • Move from 2 to 20 fuel
  • Move from 0 to 22 fuel
  • Move from 4 to 22 fuel
  • Move from 2 to 20 fuel
  • Move from 7 to 25 fuel
  • Move from 1 to 21 fuel
  • Move from 2 to 20 fuel
  • Move from 14 to 212 fuel

This costs a total of 37 fuel. This is the cheapest possible outcome; more expensive outcomes include aligning at position 1 (41 fuel), position 3 (39 fuel), or position 10 (71 fuel).

Determine the horizontal position that the crabs can align to using the least fuel possible. How much fuel must they spend to align to that position?

 

All credit for the above puzzle goes to Eric Wastl and Advent of Code.

Don’t forget to submit your solutions at adventofcode.com**** and join the KX leaderboard using code 1526329-bb0915a5.

This post includes solutions!

In today’s 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 we’ll 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 that’s 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’, we’d 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 it’s 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