9-2

1 files changed, 48 insertions, 0 deletions

diff --git a/9-2.hs b/9-2.hs
new file mode 100644
index 0000000..361b9d1
--- /dev/null
+++ b/9-2.hs
@@ -0,0 +1,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