diff options
author | Tom Smeding <tom.smeding@gmail.com> | 2020-12-13 21:47:50 +0100 |
---|---|---|
committer | Tom Smeding <tom.smeding@gmail.com> | 2020-12-13 21:47:50 +0100 |
commit | d90266f905d2713c23bf3512f4bb654e8e148174 (patch) | |
tree | da6e5681ddeeb68d8e3e1ad0ec0f4f8ad50f8c5a /2020/10.hs | |
parent | 3ca5033e1ddd578dd5c6a3b0e8488751c879f10b (diff) |
Day 10
This one is particularly nice in Haskell, since transforming the naive
recursive function to a memoised, linear form was literally a matter of
writing the recursion using an explicit fixpoint combinator, and then
replacing the recursive call with a lazy array index. This is where
laziness shines.
Diffstat (limited to '2020/10.hs')
-rw-r--r-- | 2020/10.hs | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/2020/10.hs b/2020/10.hs new file mode 100644 index 0000000..b1c2f69 --- /dev/null +++ b/2020/10.hs @@ -0,0 +1,23 @@ +module Main where + +import qualified Data.Array as A +import Data.List (sort) + +import Input + + +main :: IO () +main = do + input <- map read <$> getInput 10 :: IO [Int] + let deviceRate = maximum input + 3 + input' = 0 : deviceRate : input + diffs = zipWith (-) (tail (sort input')) (sort input') + print (length (filter (== 1) diffs) * length (filter (== 3) diffs)) + + let numArrangements _ 0 = 1 :: Int + numArrangements recur target = + let suitable = filter (\i -> target - 3 <= i && i < target) (0 : input) + in sum (map recur suitable) + dyn = A.listArray (0, deviceRate) [numArrangements (dyn A.!) i | i <- [0..deviceRate]] + -- print (Data.Function.fix numArrangements deviceRate) -- naive recursion + print (dyn A.! deviceRate) |