From 0cb8ce8d9c118041a6095764fe2672b2f67879ba Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 16 Dec 2019 17:26:20 +0000 Subject: [PATCH] Renamed rule to reaction --- advent14/src/advent14.hs | 81 +++++++-------- problems/day14.html | 209 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 247 insertions(+), 43 deletions(-) create mode 100644 problems/day14.html diff --git a/advent14/src/advent14.hs b/advent14/src/advent14.hs index 1fafe9b..4e35ee2 100644 --- a/advent14/src/advent14.hs +++ b/advent14/src/advent14.hs @@ -17,75 +17,66 @@ import qualified Data.Set as S data Reagent = Reagent { _quantity :: Int, _chemical :: String } deriving (Ord, Eq, Show) -data Rule = Rule {_lhs :: S.Set Reagent, _rhs :: Reagent} deriving (Eq, Show) +data Reaction = Reaction {_lhs :: S.Set Reagent, _rhs :: Reagent} deriving (Eq, Show) -type RuleBase = M.Map String Rule +type Reactions = M.Map String Reaction type Requirement = M.Map String Int main :: IO () main = do text <- TIO.readFile "data/advent14.txt" - -- let rules = successfulParse text - -- let ruleBase = mkRuleBase rules - let ruleBase = successfulParse text - -- print rules - -- print ruleBase - print $ part1 ruleBase - print $ part2 ruleBase + let reactions = successfulParse text + print $ part1 reactions + print $ part2 reactions oreLimit :: Int oreLimit = 10^12 -mkRuleBase :: [Rule] -> RuleBase -mkRuleBase = foldl' addRule M.empty - where addRule base rule = M.insert (_chemical $ _rhs rule) rule base - - --- part1 rules = required!"ORE" +-- part1 reactions = required!"ORE" -- where required0 = M.singleton "FUEL" 1 --- required = produce rules required -part1 rules = oreForFuel rules 1 +-- required = produce reactions required +part1 reactions = oreForFuel reactions 1 -part2 rules = searchFuel rules (upper `div` 2) upper - where upper = findUpper rules (oreLimit `div` base) - base = oreForFuel rules 1 +part2 reactions = searchFuel reactions (upper `div` 2) upper + where upper = findUpper reactions (oreLimit `div` base) + base = oreForFuel reactions 1 -oreForFuel :: RuleBase -> Int -> Int -oreForFuel rules n = required!"ORE" +oreForFuel :: Reactions -> Int -> Int +oreForFuel reactions n = required!"ORE" where required0 = M.singleton "FUEL" n - required = produce rules required0 + required = produce reactions required0 -findUpper :: RuleBase -> Int -> Int +findUpper :: Reactions -> Int -> Int -- findUpper _ n | trace ("Upper " ++ show n) False = undefined -findUpper rules n = if ore > oreLimit +findUpper reactions n = if ore > oreLimit then n - else findUpper rules (n * 2) - where ore = oreForFuel rules n + else findUpper reactions (n * 2) + where ore = oreForFuel reactions n -searchFuel :: RuleBase -> Int -> Int -> Int +searchFuel :: Reactions -> Int -> Int -> Int -- searchFuel _ lower upper | trace ("Search " ++ show lower ++ " - " ++ show upper) False = undefined -searchFuel rules lower upper +searchFuel reactions lower upper | upper == lower = upper | otherwise = if ore > oreLimit - then searchFuel rules lower (mid - 1) - else searchFuel rules mid upper + then searchFuel reactions lower (mid - 1) + else searchFuel reactions mid upper where mid = (upper + lower + 1) `div` 2 - ore = oreForFuel rules mid + ore = oreForFuel reactions mid -produce :: RuleBase -> Requirement -> Requirement -produce rules required +produce :: Reactions -> Requirement -> Requirement +produce reactions required | M.null outstanding = required - | otherwise = produce rules required'' + | otherwise = produce reactions required'' where outstanding = M.filter (> 0) $ nonOre required (chem, qty) = M.findMin outstanding - rule = rules!chem - productQty = _quantity $ _rhs rule + reaction = reactions!chem + productQty = _quantity $ _rhs reaction applications = max 1 (qty `div` productQty) qty' = qty - (applications * productQty) required' = M.insert chem qty' required - required'' = S.foldl (addRequrirement applications) required' (_lhs rule) + required'' = S.foldl (addRequrirement applications) required' (_lhs reaction) nonOre :: Requirement -> Requirement @@ -114,16 +105,20 @@ arrowP = symb "=>" commaP = symb "," identifierP = some alphaNumChar <* sc -rulesP = mkRuleBase <$> many ruleP +reactionsP = mkReactions <$> many reactionP -ruleP = Rule <$> reagentsP <* arrowP <*> reagentP +reactionP = Reaction <$> reagentsP <* arrowP <*> reagentP reagentP = Reagent <$> integer <*> identifierP reagentsP = S.fromList <$> reagentP `sepBy` commaP +mkReactions :: [Reaction] -> Reactions +mkReactions = foldl' addReaction M.empty + where addReaction base reaction = M.insert (_chemical $ _rhs reaction) reaction base + -- successfulParse :: Text -> [Vec] -successfulParse :: Text -> RuleBase +successfulParse :: Text -> Reactions successfulParse input = - case parse rulesP "input" input of + case parse reactionsP "input" input of Left _err -> M.empty -- TIO.putStr $ T.pack $ parseErrorPretty err - Right rules -> rules + Right reactions -> reactions diff --git a/problems/day14.html b/problems/day14.html new file mode 100644 index 0000000..3c6f506 --- /dev/null +++ b/problems/day14.html @@ -0,0 +1,209 @@ + + + + +Day 14 - Advent of Code 2019 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 28*

      /^2019$/

