diff options
| -rw-r--r-- | 18/Cargo.toml | 17 | ||||
| -rw-r--r-- | 18/build.rs | 5 | ||||
| -rw-r--r-- | 18/input | 100 | ||||
| -rw-r--r-- | 18/src/expression.lalrpop | 34 | ||||
| -rw-r--r-- | 18/src/main.rs | 363 | ||||
| -rw-r--r-- | 18/src/types.rs | 32 | ||||
| -rw-r--r-- | 18/tests/.main.rs.swn | bin | 0 -> 12288 bytes | |||
| -rw-r--r-- | 18/tests/main.rs | 19 | ||||
| -rw-r--r-- | Cargo.lock | 10 | ||||
| -rw-r--r-- | Cargo.toml | 1 |
10 files changed, 581 insertions, 0 deletions
diff --git a/18/Cargo.toml b/18/Cargo.toml new file mode 100644 index 0000000..d5e4d18 --- /dev/null +++ b/18/Cargo.toml @@ -0,0 +1,17 @@ +[package] +name = "advent_18" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } +lalrpop-util = "0.19" + +[dev-dependencies] +assert_cmd = "0.10" +lalrpop = { version = "0.19", features = [ "lexer" ] } + +[build-dependencies] +lalrpop = { version = "0.19", features = [ "lexer" ] } + diff --git a/18/build.rs b/18/build.rs new file mode 100644 index 0000000..23c7d3f --- /dev/null +++ b/18/build.rs @@ -0,0 +1,5 @@ +extern crate lalrpop; + +fn main() { + lalrpop::process_root().unwrap(); +} diff --git a/18/input b/18/input new file mode 100644 index 0000000..ccdfb2b --- /dev/null +++ b/18/input @@ -0,0 +1,100 @@ +[2,[0,[9,[5,9]]]] +[[2,[1,8]],3] +[[[[7,2],6],[[7,8],3]],[9,[[6,9],2]]] +[[[[7,2],[9,8]],7],[4,[[2,2],[5,0]]]] +[[8,[2,2]],[5,[9,[4,9]]]] +[[[[6,2],[4,8]],5],0] +[[3,[3,[6,6]]],[6,9]] +[[[9,5],[[8,2],[4,0]]],[[5,5],[[5,0],[1,9]]]] +[[[[7,4],[8,1]],[2,[7,1]]],2] +[[[[9,6],3],8],[[[9,8],7],[5,[0,8]]]] +[[[4,[4,0]],[[7,3],3]],[8,[3,[8,2]]]] +[[[[8,4],1],6],[[1,[8,7]],1]] +[[[8,2],[[1,4],3]],[[4,5],[[9,1],[7,2]]]] +[[[[5,0],[8,8]],[[4,2],4]],[2,[[4,3],[3,7]]]] +[[[8,7],[2,1]],[9,3]] +[[3,[7,4]],[0,3]] +[4,[[[5,0],[5,2]],3]] +[[[[0,1],0],8],[6,3]] +[[7,[[9,8],[2,7]]],[[[8,8],[9,4]],[[0,5],[4,1]]]] +[[[[3,7],[5,4]],[8,[1,8]]],[[1,8],[[6,9],9]]] +[[[[7,4],[7,7]],7],[1,[[8,2],[1,8]]]] +[[[[6,2],8],[[1,2],3]],[[[3,6],[4,9]],[[3,1],[9,8]]]] +[[[3,[1,1]],[[6,5],[2,2]]],9] +[[[[9,1],4],1],[[[1,3],3],[0,[1,4]]]] +[[[5,0],[4,[6,8]]],[[2,4],[[0,3],[2,6]]]] +[9,[[9,[1,5]],1]] +[[1,[[6,0],[9,2]]],[[[4,2],7],[[2,9],6]]] +[[[[8,2],8],9],[[[4,9],[3,8]],2]] +[[[9,1],[6,5]],[[[9,5],5],1]] +[[[[1,3],5],2],[1,1]] +[[[[0,0],[8,1]],8],8] +[[[[3,3],5],[[9,6],9]],[[3,[0,9]],7]] +[[[6,5],1],1] +[[[4,[1,3]],[[2,2],2]],[[8,0],[[8,1],[2,6]]]] +[9,[[4,6],2]] +[[[5,[8,8]],[[1,8],[4,9]]],[9,[3,6]]] +[[[[9,3],3],0],8] +[[[5,0],[[2,8],[1,1]]],[[[5,6],9],8]] +[[[[5,0],[5,2]],[[7,0],[9,8]]],[3,[[5,7],[5,9]]]] +[[3,[5,7]],1] +[[[[2,5],[0,7]],9],[[[3,2],1],[7,1]]] +[6,[7,[6,0]]] +[[[8,5],[[1,7],[7,6]]],[[1,3],[5,[1,9]]]] +[[[[9,4],[8,3]],1],[[1,6],[[2,5],1]]] +[[[[6,5],[6,6]],[5,5]],[1,8]] +[[[[7,7],[2,2]],3],[1,[[8,6],[5,1]]]] +[[6,[2,4]],[[8,8],[[3,5],6]]] +[[1,[[6,1],[9,3]]],[[2,0],5]] +[[[5,9],[6,[1,9]]],[3,[4,[7,7]]]] +[[[[3,6],[8,5]],[[9,4],[4,1]]],[3,3]] +[[[3,9],[1,6]],2] +[[[[0,9],7],6],[7,[9,[9,9]]]] +[[[5,[6,0]],[8,[7,5]]],[[[8,8],0],[8,1]]] +[[[[6,9],[9,0]],2],[[[0,3],[1,6]],[2,4]]] +[[[[8,2],[3,0]],[[3,8],8]],[6,[[9,3],4]]] +[[[6,6],2],[5,[1,4]]] +[[1,[1,4]],[[[4,3],0],1]] +[[[[9,9],3],0],[[[3,3],[2,8]],[1,0]]] +[[[[1,1],[3,5]],[9,7]],4] +[[[9,[3,6]],5],[[4,9],[9,3]]] +[[8,7],[5,[7,[7,7]]]] +[[[[0,5],[7,3]],[[8,6],8]],[[[4,4],[5,0]],[[2,2],2]]] +[[[5,0],[[1,9],[5,8]]],[[1,5],[[9,3],[0,7]]]] +[[[1,[1,5]],[8,[2,2]]],0] +[[[6,[7,8]],[[0,2],5]],[3,[5,[8,0]]]] +[[[[1,7],2],3],[[[8,7],[7,8]],[7,[5,5]]]] +[[1,[7,[3,3]]],[8,[9,[3,0]]]] +[[5,6],[[5,[2,8]],[[5,5],[8,8]]]] +[[8,[[7,7],[4,0]]],[[5,[0,4]],[6,[6,2]]]] +[[4,[[0,0],[0,1]]],[[3,1],[[6,7],4]]] +[[[[3,2],[4,2]],[[4,4],[6,3]]],[9,[0,[1,9]]]] +[[[[4,6],2],[[9,6],4]],[[9,[9,1]],[0,[1,8]]]] +[[[5,8],[[6,5],[0,4]]],[[0,[6,3]],[2,0]]] +[[6,8],[[5,5],[5,8]]] +[[[7,3],[8,[6,7]]],[[[1,5],2],7]] +[[6,[8,[8,9]]],[[[1,1],[3,0]],[[7,2],[3,7]]]] +[[[[8,1],6],[9,[5,1]]],[[[5,9],[1,9]],5]] +[[[[3,6],[5,7]],[[0,3],8]],[3,[[2,1],0]]] +[[7,[5,1]],[[[3,6],9],[[4,0],6]]] +[[[[3,8],8],0],[[1,[1,4]],[[4,5],[8,5]]]] +[[[8,[0,6]],[4,3]],[8,[[1,5],8]]] +[2,[[1,[9,7]],[[2,0],6]]] +[[[[7,4],4],[[4,9],3]],[[[6,5],[0,5]],[[9,8],[2,6]]]] +[[[3,[7,2]],[[7,7],4]],[[[3,4],[6,0]],[6,3]]] +[[[1,9],[[9,8],9]],5] +[[[4,2],2],[[[4,4],7],5]] +[[[9,1],[2,[1,5]]],[[4,3],[4,[9,5]]]] +[2,[[[8,4],1],[[2,4],2]]] +[[[0,6],5],[1,[[2,0],6]]] +[[[[2,4],[1,7]],[1,0]],[9,5]] +[[7,[3,[2,0]]],[[7,8],8]] +[[9,[1,0]],[[0,4],[[0,1],0]]] +[0,9] +[[[[2,9],[2,4]],[[5,6],8]],[[5,[1,4]],[3,[0,6]]]] +[[5,[[5,8],0]],[[[0,6],[4,5]],[[8,9],[8,3]]]] +[[[[5,2],[7,7]],[0,[4,1]]],[[8,7],[[5,3],7]]] +[[[5,3],5],[0,0]] +[3,5] +[[2,6],5] +[[5,[[6,0],3]],[[3,[8,7]],[2,0]]] diff --git a/18/src/expression.lalrpop b/18/src/expression.lalrpop new file mode 100644 index 0000000..49356f6 --- /dev/null +++ b/18/src/expression.lalrpop @@ -0,0 +1,34 @@ +use crate::types::{Pair, Value}; + +grammar; + +pub Pair: Pair = { + LEFT_BRACKET <left:Value> COMMA <right:Value> RIGHT_BRACKET => { + Pair { + left: left, + right: right, + } + }, +}; + +Value: Value = { + NUMBER => { + Value::Literal(<>.parse::<i64>().unwrap()) + }, + Pair => { + Value::Pair(Box::new(<>)) + }, +}; + +match { + r"\p{Zs}+" => { }, + + r"[0-9]+" => NUMBER, + + "," => COMMA, + + "[" => LEFT_BRACKET, + + "]" => RIGHT_BRACKET, +} + diff --git a/18/src/main.rs b/18/src/main.rs new file mode 100644 index 0000000..df21bd0 --- /dev/null +++ b/18/src/main.rs @@ -0,0 +1,363 @@ +use advent_lib::prelude::*; + +use crate::types::{Pair, Value}; +#[macro_use] extern crate lalrpop_util; + +pub mod types; +lalrpop_mod!(pub expression); + + +#[derive(Debug, Clone)] +enum Step { + Left, + Right, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let parser = expression::PairParser::new(); + + let mut result = None; + for line in &input { + let expression = Box::new(parser.parse(line)?); + + match result { + None => { + result = Some(expression); + } + Some(previous_result) => { + let mut new_expression = add(previous_result, expression); + reduce(&mut new_expression); + result = Some(new_expression); + } + } + } + + let output = magnitude(&result.unwrap()); + println!("{}", output); + + let mut expressions = Vec::new(); + for line in &input { + expressions.push(Box::new(parser.parse(line)?)); + } + + let mut max_sum = None; + for i in 0 .. expressions.len() - 2 { + for j in i + 1 .. expressions.len() - 1 { + let left = expressions[i].clone(); + let right = expressions[j].clone(); + let mut sum = add(left, right); + reduce(&mut sum); + let sum = magnitude(&sum); + match max_sum { + None => { + max_sum = Some(sum); + } + Some(old_sum) => { + if sum > old_sum { + max_sum = Some(sum); + } + } + } + } + } + + println!("{}", max_sum.unwrap()); + + Ok(()) +} + + +fn add(left: Box<Pair>, right: Box<Pair>) -> Box<Pair> { + Box::new(Pair { + left: Value::Pair(left), + right: Value::Pair(right), + }) +} + + +fn reduce(expression: &mut Box<Pair>) { + loop { + match find_four_x_nested(&expression, Vec::new(), 0) { + None => { } + Some((path, left_addend, right_addend)) => { + match subtree_to_left(&path) { + None => { } + Some(left_path) => { + let subtree = get_subtree(expression, &left_path); + add_to_rightmost_value(subtree, left_addend); + } + } + + match subtree_to_right(&path) { + None => { } + Some(right_path) => { + let subtree = get_subtree(expression, &right_path); + add_to_leftmost_value(subtree, right_addend); + } + } + + replace_with_zero(expression, &path); + + continue; + } + } + + if perform_split(expression) { + continue; + } + + break; + } +} + + +fn find_four_x_nested(expression: &Pair, path_so_far: Vec<Step>, depth: usize) + -> Option<(Vec<Step>, i64, i64)> +{ + if depth >= 4 { + match (&expression.left, &expression.right) { + (Value::Literal(left), Value::Literal(right)) => { + return Some((path_so_far, *left, *right)) + } + //_ => { panic!("you don't say"); } + _ => { return None; } + } + } + + match &expression.left { + Value::Literal(_) => { } + Value::Pair(left) => { + let mut path = path_so_far.clone(); + path.push(Step::Left); + let result = find_four_x_nested(left.as_ref(), path, depth + 1); + if result.is_some() { + return result; + } + } + } + + match &expression.right { + Value::Literal(_) => { } + Value::Pair(right) => { + let mut path = path_so_far.clone(); + path.push(Step::Right); + let result = find_four_x_nested(right.as_ref(), path, depth + 1); + if result.is_some() { + return result; + } + } + } + + None +} + + +fn subtree_to_left(path: &Vec<Step>) -> Option<Vec<Step>> { + let mut result = path.clone(); + + loop { + match result[result.len() - 1] { + Step::Left => { + result.pop(); + + if result.len() == 0 { + return None; + } + } + Step::Right => { + result.pop(); + result.push(Step::Left); + return Some(result); + } + } + } +} + + +fn subtree_to_right(path: &Vec<Step>) -> Option<Vec<Step>> { + let mut result = path.clone(); + + loop { + match result[result.len() - 1] { + Step::Left => { + result.pop(); + result.push(Step::Right); + return Some(result); + } + Step::Right => { + result.pop(); + + if result.len() == 0 { + return None; + } + } + } + } +} + + +fn get_subtree<'a>(pair: &'a mut Box<Pair>, path: &Vec<Step>) -> &'a mut Value { + let mut here: &mut Box<Pair> = pair; + + for (i, step) in path.iter().enumerate() { + if i == path.len() - 1 { + match step { + Step::Left => { + return &mut here.left; + } + Step::Right => { + return &mut here.right; + } + } + } else { + match step { + Step::Left => { + match &mut here.left { + Value::Pair(left) => { + here = left; + } + _ => { panic!("left is not a pair"); } + } + } + Step::Right => { + match &mut here.right { + Value::Pair(right) => { + here = right; + } + _ => { panic!("right is not a pair"); } + } + } + } + } + } + + panic!("empty path"); +} + + +fn add_to_rightmost_value(subtree: &mut Value, addend: i64) { + match subtree { + Value::Literal(value) => { + *value += addend; + } + Value::Pair(pair) => { + add_to_rightmost_value(&mut pair.right, addend); + } + } +} + + +fn add_to_leftmost_value(subtree: &mut Value, addend: i64) { + match subtree { + Value::Literal(value) => { + *value += addend; + } + Value::Pair(pair) => { + add_to_leftmost_value(&mut pair.left, addend); + } + } +} + + +fn replace_with_zero(pair: &mut Box<Pair>, path: &Vec<Step>) { + let mut here: &mut Box<Pair> = pair; + + for (i, step) in path.iter().enumerate() { + if i == path.len() - 1 { + match step { + Step::Left => { + here.left = Value::Literal(0); + } + Step::Right => { + here.right = Value::Literal(0); + } + } + } else { + match step { + Step::Left => { + match &mut here.left { + Value::Pair(left) => { + here = left; + } + _ => { panic!("left is not a pair"); } + } + } + Step::Right => { + match &mut here.right { + Value::Pair(right) => { + here = right; + } + _ => { panic!("right is not a pair"); } + } + } + } + } + } +} + + +fn perform_split(expression: &mut Box<Pair>) -> bool { + match &mut expression.left { + Value::Literal(n) => { + if *n >= 10 { + expression.left = Value::Pair(Box::new(Pair { + left: Value::Literal((*n as f64 / 2.0).floor() as i64), + right: Value::Literal((*n as f64 / 2.0).ceil() as i64), + })); + return true; + } + } + Value::Pair(left) => { + if perform_split(left) { + return true; + } + } + } + + match &mut expression.right { + Value::Literal(n) => { + if *n >= 10 { + expression.right = Value::Pair(Box::new(Pair { + left: Value::Literal((*n as f64 / 2.0).floor() as i64), + right: Value::Literal((*n as f64 / 2.0).ceil() as i64), + })); + return true; + } + } + Value::Pair(right) => { + if perform_split(right) { + return true; + } + } + } + + false +} + + +fn magnitude(expression: &Box<Pair>) -> i64 { + let mut result = 0; + + result += 3 * match &expression.left { + Value::Literal(n) => *n, + Value::Pair(left) => magnitude(left), + }; + + result += 2 * match &expression.right { + Value::Literal(n) => *n, + Value::Pair(right) => magnitude(right), + }; + + result +} + diff --git a/18/src/types.rs b/18/src/types.rs new file mode 100644 index 0000000..6800fdc --- /dev/null +++ b/18/src/types.rs @@ -0,0 +1,32 @@ +use std::fmt; + + +#[derive(Clone)] +pub enum Value { + Literal(i64), + Pair(Box<Pair>), +} + +#[derive(Clone)] +pub struct Pair { + pub left: Value, + pub right: Value, +} + + +impl fmt::Debug for Value { + fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Value::Literal(n) => { write!(formatter, "{}", n) } + Value::Pair(pair) => { write!(formatter, "{:?}", pair) } + } + } +} + + +impl fmt::Debug for Pair { + fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(formatter, "[{:?},{:?}]", self.left, self.right) + } +} + diff --git a/18/tests/.main.rs.swn b/18/tests/.main.rs.swn new file mode 100644 index 0000000..6017cf8 --- /dev/null +++ b/18/tests/.main.rs.swn Binary files differdiff --git a/18/tests/main.rs b/18/tests/main.rs new file mode 100644 index 0000000..af55fe3 --- /dev/null +++ b/18/tests/main.rs @@ -0,0 +1,19 @@ +use assert_cmd::prelude::*; +//use predicates::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_18")?; + + command.arg("input"); + command.assert().success().stdout( + "3216\n\ + 4643\n"); + + + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index 48af539..f55c263 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -137,6 +137,16 @@ dependencies = [ ] [[package]] +name = "advent_18" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", + "lalrpop", + "lalrpop-util", +] + +[[package]] name = "advent_lib" version = "0.1.0" dependencies = [ diff --git a/Cargo.toml b/Cargo.toml index c2dfe1d..75704cb 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -18,4 +18,5 @@ members = [ "15", "16", "17", + "18", ] |