This year was the 4th installment of Advent of Code and like the last years I focused on doing the puzzles in Haskell.
For the most part the puzzles where interesting and there where some gems in there that I had to research long forgotten algorithms again to get it done in reasonable time.
Then came day 23.
I don't want to spoil too much so please go at the site and read the nice little story for yourself.
Basically you are given a list of about 1000 coordinates in 3D together with a radius. The coordinates are quite big and span a huge bounding box.
The first part (there are always two parts) is quite simple: you should just find the input with the largest radius and count all other nanobots (each input line is called a nanobot in the story) that are in range. Meaning the Manhatten-Distance between the strongest (biggest radius) bot and this other bot is less then the radius of our champion.
After parsing the input that's quite easy.
Then comes part 2 ... you are asked to find a coordinate that is in range of
the most nanobots and if there are more than one position with the same
amount of bots in range you should pick the one that is closer to the origin
I have to admit: I had to think quite some time on this - the naive solution of trying each coordinate is practically impossible giving the huge bounding-box in 3D.
So thinking it's a cheap trick I tried only the given coords plus the vertices of the box given by these middle-points + the bots radius. Which would only meant checking around 9000 positions.
I think it even worked for the examples but of course it's wrong for the real input ... damn (btw: it's a nice task to figure out why this does not work, can you find a counter-example to this naive algorithm?)
Luckily I remembered an algorithm that is basically binary interval search in 3D - you start with the complete bounding box iteratively slice it into 8 half-size boxes always checking which one intersects the most bot-boxes.
This gives a quite fast solution and looks like this in Haskell (see Solution.hs for the complete solution):
search :: [Nanobot] -> Coord search bots = go startCubeRadius $ bounds bots where go 1 bds = bestCoord 1 $ candidates 1 bds go cubeRadius bds = if cubeRadius <= 1 then bestC else go (cubeRadius `div` 2) ((x-cubeRadius, y-cubeRadius, z-cubeRadius), (x+cubeRadius,y+cubeRadius,z+cubeRadius)) where bestC@(x,y,z) = bestCoord cubeRadius $ candidates cubeRadius bds -- find a power of 2 such that every bot is in the cube startCubeRadius = let ((minX, minY, minZ), (maxX, maxY, maxZ)) = bounds bots in findNextPower $ maximum [maxX - minX, maxY - minY, maxZ - minZ] -- find the coord in 'crds' where a cube around it with radius 'cubeRadius' intersects the most bots bestCoord cubeRadius crds = let coordAndCount = map (botsInRange cubeRadius &&& id) crds bestCount = maximum $ map fst coordAndCount in minimumBy (comparing $ dist (0,0,0)) $ map snd $ filter ((== bestCount) . fst) coordAndCount botsInRange cubeRadius c = length $ filter (intersect cubeRadius c) bots intersect cubeRadius c bot = dist c (nanobotPos bot) < cubeRadius + nanobotRadius bot -- candidates for coords are the vertices of all dividing sub-cubes candidates cubeLen bds = let ((minX, minY, minZ), (maxX, maxY, maxZ)) = bds in [(x,y,z) | x <- [minX,minX+cubeLen..maxX-1] , y <- [minY,minY+cubeLen..maxY-1] , z <- [minZ,minZ+cubeLen..maxZ-1] ] findNextPower n = head $ dropWhile (< n) $ iterate (*2) 1
But this post is not really about this solution.
people used what?
In this case I was quite proud (no I did get no points - never did, probably never will, those folks are insanely quick and I did not bother to wake up early to do this), and so I looked at reddit to see what other people did.
Indeed some used basically the same algorithm, some tried some greedy annealing like process (which I'm quite surprised worked) and then there where some who used SMT Solvers.
This really sparked my interest. And I finally found some time to play with it.
choosing a library/solver
I looked around a bit and it became quite clear that Z3 is a good choice as I wanted to try bindings with Haskell.
Initially I tried z3 Bindings for the Z3 Theorem Prover and after some confusion I got it working (turns out it only works with the 4.6.0 release, the Ubuntu repos only had 4.4 and I manually downloaded 4.8.x).
But this one does not seem to have bindings for the optimization part.
Next I looked at sbv and this one is a gem. Not only does it include everything for optimization, it also works with quite a lot of solvers and yes Z3 is the default and very easy to use.
I just downloaded the newest release from here,
extracted the files somewhere and made a symbolic link to the
z3 binary (in
./bin) into a
folder that sits on my path.
SBV calls the binary directly so that's enough - if you have something that needs to link to
the libraries you probably have to add the includes and library paths to your build system
(in Haskell/Stack this is done by adding entries to the
stack.yaml) or you can
put the header files in
/usr/incldue and the libraries in
usr/lib this is where
most linkers/compilers expect them to be on *nix.
The rest was actually quite simple (you can find the complete file here).
SBV abstracts away many thinks and give you some monads to work in.
Literals and Variables are instances of all the obvious calculation/math classes like
so modelling is as simple as implementing it directly.
Just prepare to implement things like
abs for yourself (maybe I missed it but I doubt that) the rest
was easy for this case:
part2 :: [Nanobot] -> IO () part2 bots = do -- optimize and make sure that the "bots in range" goal is more important than "distance from origin" res <- optimize Lexicographic $ script bots print res script :: [Nanobot] -> Goal script bots = do xV <- sInteger "x" yV <- sInteger "y" zV <- sInteger "z" maximize "bots in range" $ sum $ map (isInRange (xV,yV,zV)) bots minimize "distance from origin" $ mkAbs xV + mkAbs yV + mkAbs zV where -- 1 if xV,yV,zV is in range of the given bot - 0 otherwise isInRange (xVar, yVar, zVar) bot = ite (distFrom (xVar, yVar, zVar) bot .<= fromIntegral (nanobotRadius bot)) 1 (0 :: SInteger) -- manhatten distance distFrom (xVar, yVar, zVar) bot = let (x',y',z') = nanobotPos bot in mkAbs (xVar - fromIntegral x') + mkAbs (yVar - fromIntegral y') + mkAbs (zVar - fromIntegral z') mkAbs x = ite (0 .< x) x (negate x)
I'm no expert at all (indeed I'm a bloody noob) so maybe there are better ways but here I choose to
define 3 variables
x, y, v and then
maximize the number of bots in range of these coordinate and,
with lower priority - that's what the
Lexicographic is for -
minimize the distance to the origin.
I only had to write the 3 helpers in the
mkAbsis a simple implementation of
abs(checks if the variable given is bigger then 0, if so just returns the variable, if not the negated value -
iteis SBV/Z3s version of
distFromis calculating the Manhattan distance between the coordinate given by the variables and the fixed coordinates of a bot
isInRangeis 1 if the variable is in range of the bot and 0 else. I had to annotated the
0to disambiguate types.
Well it works and prints
But it's a lot slower then the algorithm I showed above. I guess it's not that surprising (given the poor modeling I did) but I was almost expecting more from the way people scored with this.
I did not measure the time but it takes around 1 minute I think.
If anybody can give me some hints on how I can make this quicker with Z3 please leave me a message on Twitter or even better make a PR ;)
I like the approach and I will look more into Z3 in the future.
I think the next task will be to let it search for magic squares - my naive list-comprehension algorithm is OK for 4x4 squares but already fails at 5x5 and this solver should be able to get this quicker right?