2020/10.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)