-
Notifications
You must be signed in to change notification settings - Fork 0
/
1.hs
71 lines (63 loc) · 2.12 KB
/
1.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
{-# LANGUAGE TypeApplications #-}
import Data.List
dummyData :: [Int]
dummyData = [ 1721
, 979
, 366
, 299
, 675
, 1456 ]
main = do
let result = dummyData `addUpTo` 2020
print result
print $ fmap (uncurry (*)) result
print "----------------"
file <- readFile "1.input"
let contents = (fmap (read @Int) $ lines file)
let res2 = contents `addUpTo` 2020
print res2
print $ fmap (uncurry (*)) res2
print "----------------"
let res3 = repAddUpTo 2020 3 contents
print res3
print $ fmap product res3
{-
print "----------------"
let res4 = addUpTo' contents 2020 2
print res4
print $ fmap product res4
-}
-- very inefficient due to the permutations call;
-- too many idential permutations of length c generated
addUpTo' :: [Int] -> Int -> Int -> Maybe [Int]
addUpTo' l i c = headMaybe
$ filter ((==i) . sum)
$ map (take c)
$ permutations l
headMaybe :: [a] -> Maybe a
headMaybe [] = Nothing
headMaybe (a:_) = Just a
addUpTo :: [Int] -> Int -> Maybe (Int, Int)
addUpTo [] _ = Nothing
addUpTo (a:[]) _ = Nothing
addUpTo (h:t) i
| length result > 0 = Just $ (h, head result)
| otherwise = t `addUpTo` i
where
result = filter ((==i) . (+h)) t
repAddUpTo :: Int -> Int -> [Int] -> Maybe [Int]
repAddUpTo num count list = go (count-1) $ map return list
where
go :: Int -> [[Int]] -> Maybe [Int]
go 0 prev = headMaybe $
filter (\y -> length y == count && sum y == num) prev
go n' prev = go (n'-1) newPrev
where
prevWithCandidates :: [([Int], [Int])]
prevWithCandidates = map (\p ->
(p, filter (\l -> not (elem l p) && (sum p)+l <= num) list)
) prev
newPrev :: [[Int]]
newPrev = intercalate []
$ map (\(p, is) -> map (:p) is)
prevWithCandidates