From fc12d3728a85d2e0a3d4de32a30faa0c7162ab2f Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 21 Dec 2022 18:45:26 +0200 Subject: Day 21 part 1 --- 2022/src/bin/day_21.rs | 291 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 291 insertions(+) create mode 100644 2022/src/bin/day_21.rs (limited to '2022/src/bin') diff --git a/2022/src/bin/day_21.rs b/2022/src/bin/day_21.rs new file mode 100644 index 0000000..7b23bab --- /dev/null +++ b/2022/src/bin/day_21.rs @@ -0,0 +1,291 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, i64, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fmt, fs, +}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_21.txt")?; + let mut monkeys = Monkeys::parser(&input).unwrap().1; + + dbg!(monkeys.eval("root")); + + let (original_root_left, original_root_right) = + monkeys.0.get("root").expect("No root monkey!").values(); + + monkeys.0.insert( + "root".into(), + Expression::Eql(original_root_left, original_root_right.expect("foo")), + ); + monkeys + .0 + .insert("humn".into(), Expression::Value(Value::Input)); + + // TODO: This should be some sort of loop until done. It isn't complete yet. + monkeys.simplify(); + dbg!(monkeys.0.len()); + monkeys.simplify(); + dbg!(monkeys.0.len()); + monkeys.simplify(); + dbg!(monkeys.0.len()); + dbg!(monkeys.print_expression("root")); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Monkeys(BTreeMap); + +#[derive(Debug, Clone)] +enum Expression { + Value(Value), + Add(Value, Value), + Sub(Value, Value), + Mul(Value, Value), + Div(Value, Value), + Eql(Value, Value), +} + +#[derive(Debug, Clone)] +enum Value { + Ref(String), + Literal(i64), + Input, +} + +impl Monkeys { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, tuple((alpha1, tag(": "), Expression::parser))), + |lines| { + Monkeys( + lines + .into_iter() + .map(|(id, _, expression): (&str, _, Expression)| { + (id.to_owned(), expression) + }) + .collect(), + ) + }, + )(input) + } + + fn simplify(&mut self) { + let ids: Vec = self.0.keys().cloned().collect(); + + // simplify to literals where possible + for id in &ids { + if let Some(val) = self.eval(id) { + self.0 + .insert(id.clone(), Expression::Value(Value::Literal(val))); + } + } + + // simplify single sides of expressions where possible (especially unwrap refs) + for id in &ids { + let monkey = self.0.get(id).expect("Unknown monkey!"); + let simplified = match monkey { + Expression::Value(v) => Expression::Value(self.simplify_value(v)), + Expression::Add(a, b) => { + Expression::Add(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Sub(a, b) => { + Expression::Sub(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Mul(a, b) => { + Expression::Mul(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Div(a, b) => { + Expression::Div(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Eql(a, b) => { + Expression::Eql(self.simplify_value(a), self.simplify_value(b)) + } + }; + self.0.insert(id.clone(), simplified); + + if let Some(val) = self.eval(id) { + self.0 + .insert(id.clone(), Expression::Value(Value::Literal(val))); + } + } + + // simplify across the equals + // TODO: There are probably more of these cases needed + for id in &ids { + let monkey = self.0.get(id).expect("Unknown monkey!").clone(); + match monkey { + Expression::Eql(Value::Ref(r), Value::Literal(v)) + | Expression::Eql(Value::Literal(v), Value::Ref(r)) => { + let referenced_monkey = self.0.get(&r).expect("Unknown monkey!").clone(); + + let new_eql = match referenced_monkey { + Expression::Add(Value::Ref(new_r), Value::Literal(added)) + | Expression::Add(Value::Literal(added), Value::Ref(new_r)) => { + Some((new_r.clone(), v - added)) + } + Expression::Sub(Value::Ref(new_r), Value::Literal(subtracted)) => { + Some((new_r.clone(), v + subtracted)) + } + Expression::Mul(Value::Ref(new_r), Value::Literal(mult)) + | Expression::Mul(Value::Literal(mult), Value::Ref(new_r)) => { + Some((new_r.clone(), v / mult)) + } + Expression::Div(Value::Ref(new_r), Value::Literal(denom)) => { + Some((new_r.clone(), v * denom)) + } + _ => None, + }; + + if let Some((new_r, new_v)) = new_eql { + self.0.insert( + id.clone(), + Expression::Eql(Value::Ref(new_r), Value::Literal(new_v)), + ); + } + } + _ => {} + } + } + + // clearing out unreferenced monkeys + let monkey_references: BTreeSet = self + .0 + .values() + .flat_map(|expression| match expression.values() { + (Value::Ref(v1), Some(Value::Ref(v2))) => vec![v1, v2], + (Value::Ref(v), _) | (_, Some(Value::Ref(v))) => vec![v], + _ => vec![], + }) + .collect(); + for id in &ids { + if id != "root" && !monkey_references.contains(id) { + self.0.remove(id); + } + } + } + + fn simplify_value(&self, val: &Value) -> Value { + match val { + Value::Ref(r) => { + let referenced = self.0.get(r).expect("Unknown monkey!"); + match referenced { + Expression::Value(v) => v.clone(), + _ => val.clone(), + } + } + v => v.clone(), + } + } + + fn eval(&self, id: &str) -> Option { + let monkey = self.0.get(id).expect("Unknown monkey!"); + + match monkey { + Expression::Value(v) => self.resolve_value(v), + Expression::Add(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a + b), + Expression::Sub(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a - b), + Expression::Mul(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a * b), + Expression::Div(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a / b), + Expression::Eql(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| if a == b { 1 } else { 0 }), + } + } + + fn resolve_value(&self, value: &Value) -> Option { + match value { + Value::Ref(id) => self.eval(id), + Value::Literal(num) => Some(*num), + Value::Input => None, + } + } + + fn print_expression(&self, id: &str) -> String { + let monkey = self.0.get(id).expect("Unknown monkey!"); + + match monkey { + Expression::Value(v) => format!("({})", self.print_value(v)), + Expression::Add(a, b) => format!("({} + {})", self.print_value(a), self.print_value(b)), + Expression::Sub(a, b) => format!("({} - {})", self.print_value(a), self.print_value(b)), + Expression::Mul(a, b) => format!("({} * {})", self.print_value(a), self.print_value(b)), + Expression::Div(a, b) => format!("({} / {})", self.print_value(a), self.print_value(b)), + Expression::Eql(a, b) => { + format!("({} == {})", self.print_value(a), self.print_value(b)) + } + } + } + + fn print_value(&self, value: &Value) -> String { + match value { + Value::Ref(id) => self.print_expression(id), + Value::Literal(num) => format!("{}", num), + Value::Input => "input".into(), + } + } +} + +impl Expression { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map( + tuple((Value::parser, tag(" + "), Value::parser)), + |(a, _, b)| Expression::Add(a, b), + ), + map( + tuple((Value::parser, tag(" - "), Value::parser)), + |(a, _, b)| Expression::Sub(a, b), + ), + map( + tuple((Value::parser, tag(" * "), Value::parser)), + |(a, _, b)| Expression::Mul(a, b), + ), + map( + tuple((Value::parser, tag(" / "), Value::parser)), + |(a, _, b)| Expression::Div(a, b), + ), + map(Value::parser, Expression::Value), + ))(input) + } + + fn values(&self) -> (Value, Option) { + match self.clone() { + Expression::Value(v) => (v, None), + Expression::Add(a, b) => (a, Some(b)), + Expression::Sub(a, b) => (a, Some(b)), + Expression::Mul(a, b) => (a, Some(b)), + Expression::Div(a, b) => (a, Some(b)), + Expression::Eql(a, b) => (a, Some(b)), + } + } +} + +impl Value { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map(i64, Value::Literal), + map(alpha1, |s: &str| Value::Ref(s.to_owned())), + ))(input) + } +} -- cgit v1.2.3