commit 8b195a355ad62985df7f0b2d17d710ec17d69028
parent 5ade4df40362d4d4ccfb5b11e34cdea3bc8a230c
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sat, 14 Dec 2019 11:50:13 -0500
Add Rust solution for day 14
Diffstat:
| A | day-14/day-14.rs | | | 84 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 84 insertions(+), 0 deletions(-)
diff --git a/day-14/day-14.rs b/day-14/day-14.rs
@@ -0,0 +1,84 @@
+use std::collections::HashMap;
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+
+fn main() {
+ let input = BufReader::new(File::open("input.txt").unwrap())
+ .lines()
+ .map(|line| {
+ let line = line.unwrap();
+ let mut line = line.split(" => ");
+ let mut material = line
+ .next()
+ .unwrap()
+ .split(", ")
+ .map(|term| {
+ let term = term.split(" ").collect::<Vec<_>>();
+ (term[1].to_string(), term[0].parse::<u64>().unwrap())
+ })
+ .collect::<HashMap<_, _>>();
+ let product = line.next().unwrap().split(" ").collect::<Vec<_>>();
+ let product = (product[1].to_string(), product[0].parse::<u64>().unwrap());
+ material.insert(product.0.clone(), product.1);
+ (product.0, material)
+ })
+ .collect::<HashMap<String, HashMap<String, u64>>>();
+ println!("Rust:");
+ println!("Part 1: {}", part_1(&input));
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn calc_fuel_cost(recipes: &HashMap<String, HashMap<String, u64>>, fuel_count: u64) -> u64 {
+ let mut chemicals = HashMap::new();
+ chemicals.insert("FUEL".to_string(), fuel_count);
+ let mut leftovers = HashMap::new();
+ let mut ore_count = 0;
+ while !chemicals.is_empty() {
+ let target = chemicals.keys().next().unwrap().to_string();
+ let mut amount = chemicals.remove(&target).unwrap();
+ if target == "ORE" {
+ ore_count += amount;
+ continue;
+ }
+ // Check leftovers before commiting to reaction.
+ let leftover_amount = *leftovers.entry(target.clone()).or_insert(0);
+ *leftovers.get_mut(&target).unwrap() -= amount.min(leftover_amount);
+ amount -= amount.min(leftover_amount);
+ if amount == 0 {
+ continue;
+ }
+ // Initiate new reaction.
+ let recipe = &recipes[&target];
+ let reaction_count = (amount as f64 / recipe[&target] as f64).ceil() as u64;
+ for (k, v) in recipe {
+ if *k != target {
+ *chemicals.entry(k.clone()).or_insert(0) += v * reaction_count;
+ } else {
+ // Place excess product in leftovers.
+ *leftovers.entry(k.clone()).or_insert(0) += v * reaction_count - amount;
+ }
+ }
+ }
+ ore_count
+}
+
+fn part_1(input: &HashMap<String, HashMap<String, u64>>) -> u64 {
+ calc_fuel_cost(input, 1)
+}
+
+fn part_2(input: &HashMap<String, HashMap<String, u64>>) -> u64 {
+ // Binary search.
+ let ore_cargo = 1000000000000;
+ let mut lo = 1;
+ let mut hi = ore_cargo;
+ while lo + 1 < hi {
+ let mi = lo + (hi - lo) / 2;
+ if calc_fuel_cost(input, mi) > ore_cargo {
+ hi = mi;
+ } else {
+ lo = mi;
+ }
+ }
+ lo
+}