You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

169 lines
4.2 KiB

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>());
}