add day10

4 files changed, 133 insertions, 0 deletions

diff --git a/aoc.cabal b/aoc.cabal
index 0957baa..bcb8d8c 100644
--- a/aoc.cabal
+++ b/aoc.cabal
@@ -75,3 +75,9 @@ executable Day09
   build-depends:       base, aoc, containers, parsec
   default-language:    Haskell2010
   hs-source-dirs:      execs
+
+executable Day10
+  main-is:             Day10.hs
+  build-depends:       base, aoc, containers, monad-memo
+  default-language:    Haskell2010
+  hs-source-dirs:      execs
diff --git a/execs/Day10.hs b/execs/Day10.hs
new file mode 100644
index 0000000..c42a550
--- /dev/null
+++ b/execs/Day10.hs
@@ -0,0 +1,29 @@
+
+module Main where
+
+import Utils
+import Data.List (sort)
+import Control.Monad
+import Control.Monad.Memo
+
+parseLine :: String -> Int
+parseLine = read
+
+diffs :: [Int] -> Int
+diffs s = product $ ($ q s) <$> [howMany (==1), howMany (==3)]
+    where q = zipWith subtract `ap` tail
+
+combos top s = startEvalMemo $ go 0
+    where go c
+            | c == top = return 1
+            | otherwise = do
+                let cs = filter (`elem` s) $ map (+c) [1,2,3]
+                sum <$> mapM (memo go) cs
+
+main :: IO ()
+main = do
+    n <- map parseLine . lines <$> readFile "input/10"
+    let top = maximum n + 3
+        ls = sort (0:top:n)
+    print $ diffs ls
+    print $ combos top ls
diff --git a/input/10 b/input/10
new file mode 100644
index 0000000..0e77ade
--- /dev/null
+++ b/input/10
@@ -0,0 +1,92 @@
+56
+139
+42
+28
+3
+87
+142
+57
+147
+6
+117
+95
+2
+112
+107
+54
+146
+104
+40
+26
+136
+127
+111
+47
+8
+24
+13
+92
+18
+130
+141
+37
+81
+148
+31
+62
+50
+80
+91
+33
+77
+1
+96
+100
+9
+120
+27
+97
+60
+102
+25
+83
+55
+118
+19
+113
+49
+133
+14
+119
+88
+124
+110
+145
+65
+21
+7
+74
+72
+61
+103
+20
+41
+53
+32
+44
+10
+34
+121
+114
+67
+69
+66
+82
+101
+68
+84
+48
+73
+17
+43
+140
diff --git a/lib/Utils.hs b/lib/Utils.hs
index 1381f16..61c4e49 100644
--- a/lib/Utils.hs
+++ b/lib/Utils.hs
@@ -43,3 +43,9 @@ sublists = concatMap inits . tails
 
 windows :: Int -> [a] -> [[a]]
 windows m = foldr (zipWith (:)) (repeat []) . take m . tails
+
+kadane :: [Int] -> Int
+kadane = go 0 0
+    where go :: Int -> Int -> [Int] -> Int
+          go best _ [] = best
+          go best current (l:ls) = go (max best (current + l)) (max current (current + l)) ls