diff options
author | Julien Dessaux | 2023-12-11 23:45:09 +0100 |
---|---|---|
committer | Julien Dessaux | 2023-12-11 23:45:09 +0100 |
commit | e89d52558991ff10a076a5b14856aad98daaa53f (patch) | |
tree | c2a341414b4ab9010dc2ad77c13cbf5d86a86d49 /2023/11-Cosmic_Expansion/second.hs | |
parent | 2023-10 in haskell (diff) | |
download | advent-of-code-e89d52558991ff10a076a5b14856aad98daaa53f.tar.gz advent-of-code-e89d52558991ff10a076a5b14856aad98daaa53f.tar.bz2 advent-of-code-e89d52558991ff10a076a5b14856aad98daaa53f.zip |
2023-11 in haskell
Diffstat (limited to '')
-rw-r--r-- | 2023/11-Cosmic_Expansion/second.hs | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/2023/11-Cosmic_Expansion/second.hs b/2023/11-Cosmic_Expansion/second.hs new file mode 100644 index 0000000..14ed19d --- /dev/null +++ b/2023/11-Cosmic_Expansion/second.hs @@ -0,0 +1,71 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Vector qualified as V +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 374 + +type Position = (Int, Int) +type Input = [Position] + +type Parser = Parsec Void String + +parseLine :: Parser Position +parseLine = do + (SourcePos _ y x) <- getSourcePos + void $ char '#' <* some (void (char '.') <|> void eol) + return (unPos x, unPos y) + +parseInput' :: Parser Input +parseInput' = do + some (void (char '.') <|> void eol) + some parseLine <* eof + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute input = distances $ map expand input + where + distances :: Input -> Int + distances [] = 0 + distances (x:xs) = distances' x xs + distances xs + distances' :: Position -> Input -> Int + distances' a [] = 0 + distances' a (x:xs) = distance a x + distances' a xs + distance :: Position -> Position -> Int + distance (x1, y1) (x2, y2) = abs (x2-x1) + abs (y2-y1) + expand :: Position -> Position + expand (x, y) = (x', y') + where + x' = x + 999999 * S.size (S.filter (< x) emptyCols) + y' = y + 999999 * S.size (S.filter (< y) emptyRows) + cols = S.fromList $ map fst input + rows = S.fromList $ map snd input + allCols = S.fromList [0..S.findMax cols] + allRows = S.fromList [0..S.findMax rows] + emptyCols = allCols S.\\ cols + emptyRows = allRows S.\\ rows + +main :: IO () +main = do + input <- parseInput "input" + print $ compute input |