aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--aoc.cabal6
-rw-r--r--execs/Day13.hs25
-rw-r--r--input/132
-rw-r--r--lib/Utils.hs27
4 files changed, 60 insertions, 0 deletions
diff --git a/aoc.cabal b/aoc.cabal
index dfd102e..87867f4 100644
--- a/aoc.cabal
+++ b/aoc.cabal
@@ -93,3 +93,9 @@ executable Day12
93 build-depends: base, aoc, containers 93 build-depends: base, aoc, containers
94 default-language: Haskell2010 94 default-language: Haskell2010
95 hs-source-dirs: execs 95 hs-source-dirs: execs
96
97executable Day13
98 main-is: Day13.hs
99 build-depends: base, aoc, containers, split
100 default-language: Haskell2010
101 hs-source-dirs: execs
diff --git a/execs/Day13.hs b/execs/Day13.hs
new file mode 100644
index 0000000..07d379d
--- /dev/null
+++ b/execs/Day13.hs
@@ -0,0 +1,25 @@
1module Main where
2
3import Utils
4import Data.List.Split
5import Data.Tuple
6import Data.List (sortOn)
7import Data.Bifunctor
8import Control.Monad (zipWithM, ap)
9
10earliest :: Int -> [Int] -> Int
11earliest start ls = t * b
12 where (t, b) = minimum $ map swap $ zip `ap` map (mod start) $ ls
13
14gold :: [(Int, Int)] -> Int
15gold ls = t
16 where Just t = chineseRemainder ls
17
18main :: IO ()
19main = do
20 n <- lines <$> readFile "input/13"
21 let start = read (head n) :: Int
22 departs = map read $ filter (/= "x") $ splitOn "," (last n)
23 offs = map (bimap negate read) $ filter ((/= "x") . snd) $ zip [0..] $ splitOn "," (last n)
24 print $ earliest (negate start) departs
25 print $ gold offs
diff --git a/input/13 b/input/13
new file mode 100644
index 0000000..dec83ff
--- /dev/null
+++ b/input/13
@@ -0,0 +1,2 @@
11000053
219,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,523,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,x,23,x,x,x,x,x,29,x,547,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,17
diff --git a/lib/Utils.hs b/lib/Utils.hs
index 56d9c69..e0f9d62 100644
--- a/lib/Utils.hs
+++ b/lib/Utils.hs
@@ -65,3 +65,30 @@ makeGrid s = (grid, width, height) where
65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row] 65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row]
66 width = length (head rows) 66 width = length (head rows)
67 height = length rows 67 height = length rows
68
69-- number theory
70
71egcd :: Int -> Int -> (Int, Int)
72egcd _ 0 = (1, 0)
73egcd a b = (t, s - q * t)
74 where
75 (s, t) = egcd b r
76 (q, r) = a `quotRem` b
77
78modInv :: Int -> Int -> Maybe Int
79modInv a b =
80 case egcd a b of
81 (x, y)
82 | a * x + b * y == 1 -> Just x
83 | otherwise -> Nothing
84
85-- from rosetta code
86chineseRemainder :: [(Int, Int)] -> Maybe Int
87chineseRemainder ls =
88 zipWithM modInv crtModulii modulii >>=
89 (Just . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues)
90 where
91 residues = map fst ls
92 modulii = map snd ls
93 modPI = product modulii
94 crtModulii = (modPI `div`) <$> modulii