AoC Day 7: The Treachery of Whales

Advent of Code day 7, “the Treachery of Whales” is a bit weird, in that I didn’t really code my way to the gold stars. Still, it accepts a rather simple coded solution, so let’s write it out. This post is literate Haskell, here are some imports.

import Control.Arrow   ((&&&))
import Data.List.Split (wordsBy)
import Data.Array      (listArray,(!))

The general idea is to find a position that minimizes the sum of costs to reach it. Now cost is very closely related to distance, which is a convex function; so is a sum of multiple of it,¹ so we can find its minimum in logarithmic time using (integer) ternary search.

tsearch :: (Int -> Int) -> Int -> Int -> Int
tsearch f lo hi
  | hi - lo < 3 = minimum $ f <$> [lo..hi-1]
  | f a < f b = tsearch f lo b
  | otherwise = tsearch f a hi
  where a = (2*lo + hi) `div` 3
        b = (lo + 2*hi) `div` 3

In part 1, the cost is exactly the distance.

part1 :: [Int] -> Int
part1 ps = tsearch (sumDistTo ps id) (minimum ps) (maximum ps + 1)

sumDistTo :: [Int] -> (Int -> Int) -> Int -> Int
sumDistTo ps f p = sum [ f (abs (p'-p)) | p' <- ps ]

In part 2, the cost is a staircase function of “sum of the step indices”.

staircase :: Int -> Int
staircase = (listArray (0,1999) cs !) where cs = 0 : zipWith (+) cs [1..]

part2 :: [Int] -> Int
part2 ps = tsearch (sumDistTo ps staircase) (minimum ps) (maximum ps + 1)

A short wrapper to perform it all.

main :: IO ()
main = interact $ show . (part1 &&& part2) . map read . wordsBy (== ',')

This concludes the coded aspect of today’s solution. See you soon!

I cross-read that proposition over multiple times. It really is correct. Garden-path, yes, but correct.↩︎