Day 14

2 files changed, 115 insertions, 0 deletions

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)))
diff --git a/2019/14.in b/2019/14.in
new file mode 100644
index 0000000..6ff4298
--- /dev/null
+++ b/2019/14.in
@@ -0,0 +1,60 @@
+1 FVBHS, 29 HWPND => 4 CPXDX
+5 TNWDG, 69 VZMS, 1 GXSD, 48 NCLZ, 3 RSRZ, 15 HWPND, 25 SGPK, 2 SVCQ => 1 FUEL
+1 PQRLB, 1 TWPMQ => 4 QBXC
+9 QBXC => 7 RNHQ
+12 VZMS => 6 MGQRZ
+6 QBVG, 10 XJWX => 6 BWLZ
+4 MVGN => 6 BHZH
+2 LKTWD => 7 FVBHS
+2 BWFK => 7 TFPQ
+15 VZBJ, 9 TSVN, 2 BWLZ => 2 TNWDG
+10 KVFL, 2 BWLZ, 1 VGSBF => 4 KBFJV
+12 TXCR, 2 JMBG => 4 DCFD
+5 VMDT, 6 JKPFT, 3 RJKJD => 7 LGWM
+1 LDFGW => 2 DHRBP
+129 ORE => 8 LDFGW
+9 DNVRJ => 8 BMNGX
+7 NLPB => 6 NCLZ
+1 VMDT, 6 DCFD => 9 SGRXC
+1 LDFGW, 2 VRHFB => 8 QHGQC
+10 VGSBF, 5 WVMG, 6 BWLZ => 3 BWFK
+4 KVFL, 1 TSVN => 6 SVCQ
+2 VZBJ, 3 SWJZ => 3 QZLC
+5 JMBG, 1 PQRLB => 3 CJLH
+13 LKTWD, 6 TFPQ => 3 WVRXR
+20 QHGQC, 10 NSPVD => 5 VGSBF
+5 TFPQ, 1 DHRBP, 2 KVFL => 8 NLPB
+2 KBFJV, 1 CJLH, 20 RNHQ, 1 BWLZ, 13 MNBK, 1 BHZH, 1 PKRJF => 8 RSRZ
+154 ORE => 2 VRHFB
+2 NHRCK => 7 DNVRJ
+2 VRHFB, 4 XJWX => 4 NHRCK
+1 TFPQ, 12 JMBG => 5 MNBK
+8 TMFS => 2 VZMS
+175 ORE => 2 TMFS
+1 LBZN, 2 SWJZ, 3 VGSBF => 8 BLDN
+7 KFJD, 5 WVRXR, 5 RJKJD => 6 MVGN
+3 RJKJD, 1 TXCR => 8 KVFL
+3 QHGQC, 1 MGQRZ, 10 VGSBF => 8 LKTWD
+178 ORE => 1 XJWX
+1 QBXC, 1 BWFK => 6 TSVN
+1 NHRCK, 2 DHRBP => 4 VZBJ
+1 LDFGW, 2 NHRCK, 10 BWLZ => 8 TWPMQ
+28 TWPMQ => 4 RJKJD
+10 SVCQ, 1 KVFL => 6 CZNMG
+3 VZMS, 3 MGQRZ => 3 WVMG
+19 MGQRZ => 8 KFJD
+3 WVMG => 6 PQRLB
+31 SVCQ, 1 TXCR => 8 VMDT
+20 KFJD, 5 CPXDX, 2 BLDN, 2 PQWJX, 12 TFPQ, 2 BHZH, 2 MVGN => 9 SGPK
+7 QZLC => 8 JMBG
+1 PQRLB => 1 HWPND
+9 VMDT, 5 CZNMG, 3 CPXDX, 1 MVGN, 8 VSMTK, 2 SGRXC, 1 MNBK, 8 LGWM => 7 GXSD
+2 NSPVD => 8 QBVG
+20 CZNMG => 4 PQWJX
+1 LDFGW => 4 NSPVD
+16 KBFJV, 22 BLDN => 2 VSMTK
+10 BWLZ => 9 LBZN
+1 BWLZ => 3 SWJZ
+1 HWPND => 9 TXCR
+12 CJLH, 9 LGWM, 3 BHZH => 6 PKRJF
+5 BMNGX => 7 JKPFT