/
Euler79.hs
31 lines (26 loc) · 961 Bytes
/
Euler79.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
module Main
where
import Common (numberToDigits, inputFileInteract)
import Data.List
import qualified Data.IntSet as I
import qualified Data.Map as M
-- [3,1,7] -> [(3,[]),(1,[3]),(7,[3,1])]
before :: [a] -> [(a, [a])]
before xs = zipWith (\a b -> (a,b)) xs (init . inits $ xs)
-- Solution is straightforward:
-- Build a map from numbers to the preceding number set and sort
-- by the cardinality of these sets.
analyse :: [(Int, [Int])] -> Int
analyse l = getMax . analyse' l $ M.empty
where
analyse' [] m = m
analyse' ((x,xs):ys) m
= analyse' ys (M.insertWith I.union x (I.fromList xs) m)
getMax m = foldl1 (\a b -> a*10 + b) . map fst .
sortBy (\(_,a) (_,b) -> compare a b) .
M.toList . M.map (\a -> I.size a) $ m
main :: IO ()
main = inputFileInteract processInput
where
processInput = analyse . concatMap (before . numberToDigits) .
map read . words