Advent of Code 2020 day18

https://adventofcode.com/2020/day/18

part1

1 + 2 * 3 + 4 * 5 + 6
1 + (2 * 3) + (4 * (5 + 6))

のような入力が与えられる。数値計算だが普通の四則演算とは演算子の順序が異なる。*が+より優先されるということがなく、左から右に順番に評価され、括弧だけがそれらより優先される。
上の例の1つ目だと

  1 + 2 * 3 + 4 * 5 + 6
= 3 * 3 + 4 * 5 + 6
= 9 + 4 * 5 + 6
= 13 * 5 + 6
= 65 + 6
= 71

2つ目の例は

  1 + (2 * 3) + (4 * (5 + 6))
= 1 + (2 * 3) + (4 * 11)
= 1 + (2 * 3) + 44
= 1 + 6 + 44
= 7 + 44
= 51

という具合。この法則に従ってすべての式の結果の和を求めよ。という問題。
括弧で囲まれた部分をうまく再帰的に処理していくことが出来ればそれほど問題なさそう。ここでは expression.chars() でCharsを取得し、それを引数に入れていくことで1文字ずつ読み進めて再帰から返ってきてもその続きから処理ができるようにした。
あとはそのメソッドのcallごとに 現れた数値を演算子が出てくるたびに計算して結果を返してやれば良い。

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> u64 {
        self.inputs
            .iter()
            .map(|s| Solution::evaluate(s))
            .sum()
    }
    fn evaluate(expression: &str) -> u64 {
        let mut chars = expression.chars();
        Solution::helper(&mut chars)
    }
    fn helper(chars: &mut Chars) -> u64 {
        let (mut op, mut n) = ('+', 0);
        let mut ret = 0;
        while let Some(c) = chars.next() {
            match c {
                '0'..='9' => n = (c as u8 - b'0') as u64,
                '+' | '*' => {
                    ret = if op == '+' { ret + n } else { ret * n };
                    n = 0;
                    op = c;
                }
                '(' => n = Solution::helper(chars),
                ')' => break,
                _ => {}
            }
        }
        if op == '+' {
            ret + n
        } else {
            ret * n
        }
    }
}

part2

今度は、+が*よりも優先される、という法則で計算する、とのこと。
この場合は、都度処理していくわけにもいかないので、一旦(operator, oprand)の組み合わせをVecに突っ込むだけにしていって、最後に計算の処理をする。

#[derive(Copy, Clone)]
enum Op {
    Add,
    Mul,
}

impl Solution {
    fn helper(chars: &mut Chars, advanced: bool) -> u64 {
        let mut v: Vec<(Op, u64)> = Vec::new();
        let mut op = Op::Mul;
        while let Some(c) = chars.next() {
            match c {
                '0'..='9' => v.push((op, (c as u8 - b'0') as u64)),
                '+' => op = Op::Add,
                '*' => op = Op::Mul,
                '(' => v.push((op, Solution::helper(chars, advanced))),
                ')' => break,
                _ => {}
            }
        }
	...
    }
}

part1の場合はこのVecを先頭から見ていって順番に処理していくだけ。part2の場合はこれをstackとして処理していく。最後の要素を取り出しつつ、+ならその前のものと足し合わせてやり *なら答えに掛け合わせていく。

        if advanced {
            let mut ret = 1;
            while let Some(last) = v.pop() {
                match last.0 {
                    Op::Add => {
                        if let Some(prev) = v.last_mut() {
                            prev.1 += last.1;
                        }
                    }
                    Op::Mul => ret *= last.1,
                }
            }
            ret
        } else {
            v.iter().fold(1, |acc, x| match x.0 {
                Op::Add => acc + x.1,
                Op::Mul => acc * x.1,
            })
        }

code

use std::io::{BufRead, BufReader};
use std::str::Chars;

struct Solution {
    inputs: Vec<String>,
}

#[derive(Copy, Clone)]
enum Op {
    Add,
    Mul,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> u64 {
        self.inputs
            .iter()
            .map(|s| Solution::evaluate(s, false))
            .sum()
    }
    fn solve_2(&self) -> u64 {
        self.inputs
            .iter()
            .map(|s| Solution::evaluate(s, true))
            .sum()
    }
    fn evaluate(expression: &str, advanced: bool) -> u64 {
        let mut chars = expression.chars();
        Solution::helper(&mut chars, advanced)
    }
    fn helper(chars: &mut Chars, advanced: bool) -> u64 {
        let mut v: Vec<(Op, u64)> = Vec::new();
        let mut op = Op::Mul;
        while let Some(c) = chars.next() {
            match c {
                '0'..='9' => v.push((op, (c as u8 - b'0') as u64)),
                '+' => op = Op::Add,
                '*' => op = Op::Mul,
                '(' => v.push((op, Solution::helper(chars, advanced))),
                ')' => break,
                _ => {}
            }
        }
        if advanced {
            let mut ret = 1;
            while let Some(last) = v.pop() {
                match last.0 {
                    Op::Add => {
                        if let Some(prev) = v.last_mut() {
                            prev.1 += last.1;
                        }
                    }
                    Op::Mul => ret *= last.1,
                }
            }
            ret
        } else {
            v.iter().fold(1, |acc, x| match x.0 {
                Op::Add => acc + x.1,
                Op::Mul => acc * x.1,
            })
        }
    }
}

fn main() {
    let solution = Solution::new(
        BufReader::new(std::io::stdin().lock())
            .lines()
            .filter_map(|line| line.ok())
            .collect(),
    );
    println!("{}", solution.solve_1());
    println!("{}", solution.solve_2());
}