day14

2 files changed, 256 insertions, 1 deletions

diff --git a/input14 b/input14
new file mode 100644
index 0000000..c90f858
--- /dev/null
+++ b/input14
@@ -0,0 +1,61 @@
+4 QBQB, 2 NTLZ => 2 DPJP
+5 SCSDX, 3 WBLBS => 5 GVPG
+128 ORE => 1 WCQS
+14 LHMZ => 2 SWBFV
+5 NZJV, 1 MCLXC => 2 BSRT
+1 WJHZ => 6 HRZV
+5 SPNML, 1 QTVZL => 6 HBGD
+1 BSRT, 1 JRBM, 1 GVPG => 2 XVDQT
+10 CBQSB => 6 NRXGX
+6 TBFQ => 7 QPXS
+1 LKSVN => 1 FBFC
+39 CBQSB => 7 PSLXZ
+3 HBGD, 4 RCZF => 4 ZCTS
+2 BMDV, 6 DPJP => 1 RCZF
+1 GPBXP, 11 SWBFV, 12 XSBGR, 7 ZCLVG, 9 VQLN, 12 HRZV, 3 VLDVB, 3 QTVZL, 12 DVSD, 62 PSLXZ => 1 FUEL
+10 CFPG, 1 TBFQ => 3 NHKZB
+24 QLMJ => 1 SCSDX
+2 VKHZC => 1 SMLPV
+3 SMLPV, 11 NZJV, 1 HTSXK => 2 GPBXP
+1 SCKB => 3 TBFQ
+3 VKHZC, 2 XVDQT => 6 PHJH
+3 QBQB => 3 XHWH
+19 NHKZB, 3 MBQVK, 10 HTSXK, 2 GXVQG, 8 VKHZC, 1 XHWH, 1 RCZF => 5 ZCLVG
+1 GVPG => 4 QTVZL
+4 TMHMV => 7 LHMZ
+5 NRXGX, 9 NTLZ, 3 PSLXZ => 1 BMDV
+10 MCLXC => 3 VKHZC
+1 KTLR => 1 VLDVB
+5 HTSXK => 6 TMHMV
+5 LKSVN, 1 CGQHF, 11 WJHZ => 1 HGZC
+15 XHWH, 1 WBLBS => 4 NZJV
+3 MCLXC => 9 KTLR
+1 CBQSB => 1 SCKB
+140 ORE => 4 LKSVN
+2 NZJV, 8 XVDQT, 1 PHJH => 8 GXVQG
+21 NJXV, 1 XHWH, 12 TMHMV, 1 QPXS, 10 ZCTS, 3 TBFQ, 1 VLDVB => 7 DVSD
+4 QLMJ, 2 LKSVN => 1 NTLZ
+1 LKSVN => 4 QBQB
+1 SPNML, 3 CPBQ => 4 BKLPC
+2 CFPG => 5 MCLXC
+147 ORE => 7 CGQHF
+7 HGZC, 5 QLMJ => 3 CFPG
+3 LCLQV, 3 MLXGB, 1 NTLZ => 8 JRBM
+4 NHWG => 5 GPQN
+2 XHWH => 7 WBLBS
+7 CGFN, 2 RCZF, 13 NHWG, 1 VLDVB, 3 PHJH, 9 CBQSB => 9 XSBGR
+181 ORE => 7 WJHZ
+8 WJHZ => 9 CBQSB
+3 BTQWK, 8 BKLPC => 2 CGFN
+3 SCSDX => 3 NJXV
+6 JTBM, 23 GPQN => 1 VQLN
+23 MCLXC, 1 NTLZ => 7 SPNML
+1 SPNML => 2 JTBM
+1 BMDV => 7 HTSXK
+1 WBLBS => 9 NHWG
+4 FBFC, 1 LKSVN, 4 VKHZC => 7 CPBQ
+1 WCQS => 7 QLMJ
+1 BMDV, 2 DPJP => 6 MBQVK
+3 XHWH, 5 QLMJ => 4 LCLQV
+1 CBQSB, 2 PSLXZ => 2 MLXGB
+3 NHWG => 9 BTQWK
diff --git a/src/main.rs b/src/main.rs
index 9b7e3f7..a8e6819 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1209,8 +1209,129 @@ fn day13() {
     println!("13b: {}", arcade.score);
 }
 
