2021/7.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

module Main where

import Data.List
import Data.Ord

import Input
import Util


main :: IO ()
main = do
    inp <- map read . toList . splitOn (== ',') . head <$> getInput 7
    let distfun1 x = sum [abs (x - p) | p <- inp] :: Int
        distfun2 x = sum [let d = abs (x - p) in d * (d + 1) `div` 2 | p <- inp]
        ternsearch lo hi f
          | hi - lo <= 2 = minimumBy (comparing f) [lo, lo + (hi - lo) `div` 2, hi]
          | otherwise =
              let m1 = lo + (hi - lo) `div` 3
                  m2 = lo + 2 * (hi - lo) `div` 3
              in if f m1 < f m2 then ternsearch lo m2 f else ternsearch m1 hi f
    print (distfun1 $ ternsearch (minimum inp) (maximum inp) distfun1)
    print (distfun2 $ ternsearch (minimum inp) (maximum inp) distfun2)