Day 9: Disk Fragmenter
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
3 points
*
Second attempt! I like this one much better.
Edit: down to 0.040 secs now!
import Control.Arrow
import Data.Either
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
type Layout = ([(Int, (Int, Int))], Map Int Int)
readInput :: String -> Layout
readInput =
map (read . singleton) . head . lines
>>> (scanl' (+) 0 >>= zip) -- list of (pos, len)
>>> zipWith ($) (intersperse Right [Left . (id,) | id <- [0 ..]])
>>> partitionEithers
>>> filter ((> 0) . snd . snd) *** Map.filter (> 0) . Map.fromAscList
checksum :: Layout -> Int
checksum = sum . map (\(id, (pos, len)) -> id * len * (2 * pos + len - 1) `div` 2) . fst
compact :: (Int -> Int -> Bool) -> Layout -> Layout
compact select (files, spaces) = foldr moveFile ([], spaces) files
where
moveFile file@(fileId, (filePos, fileLen)) (files, spaces) =
let candidates = Map.assocs $ fst . Map.split filePos $ spaces
in case find (select fileLen . snd) candidates of
Just (spacePos, spaceLen) ->
let spaces' = Map.delete spacePos spaces
in if spaceLen >= fileLen
then
( (fileId, (spacePos, fileLen)) : files,
if spaceLen == fileLen
then spaces'
else Map.insert (spacePos + fileLen) (spaceLen - fileLen) spaces'
)
else
moveFile
(fileId, (filePos + spaceLen, fileLen - spaceLen))
((fileId, (spacePos, spaceLen)) : files, spaces')
Nothing -> (file : files, spaces)
main = do
input <- readInput <$> readFile "input09"
mapM_ (print . checksum . ($ input) . compact) [const $ const True, (<=)]
2 points
It will always be a wonder to me how you manage to do so much in so few lines, even your naive solution only takes a few seconds to run. 🤯
1 point
Aww, thank you <3
It’s just practice, I guess? (The maths degree probably doesn’t hurt either)
2 points