+struct Reaction {
+    result: String,
+    amount: isize,
+    resources: HashMap<String, isize>,
+}
+
+impl Reaction {
+    fn split_amount_material(input: &str) -> (isize, String) {
+        let splitted: Vec<&str> = input.split(' ').collect();
+        assert_eq!(splitted.len(), 2);
+        (splitted[0].parse::<isize>().unwrap(), splitted[1].to_string())
+    }
+
+    fn parse(input: &str) -> Reaction {
+        let reaction: Vec<&str> = input.split(" => ").collect();
+        let (amount, result) = Reaction::split_amount_material(reaction[1]);
+        let required = reaction[0].split(", ");
+        let mut resources = HashMap::new();
+        for resource in required {
+            let (amount, material) = Reaction::split_amount_material(resource);
+            resources.insert(material, amount);
+        }
+
+        Reaction {
+            result,
+            amount,
+            resources,
+        }
+    }
+}
+
+struct Reactions {
+    reactions: HashMap<String, Reaction>,
+}
+
+impl Reactions {
+    const ORE_LIMIT: isize = 1_000_000_000_000;
+
+    fn parse(input: &str) -> Reactions {
+        let mut reactions = HashMap::new();
+        let input = input.trim_end();
+
+        for line in input.split('\n') {
+            let reaction = Reaction::parse(line);
+            reactions.insert(reaction.result.clone(), reaction);
+        }
+        Reactions { reactions }
+    }
+
+    fn count_material_(&self, amount_requested: isize, output: &str, leftovers: &mut HashMap<String, isize>, total_ore_count: &mut isize) -> Result<isize, ()> {
+        if output == "ORE" {
+            if *total_ore_count + amount_requested > Reactions::ORE_LIMIT {
+                return Err(());
+            }
+            *total_ore_count += amount_requested;
+            return Ok(amount_requested);
+        }
+        let mut amount_requested = amount_requested;
+
+        /* use up leftover materials first */
+        let leftover = *leftovers.entry(output.to_string()).or_insert(0);
+        if leftover >= amount_requested {
+            leftovers.insert(output.to_string(), leftover - amount_requested);
+            /* no additional reaction needed, can satisfy with leftovers */
+            return Ok(0);
+        } else {
+            leftovers.insert(output.to_string(), 0);
+            amount_requested -= leftover;
+        }
+
+        let reaction = self.reactions.get(output).unwrap();
+        let mut factor = amount_requested / reaction.amount;
+        if amount_requested % reaction.amount > 0 {
+            factor += 1;
+        }
+        let produced = factor * reaction.amount;
+        leftovers.insert(output.to_string(), produced - amount_requested);
+
+        let mut ore_count = 0;
+        for resource in reaction.resources.keys() {
+            let amount = *reaction.resources.get(resource).unwrap();
+            ore_count += self.count_material_(amount * factor, &resource, leftovers, total_ore_count)?;
+        }
+
+        Ok(ore_count)
+    }
+
+    fn count_material(&self, amount_requested: isize, output: &str, ) -> isize {
+        let mut ore_count = 0;
+        self.count_material_(amount_requested, output, &mut HashMap::new(), &mut ore_count).unwrap()
+    }
+
+    fn possible_fuel(&self) -> isize {
+        let mut leftovers = HashMap::new();
+        let mut ore_count = 0;
+
+        let mut fuel_count = 1;
+        let ore_per_fuel = self.count_material_(1, "FUEL", &mut leftovers, &mut ore_count).unwrap();
+
+        fuel_count += Reactions::ORE_LIMIT / ore_per_fuel;
+        self.count_material_(Reactions::ORE_LIMIT / ore_per_fuel, "FUEL", &mut leftovers, &mut ore_count).unwrap();
+        loop {
+            match self.count_material_(1, "FUEL", &mut leftovers, &mut ore_count) {
+                Ok(_) => fuel_count += 1,
+                Err(_) => break,
+            };
+        }
+        fuel_count
+    }
+
+}
+
+fn day14() {
+    let input = read_file("input14");
+    let reactions = Reactions::parse(&input);
+
+    println!("14a: {}", reactions.count_material(1, "FUEL"));
+
+    println!("14b: {}", reactions.possible_fuel());
+}
+
 fn main() {
-    day13();
+    day14();
 }
 
 #[cfg(test)]
