Day 14, refueling

2 files changed, 280 insertions, 0 deletions

diff --git a/inputs/day_14.txt b/inputs/day_14.txt
new file mode 100644
index 0000000..dac9757
--- /dev/null
+++ b/inputs/day_14.txt
@@ -0,0 +1,59 @@
+2 RWPCH => 9 PVTL
+1 FHFH => 4 BLPJK
+146 ORE => 5 VJNBT
+8 KDFNZ, 1 ZJGH, 1 GSCG => 5 LKPQG
+11 NWDZ, 2 WBQR, 1 VRQR => 2 BMJR
+3 GSCG => 4 KQDVM
+5 QVNKN, 6 RPWKC => 3 BCNV
+10 QMBM, 4 RBXB, 2 VRQR => 1 JHXBM
+15 RPWKC => 6 MGCQ
+1 QWKRZ => 4 FHFH
+10 RWPCH => 6 MZKG
+11 JFKGV, 5 QVNKN, 1 CTVK => 4 VQDT
+1 SXKT => 5 RPWKC
+1 VQDT, 25 ZVMCB => 2 RBXB
+6 LGLNV, 4 XSNKB => 3 WBQR
+199 ORE => 2 SXKT
+1 XSNKB, 6 CWBNX, 1 HPKB, 5 PVTL, 1 JNKH, 9 SXKT, 3 KQDVM => 3 ZKTX
+7 FDSX => 6 WJDF
+7 JLRM => 4 CWBNX
+167 ORE => 5 PQZXH
+13 JHXBM, 2 NWDZ, 4 RFLX, 12 VRQR, 10 FJRFG, 14 PVTL, 2 JLRM => 6 DGFG
+12 HPKB, 3 WHVXC => 9 ZJGH
+1 JLRM, 2 ZJGH, 2 QVNKN => 9 FJRFG
+129 ORE => 7 KZFPJ
+2 QMBM => 1 RWPCH
+7 VJMWM => 4 JHDW
+7 PQZXH, 7 SXKT => 9 BJVQM
+1 VJMWM, 4 JHDW, 1 MQXF => 7 FDSX
+1 RPWKC => 7 WHVXC
+1 ZJGH => 1 ZVMCB
+1 RWPCH => 3 MPKR
+187 ORE => 8 VJMWM
+15 CTVK => 5 GSCG
+2 XSNKB, 15 ZVMCB, 3 KDFNZ => 2 RFLX
+18 QVNKN => 8 XLFZJ
+4 CWBNX => 8 ZSCX
+2 ZJGH, 1 JLRM, 1 MGCQ => 9 NPRST
+13 BJVQM, 2 BCNV => 2 QWKRZ
+2 QWKRZ, 2 BLPJK, 5 XSNKB => 2 VRQR
+13 HPKB, 3 VQDT => 9 JLRM
+2 SXKT, 1 VJNBT, 5 VLWQB => 6 CTVK
+2 MPKR, 2 LMNCH, 24 VRQR => 8 DZFNW
+2 VQDT => 1 KDFNZ
+1 CTVK, 6 FDSX => 6 QVNKN
+3 CTVK, 1 QVNKN => 4 HPKB
+3 NPRST, 1 KGSDJ, 1 CTVK => 2 QMBM
+4 KZFPJ, 1 PQZXH => 5 VLWQB
+2 VQDT => 7 KGSDJ
+3 MPKR => 2 JNKH
+1 KQDVM => 5 XQBS
+3 ZKGMX, 1 XQBS, 11 MZKG, 11 NPRST, 1 DZFNW, 5 VQDT, 2 FHFH => 6 JQNF
+2 FJRFG, 17 BMJR, 3 BJVQM, 55 JQNF, 8 DGFG, 13 ZJGH, 29 ZKTX => 1 FUEL
+27 KZFPJ, 5 VJNBT => 5 MQXF
+11 FDSX, 1 WHVXC, 1 WJDF => 4 ZKGMX
+1 ZVMCB => 4 NWDZ
+1 XLFZJ => 6 LGLNV
+13 ZSCX, 4 XLFZJ => 8 LMNCH
+1 RPWKC, 1 FDSX, 2 BJVQM => 8 JFKGV
+1 WJDF, 1 LKPQG => 4 XSNKB
diff --git a/src/bin/day_14.rs b/src/bin/day_14.rs
new file mode 100644
index 0000000..0532f5f
--- /dev/null
+++ b/src/bin/day_14.rs
@@ -0,0 +1,221 @@
+use rpds::map::red_black_tree_map::RedBlackTreeMap;
+use rpds::rbt_map;
+use rpds::vector::Vector;
+use std::fmt;
+use std::io;
+use std::io::prelude::*;
+use std::iter;
+use std::process;
+use std::str::FromStr;
+use structopt::StructOpt;
+
+#[derive(Debug, StructOpt)]
+#[structopt(name = "Day 14: Space Stoichiometry")]
+/// Finds how much ore you need to produce one fuel.
+///
+/// Recipes are passed in on stdin, one per line.
+///
+/// See https://adventofcode.com/2019/day/14 for details.
+struct Opt {
+    #[structopt(long = "available-ore")]
+    available_ore: Option<i64>,
+}
+
+fn main() {
+    let stdin = io::stdin();
+    let opt = Opt::from_args();
+
+    let recipes = stdin
+        .lock()
+        .lines()
+        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
+        .map(|x| exit_on_failed_assertion(x.parse::<Recipe>(), "Input was not a valid recipe"))
+        .collect::<Vec<_>>();
+
+    match opt.available_ore {
+        Some(ore) => println!("{}", max_fuel_production(ore, &recipes)),
+        None => println!("{}", Desires::new(1).min_ore_required(&recipes)),
+    }
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+    match data {
+        Ok(data) => data,
+        Err(e) => {
+            eprintln!("{}: {}", message, e);
+            process::exit(1);
+        }
+    }
+}
+
+fn max_fuel_production(ore_max: i64, recipes: &[Recipe]) -> i64 {
+    binary_search_max_fuel_production(
+        ore_max / Desires::new(1).min_ore_required(&recipes),
+        2 * ore_max / Desires::new(1).min_ore_required(&recipes),
+        ore_max,
+        recipes,
+    )
+}
+
+fn binary_search_max_fuel_production(
+    fuel_min: i64,
+    fuel_max: i64,
+    ore_max: i64,
+    recipes: &[Recipe],
+) -> i64 {
+    if fuel_max - fuel_min <= 1 {
+        fuel_min
+    } else if Desires::new((fuel_min + fuel_max) / 2).min_ore_required(recipes) <= ore_max {
+        binary_search_max_fuel_production((fuel_min + fuel_max) / 2, fuel_max, ore_max, recipes)
+    } else {
+        binary_search_max_fuel_production(fuel_min, (fuel_min + fuel_max) / 2, ore_max, recipes)
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Recipe {
+    ingredients: Vector<Chemical>,
+    output: Chemical,
+}
+
+#[derive(Default, Debug, Clone)]
+struct Chemical {
+    name: String,
+    quantity: i64,
+}
+
+impl FromStr for Recipe {
+    type Err = ParseErr;
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        // 2 XSNKB, 15 ZVMCB, 3 KDFNZ => 2 RFLX
+        s.replace(" => ", "=")
+            .replace(", ", ",")
+            .split(|c| c == ',' || c == '=')
+            .map(|chem| chem.parse::<Chemical>())
+            .collect::<Result<Vector<Chemical>, ParseErr>>()
+            .map(|chemicals| Recipe {
+                ingredients: chemicals
+                    .drop_last()
+                    .expect("Assertion failed: line did not have any chemicals"),
+                output: chemicals
+                    .last()
+                    .cloned()
+                    .expect("Assertion failed: line did not have any chemicals"),
+            })
+    }
+}
+
+impl Recipe {
+    fn required_scale(&self, desired_quantity: i64) -> i64 {
+        (desired_quantity + self.output.quantity - 1) / self.output.quantity
+    }
+}
+
+impl FromStr for Chemical {
+    type Err = ParseErr;
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        // 1 FUEL
+        match s.split(' ').collect::<Vec<_>>()[..] {
+            [quantity, name] => quantity
+                .parse::<i64>()
+                .map_err(|_| ParseErr)
+                .map(|q| Chemical {
+                    name: name.to_string(),
+                    quantity: q,
+                }),
+            _ => Err(ParseErr),
+        }
+    }
+}
+
+impl Chemical {
+    fn scale(&self, scale: i64) -> Chemical {
+        Chemical {
+            name: self.name.clone(),
+            quantity: self.quantity * scale,
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy)]
+struct ParseErr;
+
+impl fmt::Display for ParseErr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Error parsing input")
+    }
+}
+
+impl std::error::Error for ParseErr {}
+
+#[derive(Debug, Clone)]
+struct Desires {
+    chemicals: RedBlackTreeMap<String, i64>,
+}
+
+impl Desires {
+    fn new(fuel: i64) -> Desires {
+        Desires {
+            chemicals: rbt_map!["FUEL".to_string() => fuel, "ORE".to_string() => 0],
+        }
+    }
+
+    fn min_ore_required(&self, recipes: &[Recipe]) -> i64 {
+        iter::successors(Some(self.clone()), |prev| Some(prev.next(recipes)))
+            .find(|desires| desires.is_only_ore())
+            .unwrap()
+            .chemicals
+            .get("ORE")
+            .cloned()
+            .unwrap()
+    }
+
+    fn is_only_ore(&self) -> bool {
+        !self
+            .chemicals
+            .iter()
+            .any(|(name, quantity)| *quantity > 0 && name != "ORE")
+    }
+
+    fn next(&self, recipes: &[Recipe]) -> Desires {
+        self.chemicals
+            .iter()
+            .find(|(name, quantity)| **quantity > 0 && *name != "ORE")
+            .map(|(mixing, quantity)| {
+                self.with_mixed_recipe(
+                    recipes
+                        .iter()
+                        .find(|recipe| recipe.output.name == *mixing)
+                        .expect("Required chemical without a recipe"),
+                    *quantity,
+                )
+            })
+            .unwrap_or(self.clone())
+    }
+
+    fn with_mixed_recipe(&self, recipe: &Recipe, desired_quantity: i64) -> Desires {
+        recipe.ingredients.iter().fold(
+            self.with_chemical(
+                recipe
+                    .output
+                    .scale(-1 * recipe.required_scale(desired_quantity)),
+            ),
+            |acc, next_ingredient| {
+                acc.with_chemical(next_ingredient.scale(recipe.required_scale(desired_quantity)))
+            },
+        )
+    }
+
+    fn with_chemical(&self, chemical: Chemical) -> Desires {
+        Desires {
+            chemicals: match self.chemicals.get(&chemical.name) {
+                Some(existing_quantity) => self
+                    .chemicals
+                    .insert(chemical.name.clone(), existing_quantity + chemical.quantity),
+                None => self
+                    .chemicals
+                    .insert(chemical.name.clone(), chemical.quantity),
+            },
+        }
+    }
+}