+ + + +
+ +

--- Day 14: Space Stoichiometry ---

As you approach the rings of Saturn, your ship's low fuel indicator turns on. There isn't any fuel here, but the rings have plenty of raw material. Perhaps your ship's Inter-Stellar Refinery Union brand nanofactory can turn these raw materials into fuel.

+

You ask the nanofactory to produce a list of the reactions it can perform that are relevant to this process (your puzzle input). Every reaction turns some quantities of specific input chemicals into some quantity of an output chemical. Almost every chemical is produced by exactly one reaction; the only exception, ORE, is the raw material input to the entire process and is not produced by a reaction.

+

You just need to know how much ORE you'll need to collect before you can produce one unit of FUEL.

+

Each reaction gives specific quantities for its inputs and output; reactions cannot be partially run, so only whole integer multiples of these quantities can be used. (It's okay to have leftover chemicals when you're done, though.) For example, the reaction 1 A, 2 B, 3 C => 2 D means that exactly 2 units of chemical D can be produced by consuming exactly 1 A, 2 B and 3 C. You can run the full reaction as many times as necessary; for example, you could produce 10 D by consuming 5 A, 10 B, and 15 C.

+

Suppose your nanofactory produces the following list of reactions:

+
10 ORE => 10 A
+1 ORE => 1 B
+7 A, 1 B => 1 C
+7 A, 1 C => 1 D
+7 A, 1 D => 1 E
+7 A, 1 E => 1 FUEL
+
+

The first two reactions use only ORE as inputs; they indicate that you can produce as much of chemical A as you want (in increments of 10 units, each 10 costing 10 ORE) and as much of chemical B as you want (each costing 1 ORE). To produce 1 FUEL, a total of 31 ORE is required: 1 ORE to produce 1 B, then 30 more ORE to produce the 7 + 7 + 7 + 7 = 28 A (with 2 extra A wasted) required in the reactions to convert the B into C, C into D, D into E, and finally E into FUEL. (30 A is produced because its reaction requires that it is created in increments of 10.)

+

Or, suppose you have the following list of reactions:

+
9 ORE => 2 A
+8 ORE => 3 B
+7 ORE => 5 C
+3 A, 4 B => 1 AB
+5 B, 7 C => 1 BC
+4 C, 1 A => 1 CA
+2 AB, 3 BC, 4 CA => 1 FUEL
+
+

The above list of reactions requires 165 ORE to produce 1 FUEL:

+
    +
  • Consume 45 ORE to produce 10 A.
    • +
  • Consume 64 ORE to produce 24 B.
    • +
  • Consume 56 ORE to produce 40 C.
    • +
  • Consume 6 A, 8 B to produce 2 AB.
    • +
  • Consume 15 B, 21 C to produce 3 BC.
    • +
  • Consume 16 C, 4 A to produce 4 CA.
    • +
  • Consume 2 AB, 3 BC, 4 CA to produce 1 FUEL.
    • +
+

Here are some larger examples:

+
    +

  • 13312 ORE for 1 FUEL:

    +
    157 ORE => 5 NZVS
+165 ORE => 6 DCFZ
+44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL
+12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ
+179 ORE => 7 PSHF
+177 ORE => 5 HKGWZ
+7 DCFZ, 7 PSHF => 2 XJWVT
+165 ORE => 2 GPVTF
+3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT
+
    • +

  • 180697 ORE for 1 FUEL:

    +
    2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG
+17 NVRVD, 3 JNWZP => 8 VPVL
+53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL
+22 VJHF, 37 MNCFX => 5 FWMGM
+139 ORE => 4 NVRVD
+144 ORE => 7 JNWZP
+5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC
+5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV
+145 ORE => 6 MNCFX
+1 NVRVD => 8 CXFTF
+1 VJHF, 6 MNCFX => 4 RFSQX
+176 ORE => 6 VJHF
+
    • +

  • 2210736 ORE for 1 FUEL:

    +
    171 ORE => 8 CNZTR
+7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL
+114 ORE => 4 BHXH
+14 VRPVC => 6 BMBT
+6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL
+6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT
+15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW
+13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW
+5 BMBT => 4 WPTQ
+189 ORE => 9 KTJDG
+1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP
+12 VRPVC, 27 CNZTR => 2 XDBXC
+15 KTJDG, 12 BHXH => 5 XCVML
+3 BHXH, 2 VRPVC => 7 MZWV
+121 ORE => 7 VRPVC
+7 XCVML => 6 RJRHP
+5 BHXH, 4 VRPVC => 5 LTCX
+
    • +
+

Given the list of reactions in your puzzle input, what is the minimum amount of ORE required to produce exactly 1 FUEL?

+
+

Your puzzle answer was 598038.

--- Part Two ---

After collecting ORE for a while, you check your cargo hold: 1 trillion (1000000000000) units of ORE.

+

With that much ore, given the examples above:

+
    +
  • The 13312 ORE-per-FUEL example could produce 82892753 FUEL.
    • +
  • The 180697 ORE-per-FUEL example could produce 5586022 FUEL.
    • +
  • The 2210736 ORE-per-FUEL example could produce 460664 FUEL.
    • +
+

Given 1 trillion ORE, what is the maximum amount of FUEL you can produce?

+
+

Your puzzle answer was 2269325.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your Advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file -- 2.34.1