34 lines
773 B
Haskell
34 lines
773 B
Haskell
|
import Aoc
|
||
|
|
|
||
|
|
numWays :: Int -> [Int] -> Int
|
||
|
|
numWays 0 _ = 1
|
||
|
|
numWays _ [] = 0
|
||
|
|
numWays n (x:xs)
|
||
|
|
| n > 0 = numWays (n-x) xs + numWays n xs
|
||
|
|
| otherwise = 0
|
||
|
|
|
||
|
|
part1 :: [Int] -> Int
|
||
|
|
part1 = numWays 150
|
||
|
|
|
||
|
|
numWays' :: Int -> [Int] -> (Int, Int)
|
||
|
|
numWays' 0 _ = (0, 1)
|
||
|
|
numWays' _ [] = (0, 0)
|
||
|
|
numWays' n (x:xs)
|
||
|
|
| n < 0 = (0, 0)
|
||
|
|
| w1 == 0 = (m0 + 1, w0)
|
||
|
|
| w0 == 0 = (m1, w1)
|
||
|
|
| m0 > m1 -1 = (m1, w1)
|
||
|
|
| m0 == m1 - 1 = (m1, w0 + w1)
|
||
|
|
| m0 < m1 -1 = (m0 + 1, w0)
|
||
|
|
| otherwise = undefined
|
||
|
|
where
|
||
|
|
(m0, w0) = numWays' (n-x) xs
|
||
|
|
(m1, w1) = numWays' n xs
|
||
|
|
|
||
|
|
-- numWays and numWays' can be combined, but I think that that will make it too messy
|
||
|
|
|
||
|
|
part2 :: [Int] -> Int
|
||
|
|
part2 = snd . numWays' 150
|
||
|
|
|
||
|
|
main :: IO ()
|
||
|
|
main = aocMain (map read) part1 part2
|