From 2b1e7210176d1b2a94bb09f516d5506ba1d82a51 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sat, 14 Dec 2019 10:26:10 +0100
Subject: Day 14

---
 2019/14.hs | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
 create mode 100644 2019/14.hs

(limited to '2019/14.hs')

diff --git a/2019/14.hs b/2019/14.hs
new file mode 100644
index 0000000..b20ac93
--- /dev/null
+++ b/2019/14.hs
@@ -0,0 +1,55 @@
+module Main where
+
+import qualified Data.Map.Strict as Map
+import qualified Data.Map.Lazy as LMap
+import Data.Maybe
+import qualified Data.Set as Set
+import Text.Parsec (runParser, sepBy1, string, many1, space, letter, string, digit)
+
+import Input
+
+
+type Comp = String
+data Rule = Rule [(Int, Comp)] (Int, Comp)
+  deriving (Show)
+
+parseRule :: String -> Rule
+parseRule = either (error . show) id . runParser pRule () ""
+  where
+    pRule = Rule <$> (pPair `sepBy1` pComma) <*> (string " => " >> pPair)
+    pPair = (,) <$> (read <$> many1 digit) <*> (space >> many1 letter)
+    pComma = string ", "
+
+ceilDiv :: Integral i => i -> i -> i
+ceilDiv a b = (a + b - 1) `div` b
+
+binaryMax :: Integral i => i -> i -> (i -> Bool) -> Maybe i
+binaryMax low high f
+    | low < high = let mid = low + (high - low) `div` 2
+                       res = f mid
+                   in if res then binaryMax mid high f else binaryMax low (mid - 1) f
+    | low == high, f low = Just low
+    | otherwise = Nothing
+
+main :: IO ()
+main = do
+    rules <- map parseRule <$> getInput 14
+
+    let compounds = Set.toList $ Set.fromList [c | Rule src (_, to) <- rules, c <- to : map snd src]
+        supportGraph = Map.fromListWith (++)
+                           [(srccomp, [(num, ncomp, comp)])  -- need 'num' of 'srccomp' for 'ncomp' of 'comp'
+                           | Rule src (ncomp, comp) <- rules
+                           , (num, srccomp) <- src]
+
+    let buildNeedOf nfuel =
+            let computeNeed "FUEL" = nfuel
+                computeNeed comp =
+                    sum [nreqcomp * ((needOf Map.! c2) `ceilDiv` nprodc2)
+                        | (nreqcomp, nprodc2, c2) <- fromMaybe [] (Map.lookup comp supportGraph)]
+                needOf = LMap.fromList [(comp, computeNeed comp) | comp <- compounds]
+            in needOf
+
+    print (buildNeedOf 1 Map.! "ORE")
+
+    let lim = 1000000000000
+    print (fromJust (binaryMax 0 lim (\m -> buildNeedOf m Map.! "ORE" <= lim)))
-- 
cgit v1.2.3-70-g09d2