18

8 files changed, 570 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(())
+}
+