@@ -1415,4 +1536,77 @@ mod tests {
 
         assert_eq!(asteroid_map.vaporized(max.0, 200), Point { x: 8, y: 2 });
     }
+
+    #[test]
+    fn test_day14() {
+        let input = "10 ORE => 10 A\n\
+                     1 ORE => 1 B\n\
+                     7 A, 1 B => 1 C\n\
+                     7 A, 1 C => 1 D\n\
+                     7 A, 1 D => 1 E\n\
+                     7 A, 1 E => 1 FUEL";
+        let reactions = Reactions::parse(input);
+        assert_eq!(reactions.count_material(1, "FUEL"), 31);
+
+        let input = "9 ORE => 2 A\n\
+                     8 ORE => 3 B\n\
+                     7 ORE => 5 C\n\
+                     3 A, 4 B => 1 AB\n\
+                     5 B, 7 C => 1 BC\n\
+                     4 C, 1 A => 1 CA\n\
+                     2 AB, 3 BC, 4 CA => 1 FUEL";
+        let reactions = Reactions::parse(input);
+        assert_eq!(reactions.count_material(1, "FUEL"), 165);
+
+
+        let input = "157 ORE => 5 NZVS\n\
+                     165 ORE => 6 DCFZ\n\
+                     44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL\n\
+                     12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ\n\
+                     179 ORE => 7 PSHF\n\
+                     177 ORE => 5 HKGWZ\n\
+                     7 DCFZ, 7 PSHF => 2 XJWVT\n\
+                     165 ORE => 2 GPVTF\n\
+                     3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT";
+        let reactions = Reactions::parse(input);
+        assert_eq!(reactions.count_material(1, "FUEL"), 13312);
+        //assert_eq!(reactions.possible_fuel(), 82892753);
+
+        let input = "2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG\n\
+                     17 NVRVD, 3 JNWZP => 8 VPVL\n\
+                     53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL\n\
+                     22 VJHF, 37 MNCFX => 5 FWMGM\n\
+                     139 ORE => 4 NVRVD\n\
+                     144 ORE => 7 JNWZP\n\
+                     5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC\n\
+                     5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV\n\
+                     145 ORE => 6 MNCFX\n\
+                     1 NVRVD => 8 CXFTF\n\
+                     1 VJHF, 6 MNCFX => 4 RFSQX\n\
+                     176 ORE => 6 VJHF";
+        let reactions = Reactions::parse(input);
+        assert_eq!(reactions.count_material(1, "FUEL"), 180697);
+        //assert_eq!(reactions.possible_fuel(), 5586022);
+
+        let input = "171 ORE => 8 CNZTR\n\
+                     7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL\n\
+                     114 ORE => 4 BHXH\n\
+                     14 VRPVC => 6 BMBT\n\
+                     6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL\n\
+                     6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT\n\
+                     15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW\n\
+                     13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW\n\
+                     5 BMBT => 4 WPTQ\n\
+                     189 ORE => 9 KTJDG\n\
+                     1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP\n\
+                     12 VRPVC, 27 CNZTR => 2 XDBXC\n\
+                     15 KTJDG, 12 BHXH => 5 XCVML\n\
+                     3 BHXH, 2 VRPVC => 7 MZWV\n\
+                     121 ORE => 7 VRPVC\n\
+                     7 XCVML => 6 RJRHP\n\
+                     5 BHXH, 4 VRPVC => 5 LTCX";
+        let reactions = Reactions::parse(input);
+        assert_eq!(reactions.count_material(1, "FUEL"), 2210736);
+        //assert_eq!(reactions.possible_fuel(), 460664);
+    }
 }