aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2023/11-Cosmic_Expansion/example10
-rw-r--r--2023/11-Cosmic_Expansion/first.hs74
-rw-r--r--2023/11-Cosmic_Expansion/input140
-rw-r--r--2023/11-Cosmic_Expansion/second.hs71
4 files changed, 295 insertions, 0 deletions
diff --git a/2023/11-Cosmic_Expansion/example b/2023/11-Cosmic_Expansion/example
new file mode 100644
index 0000000..986aad4
--- /dev/null
+++ b/2023/11-Cosmic_Expansion/example
@@ -0,0 +1,10 @@
+...#......
+.......#..
+#.........
+..........
+......#...
+.#........
+.........#
+..........
+.......#..
+#...#.....
diff --git a/2023/11-Cosmic_Expansion/first.hs b/2023/11-Cosmic_Expansion/first.hs
new file mode 100644
index 0000000..cef9e77
--- /dev/null
+++ b/2023/11-Cosmic_Expansion/first.hs
@@ -0,0 +1,74 @@
+-- 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 + S.size (S.filter (< x) emptyCols)
+ y' = y + 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
+ example <- parseInput "example"
+ let exampleOutput = compute example
+ when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+ input <- parseInput "input"
+ print $ compute input
diff --git a/2023/11-Cosmic_Expansion/input b/2023/11-Cosmic_Expansion/input
new file mode 100644
index 0000000..0723e73
--- /dev/null
+++ b/2023/11-Cosmic_Expansion/input
@@ -0,0 +1,140 @@
+.......#.....#.....................#.............#.................#.........................#..............................................
+#.....................#.......#.................................................................................#.......#...................
+.......................................................................#.........................#..................................#.......
+................................................................#..............#..............................................#.............
+.........................................#............................................................#....................................#
+.................#..................................................#.......................................................................
+...........................#...............................................................................#................................
+....#.......#...........................................#..........................#.............................#..........................
+....................#.............#........#................................................................................................
+...................................................#...................................................#...................#................
+.........................#........................................#..................................................#......................
+......#..........#...........................................#...........#............#.....................................................
+......................................#..........................................#.........................#.....................#..........
+.#...................#..................................#.......................................#...........................................
+............#.................................#.....................#.......................................................................
+............................................................................................................................................
+..............................#.....................................................................................#..................#....
+....................................................................................#........#......#.......................................
+.........................#.........................#............#...........................................#...............................
+.#......#.....#.......................#.................#........................................................#.....#....................
+...........................................................................#.................................................#..............
+...............................................#.......................................#...............#..........................#.........
+......................#..................#..................................................................................................
+..........................................................................................................................#.................
+......#...........................#.........................................................#........................#......................
+..............................................................................................................................#.............
+..#.......................#.................#............................................................................................#..
+..................#....................................................#................#...................................................
+....................................................#.....#....................#............................................................
+...............................#............................................................................................................
+..............................................#...............#..........................................................#...........#......
+.#.........#........................#..................................................................#....................................
+..........................................................................#.......................#........................................#
+...................#......................................................................#.................................................
+.............................................................................................................................#..............
+.....#......................................................................................................................................
+........................................................#........................#..........................................................
+.............................#...............#.....................#.....#............#..................#..............................#...
+............................................................................................#......#...........#............................
+.........................#........#...................................................................................#.....................
+...........................................................................................................................................#
+.....................................................#.....#.................................................................#..............
+#.........................................................................................................#.......................#.........
+................#...........................................................#.....................#.........................................
+..............................#..............#...................................#.......#...........................#......................
+........#................#.........#............................#............................................#.............#.........#......
+............................................................................................................................................
+.......................................................#...............#.............................#...........................#..........
+.............#.................................#............................................................................................
+............................................................................................................................................
+..#.............................................................................#...........................................#...........#...
+............................................................................................................................................
+......................................#..........................................................#................#.........................
+............................#................#......#......................#...........#....................................................
+............................................................................................................................................
+....................................................................................................#................#..........#...........
+.#............#...................#...............................#........................................#.............................#..
+.........#...............................................................#..................................................................
+.......................#....................#........#...........................................#..........................................
+............................................................#.....................................................#.........................
+..............................#.......................................................................#...................#.......#.........
+............#.......................#...................#............................#......................................................
+...................................................#......................................#..............................................#..
+.#................#...................................................#........................#............................................
+......#....................................................................#................................#...............................
+...............................#....................................................................................#.......................
+.........................#.....................#......#.............................................#.................................#.....
+............................................................................................................................................
+...............#.....................#....................................................#.................................................
+..................................................................................................................#.........................
+....#......#.....................................#..............................#............................#............#.....#...........
+....................#.............................................#....................#.........#.......................................#..
+.........................................................#..............#.............................#.....................................
+............................#...........#...........................................................................#.......................
+............................................................................................................................................
+#..................................#...............................................................#..........#.............................
+.......#......................................................................................#.................................#.......#...
+.....................#....................#...............................#.....#......................................#....................
+................................#..........................#......#....................#..........................#.........................
+..............#...................................#........................................................................#...............#
+....#....................................................................................................#..................................
+.......................#....................................................................................................................
+......................................#................................#..................#.................................................
+.....................................................#............................................#...............................#.........
+............................................................................................................................................
+............................................................................................................................................
+....#.................#..................................#.........................#..........................#.............................
+.............#........................................................................................#..................#..................
+......................................#............................................................................#........................
+.........#....................................................#.........#............................................................#......
+.............................................................................................#..............................................
+.............................#...........#............................................................................#.....................
+#..................#................................................#....................#.......................................#.........#
+...................................................................................................#......#.................................
+...........#.............................................#...........................#......................................................
+....................................#.......................................................................................................
+..................................................#..........#.........#......................#.....................#.......................
+.#......#....................................#..............................................................#...............................
+.............................#.............................................#................................................................
+.......................#...............................................................................#....................#...............
+....................................................#.....................................#...........................................#.....
+................#.....................#..................#.................................................................................#
+...#.....#..........................................................#................#......................................................
+.............................................#...............#................................#......#......................................
+...............................#...............................................#............................................................
+.............................................................................................................................#.........#....
+.....................#................................................#.................................................#...................
+...............#.........................#.......................#..................#.......................................................
+.....#......................................................................................................#.......................#.......
+....................................#.................#.........................#..................#........................................
+........................................................................................................................................#...
+.........#..............#.....................................#........................................#.....................#..............
+...............................................#...................#........................................................................
+......................................#.............#..................................#.....#.......................#......................
+............#.....#...............................................................................#.........................................
+...#...................................................................................................................................#....
+.......................#.........................#..........................................................................................
+.........................................................#...........#.........................#........#..........#.............#..........
+............................#..............#....................#........................................................#..................
+.......#.................................................................#................#.................................................
+.................#..................................................................................#........................#...........#..
+...................................................#.......#................................................................................
+.........................................#......................................#......................................#....................
+....................................#...........................................................................#...........................
+..............................#.............................................................#...........#.......................#......#....
+.........#...............................................#..............#...................................................................
+........................#....................#.....................................#........................................................
+#...........................................................................................................................................
+............................#......................................................................#.......#................................
+......................................#.....................................................................................................
+.....#............#.........................................#..........................#..........................................#.........
+...........................................#......................#..............................................#..........................
+..............#..............................................................................#............................#.............#...
+..#......#...........................................#..............................#..................#.....#..............................
+....................#..........#.....#...............................#......................................................................
+............................................................................................................................................
+.................................................#..........................................................................................
+.............#..........#...............................#...............#.............#..........#.........#........#.......................
+............................................#................#.................#............................................................
+....................................#....................................................................................#.............#....
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