From 19bc2a98dcececcdad39dabd513caa80f8a8f023 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sun, 22 Dec 2019 16:43:12 +0200 Subject: Day 14, refueling --- inputs/day_14.txt | 59 +++++++++++++++ src/bin/day_14.rs | 221 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 280 insertions(+) create mode 100644 inputs/day_14.txt create mode 100644 src/bin/day_14.rs 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, +} + +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::(), "Input was not a valid recipe")) + .collect::>(); + + 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(data: Result, 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, + 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 { + // 2 XSNKB, 15 ZVMCB, 3 KDFNZ => 2 RFLX + s.replace(" => ", "=") + .replace(", ", ",") + .split(|c| c == ',' || c == '=') + .map(|chem| chem.parse::()) + .collect::, 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 { + // 1 FUEL + match s.split(' ').collect::>()[..] { + [quantity, name] => quantity + .parse::() + .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, +} + +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), + }, + } + } +} -- cgit v1.2.3