1 files changed, 22 insertions, 0 deletions
diff --git a/2021/7.hs b/2021/7.hs
new file mode 100644
index 0000000..cd11cd9
--- /dev/null
+++ b/2021/7.hs
@@ -0,0 +1,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)