blob: 361b9d1c93c69debce2cf6d9983b0cd2d1ba6128 (
plain)
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
|
import Data.Foldable (toList)
import Data.Sequence hiding (replicate, zip)
type FS = Seq File
data File = File { fid :: Int, size :: Int } | Blank { size :: Int }
deriving (Eq, Show)
doOne :: FS -> Maybe FS
doOne = go Empty
where
go :: FS -> FS -> Maybe FS
go _ Empty = Nothing
go _ (_ :|> (Blank _)) = Nothing
go res (y@(Blank l) :<| ys@(xs :|> x@(File _ k)))
| k <= l = Just $ res <> (x :<| Blank (l-k) :<| (xs :|> Blank k))
| otherwise = go (res :|> y) ys
go res (x :<| xs) = go (res :|> x) xs
rearrange :: FS -> FS
rearrange Empty = Empty
rearrange ys@(xs :|> x) = case doOne ys of
Nothing -> rearrange xs :|> x
Just zs -> rearrange zs
parse :: String -> Seq File
parse = go 0 Empty
where
go :: Int -> Seq File -> String -> Seq File
go _ res [] = res
go n res (x:xs) = go' (n+1) (res :|> File n (f x)) xs
go' :: Int -> Seq File -> String -> Seq File
go' _ res [] = res
go' n res (x:xs) = go n (res :|> Blank (f x)) xs
f :: Char -> Int
f = read . pure
expand :: File -> [Int]
expand (Blank n) = replicate n 0
expand (File i n) = replicate n i
checksum :: FS -> Int
checksum = sum . fmap (uncurry (*)) . zip [0..] . concatMap expand . toList
main :: IO ()
main = getLine >>= print . checksum . rearrange . parse
|
