advent day seven

DaySeven.hs

{-# LANGUAGE OverloadedStrings #-}

module DaySeven
    ( go
    ) where
import qualified Data.Text as T
import qualified Data.Text.IO as TI
import qualified Data.Maybe as M
import qualified Data.List as L
import qualified Control.Monad.State as S
import qualified Control.Monad as CM

-- ############# data types ####################
data Cmd = CdCmd T.Text | LsCmd | CdUpCmd deriving (Show, Eq)
data OutputLine = DirOutput T.Text | FileOutput Integer T.Text deriving (Show, Eq)
data Line = CmdLine Cmd | OutputLine OutputLine deriving (Show, Eq)

data Node = Node T.Text [OutputLine] [Node] deriving (Show, Eq)

children (Node _ _ c) = c
immediateContents (Node _ stuff _) = stuff


-- ############# parsing  ####################
parseCmd line = if T.isInfixOf " cd " line
                  then
                    if line == "$ cd .." then CdUpCmd else CdCmd (L.last splitted)
                  else LsCmd
                where splitted = T.split (== ' ') line

parseOutput line = if T.isPrefixOf "dir " line
                  then DirOutput (L.last splitted)
                  else FileOutput (read $ T.unpack $ L.head splitted) $ L.last splitted
                where splitted = T.split (== ' ') line

parse line = if firstChar == '$'
               then CmdLine $ parseCmd line
               else OutputLine $ parseOutput line
             where firstChar = L.head $ T.unpack line

-- ############# build directory tree  ####################
 -- no lines left to process
treeify soFar [] = (soFar, [])
-- single output gets tacked onto current node
treeify soFar@(Node dirName outputs children) rest@((OutputLine singleOutput) : others) = treeify (Node dirName (singleOutput : outputs) children) $ tail rest
-- ignore Ls commands
treeify soFar rest@((CmdLine (LsCmd)) : others) = treeify soFar $ tail rest
-- CD into new node
treeify soFar@(Node dirName outputs children) rest@((CmdLine (CdCmd subDir)) : others) = treeify newNode newRemaining
  where (subNode, newRemaining) = treeify (Node subDir [] []) others
        newNode = Node dirName outputs (subNode : children)
-- CD back upwards
treeify soFar rest@((CmdLine (CdUpCmd)) : others) = (soFar, others)

rootNode = (Node "root" [] [])


-- ############# tree inspection  ####################

totalSize :: Node -> Integer
totalSize node = immediateSize + sum (map totalSize (children node))
  where immediateSize = sum $ map rowSize $ immediateContents node
        rowSize (DirOutput _) = 0
        rowSize (FileOutput size _) = size

allNodeSizes :: Node -> [Integer]
allNodeSizes node  = (totalSize node) : (concatMap allNodeSizes $ children node)

totalDiskSpace = 70000000
minSpaceNeeded = 30000000

go :: String -> IO (Integer, Integer)
go path = do
  input <- TI.readFile path
  let
    parsed = map parse $ T.lines input
    (asTree, _) = treeify rootNode parsed
    dirTree = head $ children $ asTree
    deletionNeeded = minSpaceNeeded - remainingSpace
    remainingSpace = totalDiskSpace - (totalSize dirTree)
    largeEnough = filter (>= deletionNeeded) $ allNodeSizes dirTree
    toDelete = minimum largeEnough
    totalSmallNodesSize = sum $ filter (<= 100000) $ allNodeSizes dirTree
  return $ (totalSmallNodesSize, toDelete)