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.

2 files changed, 121 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)
diff --git a/2020/10.in b/2020/10.in
new file mode 100644
index 0000000..8ae9092
--- /dev/null
+++ b/2020/10.in
@@ -0,0 +1,98 @@
+118
+14
+98
+154
+71
+127
+38
+50
+36
+132
+66
+121
+65
+26
+119
+46
+2
+140
+95
+133
+15
+40
+32
+137
+45
+155
+156
+97
+145
+44
+153
+96
+104
+58
+149
+75
+72
+57
+76
+56
+143
+11
+138
+37
+9
+82
+62
+17
+88
+33
+5
+10
+134
+114
+23
+111
+81
+21
+103
+126
+18
+8
+43
+108
+120
+16
+146
+110
+144
+124
+67
+79
+59
+89
+87
+131
+80
+139
+31
+115
+107
+53
+68
+130
+101
+22
+125
+83
+92
+30
+39
+102
+47
+109
+152
+1
+29
+86