[Day 7: Bridge Repair](https://adventofcode.com/2024/day/7)
数値演算で指定した値を作れるか否かの判定。
色んなやり方や、計算を速くするための工夫が出てくる
## 例
```
190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20
```
各行で`:`の左がテスト値で、 右の数値列に **`add`** `(+)` と **`multiply`** `(*)` の2種類の演算子を適用することでこの値を作れるか判定し、可能なもののテスト値の合計を求める、という問題。ただし演算子の優先順位は無く、常に左から右に評価される。
この例では `190 (= 10 * 19)`, `3267 (= 81 + 40 * 27)`, `292 (= 11 + 6 * 16 + 20)` の3つが可能であり、合計した **`3749`** が解になる。
part2ではさらに **`concatenation`** `(||)` の演算子が追加され、 `12 || 345` が `12345` になるように文字列として連結する演算が取り入れられる。
上の例ではpart1の3つの他に `156 (= 15 || 6)`、`7290 (= 6 * 8 || 6 * 15)`, `192 (= 17 || 8 + 14)` の3つが加えられ、 **`11387`** となる。
## 方針
基本的には総当たりで、すべての演算子の組み合わせを実際に計算してみてテスト値に一致するものがあるかどうかを調べていくことになる。配列のサイズは高々13個程度なので $2^{13}$ = 8,192, part2でも $3^{13}$ = 1,594,323 程度なので可能な範囲ではあるはず。ただし値は大きくなるので64bit整数は必要になる。
あとは枝刈りなどで高速化を考える。DFSで再帰的に求めていって最初に1つでも可能なものが見つかればその時点で`True`と判定する、など。必ず値が増加する演算なので、途中の結果がテスト値を超えていたら即座に`False`を返す、なども有効。
あまり効果は無いかもしれないが途中で同じ値に合流する組み合わせで重複して計算する必要ないようメモ化する、というのもあるかもしれない。
また、数列を逆から見ていくことで `*`演算子によってテスト値が作れるか否かを割り算で判定できるので、その時点で不可能なものは枝刈りできる、といった考え方もあるようだ。
## 実装
### Rust
`CalibrationEquation`構造体を用意し、それ自体にテスト値を作れるか否かの判定処理を持たせた。
DFSで末尾まで計算したらテスト値になるか否かを判定して返す。 `||` の演算は一度文字列にして連結するといったやり方もあるが、 `u64::ilog10()` で桁数を取得することで数値演算だけで計算することも可能。
```rust
struct CalibrationEquation {
test_value: u64,
numbers: Vec<u64>,
}
impl CalibrationEquation {
fn calibration_result(&self, third_operator: bool) -> Option<u64> {
if self.is_possible(self.numbers[0], &self.numbers[1..], third_operator) {
Some(self.test_value)
} else {
None
}
}
fn is_possible(&self, current: u64, numbers: &[u64], third_operator: bool) -> bool {
match numbers {
[] => current == self.test_value,
[n, rest @ ..] => {
(third_operator
&& self.is_possible(
current * 10_u64.pow(n.ilog10() + 1) + n,
rest,
third_operator,
))
|| self.is_possible(current + n, rest, third_operator)
|| self.is_possible(current * n, rest, third_operator)
}
}
}
}
impl FromStr for CalibrationEquation {
type Err = Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
s.split_once(": ")
.ok_or(Error::InvalidLine)
.and_then(|(test_value, numbers)| {
Ok(Self {
test_value: test_value.parse()?,
numbers: numbers
.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<_, _>>()?,
})
})
}
}
struct Solution {
calibration_equations: Vec<CalibrationEquation>,
}
impl Solution {
fn new<R>(r: R) -> Result<Self, Error>
where
R: Read,
{
Ok(Self {
calibration_equations: BufReader::new(r)
.lines()
.map(|line| line?.parse())
.collect::<Result<_, _>>()?,
})
}
fn part1(&self) -> u64 {
self.calibration_equations
.iter()
.filter_map(|eq| eq.calibration_result(false))
.sum()
}
fn part2(&self) -> u64 {
self.calibration_equations
.iter()
.filter_map(|eq| eq.calibration_result(true))
.sum()
}
}
```