104 lines
3.5 KiB
Haskell
104 lines
3.5 KiB
Haskell
-- everything stolen from http://learnyouahaskell.com/zippers#a-very-simple-file-system
|
|
|
|
import Control.Monad
|
|
|
|
data Inode = Dir Name [Inode] | File Name Size deriving(Show)
|
|
type Name = String
|
|
type Size = Int
|
|
data Command = Ls | Cd Name | CdUp | CdRoot deriving(Show)
|
|
data Line = LineC Command | LineI Inode deriving(Show)
|
|
|
|
parseCommand :: String -> Command
|
|
parseCommand "ls" =Ls
|
|
parseCommand "cd .." =CdUp
|
|
parseCommand ('c':'d':' ':name) =(Cd name)
|
|
|
|
parseInode :: String -> Inode
|
|
parseInode ('d':'i':'r':' ': name) = Dir name []
|
|
parseInode input = File (drop 1 $ dropWhile (/= ' ') input) (read $ takeWhile (/= ' ') input)
|
|
|
|
|
|
parseEither :: String -> Line
|
|
parseEither ('$':' ':command) =LineC $ parseCommand command
|
|
parseEither input= LineI $ parseInode input
|
|
|
|
foldFunction :: FSZipper -> Line -> FSZipper
|
|
foldFunction zipper (LineC Ls) = zipper
|
|
foldFunction zipper (LineC (Cd name)) = fsTo name zipper
|
|
foldFunction zipper (LineC CdUp) = fsUp zipper
|
|
foldFunction zipper (LineI inode) = fsNewInode inode zipper
|
|
|
|
data FSCrumb = FSCrumb Name [Inode] [Inode] deriving (Show)
|
|
|
|
type FSZipper = (Inode,[FSCrumb])
|
|
|
|
fsUp :: FSZipper -> FSZipper
|
|
fsUp (item, FSCrumb name ls rs:bs) = (Dir name (ls ++ [item] ++ rs), bs)
|
|
|
|
|
|
fsUpToRoot :: FSZipper -> FSZipper
|
|
fsUpToRoot ((Dir "/" content),bc) = ((Dir "/" content),bc)
|
|
fsUpToRoot zipper = fsUp zipper
|
|
|
|
fsTo :: Name -> FSZipper -> FSZipper
|
|
fsTo name (Dir folderName items, bs) =
|
|
let (ls, item:rs) = break (nameIs name) items
|
|
in (item, FSCrumb folderName ls rs:bs)
|
|
|
|
nameIs :: Name -> Inode -> Bool
|
|
nameIs name (Dir folderName _) = name == folderName
|
|
nameIs name (File fileName _) = name == fileName
|
|
|
|
|
|
fsNewInode :: Inode -> FSZipper -> FSZipper
|
|
fsNewInode newInode ((Dir name content),bc) = (Dir name (newInode:content),bc)
|
|
|
|
initZipper :: FSZipper
|
|
initZipper = (Dir "/" [],[])
|
|
|
|
|
|
data InodeSize = DirS Size | FileS Size deriving(Show)
|
|
|
|
getSize (DirS s )=s
|
|
getSize (FileS s)=s
|
|
|
|
flattenToSmallDirs :: Inode -> (InodeSize,[InodeSize])
|
|
flattenToSmallDirs (Dir _ children) =
|
|
let childSizes =map flattenToSmallDirs children
|
|
currentSize =(sum $ map getSize $ map fst childSizes) in
|
|
(DirS currentSize ,filter isDir $ join $ map combineOwnWithChildSize childSizes )
|
|
flattenToSmallDirs (File _ size) = (FileS size,[])
|
|
|
|
combineOwnWithChildSize :: (InodeSize,[InodeSize]) -> [InodeSize]
|
|
combineOwnWithChildSize (own,children) = own:children
|
|
|
|
filterSmallDirs :: [InodeSize] -> [Size]
|
|
filterSmallDirs ((DirS s):rest) = if (s<100000) then s:(filterSmallDirs rest) else filterSmallDirs rest
|
|
filterSmallDirs ((FileS _):rest) = filterSmallDirs rest
|
|
filterSmallDirs [] = []
|
|
|
|
isDir :: InodeSize -> Bool
|
|
isDir (DirS _)= True
|
|
isDir (FileS _)=False
|
|
|
|
mainP1 :: IO ()
|
|
mainP1 = do
|
|
content <- readFile "seven-input.txt"
|
|
let statements = map parseEither $ drop 1 $ lines content
|
|
let a = foldl foldFunction initZipper statements
|
|
print $ sum $ filterSmallDirs $ combineOwnWithChildSize $ flattenToSmallDirs $ fst $ fsUpToRoot a
|
|
|
|
|
|
mainP2::IO ()
|
|
mainP2 = do
|
|
content <- readFile "seven-input.txt"
|
|
let statements = map parseEither $ drop 1 $ lines content
|
|
a = foldl foldFunction initZipper statements
|
|
(rootSize, dirSizes) =flattenToSmallDirs $ fst $ fsUpToRoot a
|
|
currentlyFree=(70000000- getSize rootSize)
|
|
requiredCleanup = 30000000-currentlyFree
|
|
largeEnoughDirs = filter (\s -> s >= requiredCleanup) $ map getSize dirSizes
|
|
print $ minimum largeEnoughDirs
|
|
|
|
main = mainP2
|