import Data.Char
import Data.List

type Id = Int
type Len = Int
data Block = Data Id Len | Free Len deriving Show
type HDD = [Block]

getDataFree :: HDD -> Id -> [Len] -> HDD
getDataFree acc id (d:[]) =
  acc ++ [Data id d]
getDataFree acc id (d:f:r) =
  getDataFree (acc ++ [Data id d, Free f]) (id + 1) r

consume :: String -> HDD
consume file =
  getDataFree [] 0 $ map digitToInt $ trim file
  where trim = dropWhileEnd isSpace . dropWhile isSpace

frag1 :: HDD -> HDD -> HDD -> HDD
frag1 acc dt (Free _:rest) =
  frag1 acc dt rest
frag1 acc (Data di dl:dr) p@(Data pi pl:_)
  | di == pi = (Data pi pl:acc)
  | otherwise = frag1 (Data di dl:acc) dr p
frag1 acc (Free f:rest) (Data id d:pack)
  | d < f = frag1 (Data id d:acc) (Free (f - d):rest) pack
  | d == f = frag1 (Data id d:acc) rest pack
  | d > f = frag1 (Data id f:acc) rest (Data id (d - f):pack)

frag :: HDD -> HDD
frag hdd = reverse $ frag1 [] hdd (reverse hdd)

checksum :: Int -> Int -> HDD -> Int
checksum acc _ [] = acc
checksum acc ix (Data id len:rest) =
  checksum (acc + (sum $ map (id*) [ix..ix+len-1])) (ix + len) rest

part1 :: HDD -> Int
part1 = (checksum 0 0) . frag

main = do
  file <- readFile "day09.input"
  let hdd = consume file
  putStrLn ("Part 1: " ++ (show $ part1 hdd))
  --putStrLn ("Part 2: " ++ (show $ part2 hdd))