Strict fold
[advent-of-code-16.git] / advent14parallel.hs
1 import Data.List (nub, tails)
2 import Data.ByteString.Char8 (pack)
3 import Crypto.Hash (hash, Digest, MD5)
4 import Control.Parallel.Strategies (withStrategy, parBuffer, rdeepseq)
5
6 salt = "yjdafjpo"
7 -- salt = "abc"
8
9 stretch_factor = [1..2016]
10 -- stretch_factor = [1..100]
11
12 main :: IO ()
13 main = do
14 part1
15 part2
16
17 part1 :: IO ()
18 part1 = print $ head $ drop 63 $ filter (\i -> possibleKey sq i && confirmKey sq i) [0..]
19 where sq = md5sequence
20
21 part2 :: IO ()
22 part2 = print $ head $ drop 63 $ filter (\i -> possibleKey sq i && confirmKey sq i) [0..]
23 where sq = md5sequenceS
24
25 getHash :: String -> String
26 getHash bs = show (hash $ pack bs :: Digest MD5)
27
28 md5sequence :: [String]
29 -- md5sequence = [makeMd5 i | i <- [0..]]
30 md5sequence = withStrategy (parBuffer 100 rdeepseq) $ map (makeMd5) [0..]
31 where makeMd5 i = getHash (salt ++ show i)
32
33 md5sequenceS :: [String]
34 -- md5sequenceS = [makeMd5 i | i <- [0..]]
35 md5sequenceS = withStrategy (parBuffer 100 rdeepseq) $ map (makeMd5) [0..]
36 where makeMd5 i = stretch $ getHash (salt ++ show i)
37 stretch h0 = foldr (\_ h -> getHash h) h0 stretch_factor
38
39 possibleKey :: [String] -> Int-> Bool
40 possibleKey s = not . null . repeats 3 . ((!!) s)
41
42 confirmKey :: [String] -> Int -> Bool
43 confirmKey s i = any (confirmation) $ take 1000 $ drop (i+1) s
44 where c = head $ repeats 3 $ s!!i
45 confirmation m = c `elem` (repeats 5 m)
46
47 repeats :: Int -> String -> [String]
48 repeats n = filter (null . tail) . map (nub) . substrings n
49
50 substrings :: Int -> [a] -> [[a]]
51 substrings l = filter (\s -> (length s) == l) . map (take l) . tails