summaryrefslogtreecommitdiff
path: root/2020
diff options
context:
space:
mode:
authorTom Smeding <tom.smeding@gmail.com>2020-12-13 21:47:50 +0100
committerTom Smeding <tom.smeding@gmail.com>2020-12-13 21:47:50 +0100
commitd90266f905d2713c23bf3512f4bb654e8e148174 (patch)
treeda6e5681ddeeb68d8e3e1ad0ec0f4f8ad50f8c5a /2020
parent3ca5033e1ddd578dd5c6a3b0e8488751c879f10b (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')
-rw-r--r--2020/10.hs23
-rw-r--r--2020/10.in98
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