2020-12-26 09:38:29 +00:00
|
|
|
const INPUT: &str = include_str!("../../data/day18");
|
|
|
|
|
|
|
|
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
|
|
|
|
enum Op {
|
|
|
|
Sum,
|
|
|
|
Mul,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl Op {
|
|
|
|
fn apply<T>(self, a: T, b: T) -> T
|
|
|
|
where
|
|
|
|
T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T>,
|
|
|
|
{
|
|
|
|
match self {
|
|
|
|
Self::Sum => a + b,
|
|
|
|
Self::Mul => a * b,
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
|
|
|
|
enum Elem<T> {
|
|
|
|
ParenLeft,
|
|
|
|
Op(Op),
|
|
|
|
Item(T),
|
|
|
|
}
|
|
|
|
|
|
|
|
impl<T> Elem<T> {
|
|
|
|
fn expect_item(self) -> T {
|
|
|
|
if let Elem::Item(item) = self {
|
|
|
|
item
|
|
|
|
} else {
|
|
|
|
panic!("Expected item");
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn expect_op(self) -> Op {
|
|
|
|
if let Elem::Op(op) = self {
|
|
|
|
op
|
|
|
|
} else {
|
|
|
|
panic!("Expected op");
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn expect_paren_left(self) {
|
|
|
|
if let Elem::ParenLeft = self {
|
|
|
|
()
|
|
|
|
} else {
|
|
|
|
panic!("Expected '('");
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
#[derive(Debug)]
|
|
|
|
struct Stack<T> {
|
|
|
|
elems: Vec<Elem<T>>,
|
|
|
|
same_precedence: bool,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl<T> Stack<T>
|
|
|
|
where
|
|
|
|
T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T> + std::fmt::Debug,
|
|
|
|
{
|
|
|
|
fn new(same_precedence: bool) -> Self {
|
|
|
|
Self {
|
|
|
|
elems: Vec::new(),
|
|
|
|
same_precedence,
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn push_item(&mut self, item: T) {
|
|
|
|
self.elems.push(Elem::Item(item))
|
|
|
|
}
|
|
|
|
|
|
|
|
fn push_op(&mut self, op: Op) {
|
|
|
|
self.elems.push(Elem::Op(op))
|
|
|
|
}
|
|
|
|
|
|
|
|
fn push_paren_left(&mut self) {
|
|
|
|
self.elems.push(Elem::ParenLeft)
|
|
|
|
}
|
|
|
|
|
|
|
|
fn _peek_top(&self) -> &Elem<T> {
|
|
|
|
&self.elems[self.elems.len() - 1]
|
|
|
|
}
|
|
|
|
|
|
|
|
fn _peek_below_top(&self) -> &Elem<T> {
|
|
|
|
&self.elems[self.elems.len() - 2]
|
|
|
|
}
|
|
|
|
|
|
|
|
fn pop_item(&mut self) -> T {
|
|
|
|
self.elems.pop().expect("expect non empty stack").expect_item()
|
|
|
|
}
|
|
|
|
|
|
|
|
fn pop_op(&mut self) -> Op {
|
|
|
|
self.elems.pop().expect("expect non empty stack").expect_op()
|
|
|
|
}
|
|
|
|
|
|
|
|
fn pop_paren_left(&mut self) {
|
|
|
|
self.elems.pop().expect("expect non empty stack").expect_paren_left()
|
|
|
|
}
|
|
|
|
|
|
|
|
fn _do_reduce_op(&self, finish: bool) -> bool {
|
|
|
|
match self._peek_below_top() {
|
|
|
|
Elem::Op(Op::Sum) => true,
|
|
|
|
Elem::Op(Op::Mul) => finish || self.same_precedence,
|
|
|
|
_ => false,
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn is_empty(&self) -> bool {
|
|
|
|
self.elems.is_empty()
|
|
|
|
}
|
|
|
|
|
|
|
|
fn eval_top(&mut self, finish: bool) {
|
|
|
|
while self.elems.len() > 2 && matches!(self._peek_top(), Elem::Item(_)) && self._do_reduce_op(finish) {
|
|
|
|
let value2 = self.pop_item();
|
|
|
|
let op = self.pop_op();
|
|
|
|
let value1 = self.pop_item();
|
|
|
|
self.push_item(op.apply(value1, value2));
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn parse<T>(mut line: &str, same_precedence: bool) -> T
|
|
|
|
where
|
|
|
|
T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T> + std::str::FromStr + std::fmt::Debug,
|
|
|
|
<T as std::str::FromStr>::Err: std::fmt::Debug,
|
|
|
|
{
|
|
|
|
let mut stack = Stack::new(same_precedence);
|
|
|
|
|
|
|
|
loop {
|
|
|
|
line = line.trim();
|
|
|
|
if line.is_empty() {
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
if let Some(rem) = line.strip_prefix('+') {
|
|
|
|
stack.push_op(Op::Sum);
|
|
|
|
line = rem;
|
|
|
|
} else if let Some(rem) = line.strip_prefix('*') {
|
|
|
|
stack.push_op(Op::Mul);
|
|
|
|
line = rem;
|
|
|
|
} else if let Some(rem) = line.strip_prefix('(') {
|
|
|
|
stack.push_paren_left();
|
|
|
|
line = rem;
|
|
|
|
} else if let Some(rem) = line.strip_prefix(')') {
|
|
|
|
stack.eval_top(true);
|
|
|
|
let item = stack.pop_item();
|
|
|
|
stack.pop_paren_left();
|
|
|
|
stack.push_item(item);
|
|
|
|
line = rem;
|
|
|
|
} else {
|
|
|
|
let num_end = line.find(|c: char| !c.is_ascii_digit()).unwrap_or(line.len());
|
|
|
|
let num = line[..num_end].parse::<T>().unwrap();
|
|
|
|
stack.push_item(num);
|
|
|
|
line = &line[num_end..];
|
|
|
|
}
|
|
|
|
stack.eval_top(false);
|
|
|
|
}
|
|
|
|
stack.eval_top(true);
|
|
|
|
let item = stack.pop_item();
|
|
|
|
assert!(stack.is_empty());
|
|
|
|
item
|
|
|
|
}
|
|
|
|
|
|
|
|
fn main() {
|
|
|
|
println!("Sum of evaluated lines (simple math): {}", INPUT.lines().map(|l| parse::<u64>(l, true)).sum::<u64>());
|
|
|
|
println!("Sum of evaluated lines (advanced math): {}", INPUT.lines().map(|l| parse::<u64>(l, false)).sum::<u64>());
|
|
|
|
}
|