tkihiraさんの問題が面白そうだったので挑戦してみた。
2023年クイズ！
— Takuo Kihira (@tkihira) December 31, 2022
上の例のように、数字の合間に四則演算（＋−×÷）や括弧を入れることで、2023 を作ってください。
- 数字の間に必ず演算子を 1 つ入れてください
- ただし 9 と 8 の間には既に ÷ が入っています
- 括弧は複数重ねて使用できます
- 10×(-9 ÷ 8) のようなマイナス記号の使用は禁止です pic.twitter.com/K0w2miMXJA
既に解説記事が出ているので解答はこちらをどうぞ。
結局自分は自力では解けなくて 他の人の解法や上記の解説記事を読んでようやくできた、のだけど… 自分なりに理解して改めてRustで実装してみた。
RPN(逆ポーランド記法)の backtracking
まずは型定義。
#[derive(Clone, Copy, PartialEq, Eq)] enum Op { Add, Sub, Mul, Div, } #[derive(Clone)] enum ExpressionElement { Operand(i32), Operator(Op), }
この ExpressionElement を stack に詰んでいって、末尾が Operator だったらさらに Operand を 2つ pop() して、演算結果を push() していくことで計算が実現できる。
常に Operand の方が多い状態でないと Operator は挿入できないので、各々の出現回数をカウントしながら条件を満たしているときだけ操作するようにする。
様々な実装が試せるように Trait を定義。
trait Rpn { fn traverse( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, ) { if i == j + 1 && self.get(i).is_none() { if self.evaluate(expr) { results.push(expr.clone()); } return; } if let Some(&n) = self.get(i) { self.backtrack(expr, (i + 1, j), results, ExpressionElement::Operand(n)); } if i > j + 1 { for op in &[Op::Add, Op::Sub, Op::Mul, Op::Div] { self.backtrack(expr, (i, j + 1), results, ExpressionElement::Operator(*op)); } } } fn evaluate(&self, expr: &[ExpressionElement]) -> bool; fn get(&self, i: usize) -> Option<&i32>; fn backtrack( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, e: ExpressionElement, ) { expr.push(e); self.traverse(expr, (i, j), results); expr.pop(); } }
self.get(i) でi番目に使う数字を呼び出す。すべて使い切っていて Operatorも適切な回数使われていたら self.evaluate(expr) で計算結果を確認し、条件に合致していた場合のみ その expr を results に格納する。
expr を push / pop して再帰的に self.traverse() を呼ぶ backtracking の部分は別の実装で上書きできるようにあえて独立のmethodで定義。
何も難しいことを考えずにこれを満たす実装を作ると、以下のようになる。
struct Fraction(i32, i32); struct DefaultSearcher { nums: Vec<i32>, target: i32, } impl DefaultSearcher { pub fn new(nums: Vec<i32>, target: i32) -> Self { Self { nums, target } } } impl Rpn for DefaultSearcher { fn evaluate(&self, expr: &[ExpressionElement]) -> bool { let mut stack = Vec::new(); for e in expr { match e { ExpressionElement::Operand(n) => stack.push(Fraction(*n, 1)), ExpressionElement::Operator(op) => { if let (Some(n0), Some(n1)) = (stack.pop(), stack.pop()) { if let Some(n) = op.apply(&n1, &n0) { stack.push(n); } else { return false; } } } } } stack .last() .map(|n| n.1 * self.target == n.0) .unwrap_or(false) } fn get(&self, i: usize) -> Option<&i32> { self.nums.get(i) } } impl Op { fn apply(&self, lhs: &Fraction, rhs: &Fraction) -> Option<Fraction> { match self { Self::Add => Some(Fraction(lhs.0 * rhs.1 + rhs.0 * lhs.1, lhs.1 * rhs.1)), Self::Sub => Some(Fraction(lhs.0 * rhs.1 - rhs.0 * lhs.1, lhs.1 * rhs.1)), Self::Mul => Some(Fraction(lhs.0 * rhs.0, lhs.1 * rhs.1)), Self::Div if rhs.0 != 0 => Some(Fraction(lhs.0 * rhs.1, lhs.1 * rhs.0)), _ => None, } } }
解説記事では浮動小数点でも十分ということでやっていたけど、自分的には整数値だけで処理したいので Fraction(i32, i32) を定義して分数で計算するようにした。約分のことはとりあえず考えなくてよくて、最終的な値の計算結果の確認は 分子が分母の 2023 倍になっているか否か、で判定できる。
各Opの適用結果を Op::apply で計算。ゼロ除算の可能性があるので返り値は Option<Fraction> に。
self.evaluate() 内で stackを用意し、exprを順に見ながら Operand だったら Fraction に変換してpushし、 Operator だったら 2つを pop して演算結果をまた格納。理論上 正しい形式のRPN式であれば最終的にはstackには1要素だけ残るはずなので、その値を確認すれば良い。
これでとりあえず、(9と8の間の割り算を無視して)計算結果が 2023 になる式の組み合わせを列挙できる。
let nums = (1..=10).rev().collect(); let mut results = Vec::new(); DefaultSearcher::new(nums, 2023).traverse(&mut Vec::new(), (0, 0), &mut results);
手元の環境で実行すると 3370 件の結果が約2分弱で列挙された。
... 10-(9-(((8*(7*6))+(5-4))*(3*(2*1)))) 10-(9-(((8*(7*6))+(5-4))*(3*(2/1)))) 10-(9-(((8*(7*6))+(5-4))*(3+(2+1)))) 10-(9-(8*(((7*(6+(5/4)))*(3+2))-1))) 10-(9-(8*((7*((6+(5/4))*(3+2)))-1))) Completed 3370 results in 111.933449708s
探索の高速化
計算結果を保持
前述の実装だと、式が完成するたびにstack用意して計算結果を確認して… というのが非常に無駄になる。解説記事によると 1,274,544,128 通り生成されるようなので、ここはもっと計算量を削りたい。
途中までの計算結果は変わらないものなので、それを保持しながら探索した方が効率的になる。
内部に別のstackを持って、 Operator を受け取った時点で演算処理結果を格納しておくようにしておく。
前述の self.evaluate() でやっていた計算を self.backtrack() の中で逐次やっておく、という感じ。
pub struct FastSearcher { nums: Vec<i32>, target: i32, stack: Vec<Fraction>, } impl FastSearcher { pub fn new(nums: Vec<i32>, target: i32) -> Self { let stack = Vec::with_capacity(nums.len()); Self { nums, target, stack, } } } impl Rpn for FastSearcher { fn evaluate(&self, _: &[ExpressionElement]) -> bool { self.stack[0].1 * self.target == self.stack[0].0 } fn get(&self, i: usize) -> Option<&i32> { self.nums.get(i) } fn backtrack( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, e: ExpressionElement, ) { match e { ExpressionElement::Operand(n) => { self.stack.push(Fraction(n, 1)); expr.push(e); self.traverse(expr, (i, j), results); expr.pop(); self.stack.pop(); } ExpressionElement::Operator(op) => { if let (Some(n0), Some(n1)) = (self.stack.pop(), self.stack.pop()) { if let Some(n) = op.apply(&n1, &n0) { self.stack.push(n); expr.push(e); self.traverse(expr, (i, j), results); expr.pop(); self.stack.pop(); } self.stack.push(n1); self.stack.push(n0); } } } } }
これによって self.evaluate() に到達した時点で計算結果は出ているので、その値だけを確認すれば良い、ということになる。また、途中でゼロ除算が生じた場合にその先の探索をしなくなるので無駄を省く効果もありそうだ。
これで、前述の 3370 件の列挙が 約30秒に短縮された。約4倍の高速化。
探索結果のキャッシュ
また、この内部stackは同じ状態を経過することも多い。例えば
10*(9-8)+...10/(9-8)+...
は 8 までの計算結果はどちらも変わらない。どちらか一方で全探索して1件も見つからなかったなら、もう片方でも1件も見つからないことが分かる。
ので、探索して条件に合致する式が見つかったか否かを返すようにし、それが false だった場合には同様の状態からの探索をスキップするように変更。
use std::collections::HashSet; type Key = (Vec<Fraction>, (usize, usize)); pub struct FastSearcher { nums: Vec<i32>, target: i32, stack: Vec<Fraction>, seen: HashSet<Key>, } impl FastSearcher { pub fn new(nums: Vec<i32>, target: i32) -> Self { let stack = Vec::with_capacity(nums.len()); Self { nums, target, stack, seen: HashSet::new(), } } } impl Rpn for FastSearcher { fn traverse( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, ) -> bool { if i == j + 1 && self.get(i).is_none() { let found = self.evaluate(expr); if found { results.push(expr.clone()); } return found; } let key = (self.stack.clone(), (i, j)); if self.seen.contains(&key) { return false; } let mut ret = false; if let Some(&n) = self.get(i) { ret |= self.backtrack(expr, (i + 1, j), results, ExpressionElement::Operand(n)); } if i > j + 1 { for op in &Op::ALL { ret |= self.backtrack(expr, (i, j + 1), results, ExpressionElement::Operator(*op)); } } if !ret { self.seen.insert(key); } ret } }
これで、約12秒くらいに短縮された。さらに2倍以上速くなった。
実際にはこの key に使っている self.stack は約分されていない計算結果なので、同じ状態を経由しているはずなのに 値が異なっているという扱いになってしまうケースがある。
gcd を使って既約分数を格納するようにしてみる。
impl FastSearcher { fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { Self::gcd(b, a % b) } } } impl Rpn for FastSearcher { ... fn backtrack( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, e: ExpressionElement, ) -> bool { let mut ret = false; match e { ExpressionElement::Operand(n) => {...} ExpressionElement::Operator(op) => { if let (Some(n0), Some(n1)) = (self.stack.pop(), self.stack.pop()) { if let Some(n) = op.apply(&n1, &n0) { let gcd = Self::gcd(n.0, n.1); self.stack.push(Fraction(n.0 / gcd, n.1 / gcd)); ... } self.stack.push(n1); self.stack.push(n0); } } } ret } }
これで、3370 件の列挙が 約7.5秒程度まで短縮された。
このキャッシュ手法は探索目標の値などによって効率が変わってくるので一概には言えないかもしれないが、少なくともこの例においては数倍の高速化が実現できた。
割り算を考慮した条件つき生成
ここまでは計算結果が 2023 になるものを全列挙することだけを考えていたが、件のパズル問題では「9と8の間には既に÷が入っています」という制約がある。
前述した 3370 件から条件に合致するものを抽出しても良いが、そもそも探索する時点で条件に合致しない式になるものを除外していくほうが効率が良い。
これは自分ではまったく思いつかなくて解説記事を読んで目から鱗だったのだけど、 「8の数字が出た後、数字と演算子の数が一致していた場合」の演算子を割り算に固定 することによって実現できる。
解説記事を参考に、専用のSearcherを実装してみる。
struct Div8Searcher { nums: Vec<i32>, target: i32, stack: Vec<Fraction>, eight_depth: i32, } impl Div8Searcher { pub fn new(nums: Vec<i32>, target: i32) -> Self { let stack = Vec::with_capacity(nums.len()); Self { nums, target, stack, eight_depth: -1, } } } impl Rpn for Div8Searcher { fn traverse( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, ) -> bool { ... if i > j + 1 { for op in &Op::ALL { if self.eight_depth == 0 && op != &Op::Div { continue; } ret |= self.backtrack(expr, (i, j + 1), results, ExpressionElement::Operator(*op)); } } ret } fn backtrack( &mut self, expr: &mut Vec<ExpressionElement>, (i, j): (usize, usize), results: &mut Vec<Vec<ExpressionElement>>, e: ExpressionElement, ) -> bool { let mut ret = false; match e { ExpressionElement::Operand(n) => { let orig = self.eight_depth; if n == 8 { self.eight_depth = 0; } else if self.eight_depth >= 0 { self.eight_depth += 1; } self.stack.push(Fraction(n, 1)); expr.push(e); ret |= self.traverse(expr, (i, j), results); expr.pop(); self.stack.pop(); self.eight_depth = orig; } ExpressionElement::Operator(op) => { if let (Some(n0), Some(n1)) = (self.stack.pop(), self.stack.pop()) { if let Some(n) = op.apply(&n1, &n0) { self.eight_depth -= 1; self.stack.push(n); expr.push(e); ret |= self.traverse(expr, (i, j), results); expr.pop(); self.stack.pop(); self.eight_depth += 1; } self.stack.push(n1); self.stack.push(n0); } } } ret } }
eight_depth の値を保持し、8 が出現したら 0 にセットして Operand か Operator かによって値を増減。値が 0 のときには次に push する Opeator が Op::Div だけに制限される。
前述したような探索結果のキャッシュも使いたいところだが、新たな状態としてこの self.eight_depth もキーに含める必要があり、その割にはそれほど効果も無さそうなのでここでは省いた。
これによって 「9と8の間には必ず/が入る」式だけが探索されるようになる。
条件に合致する 530 件が、約4秒強で列挙されるようになった。全列挙してから抽出するよりも明らかに速いことが分かる。
... (10*(9/((8-7)/((6*5)/(4/3)))))-(2/1) (10*(9/((8-7)/(6*((5/4)*3)))))-(2*1) (10*(9/((8-7)/(6*((5/4)*3)))))-(2/1) (10*(9/((8-7)/(6*(5/(4/3))))))-(2*1) (10*(9/((8-7)/(6*(5/(4/3))))))-(2/1) Completed 530 results in 4.187013041s
中置記法、正規化
ここまでで探索して収集された results は Vec<Vec<ExpressionElement>> であり、これを中置記法に書き換える操作もまたstackを使って実現していくことになる。
impl Display for Op { fn fmt(&self, f: &mut Formatter<'_>) -> Result { f.write_char(match self { Self::Add => '+', Self::Sub => '-', Self::Mul => '*', Self::Div => '/', }) } } fn solve(searcher: &mut impl Rpn) { let mut results = Vec::new(); searcher.traverse(&mut Vec::new(), (0, 0), &mut results); for result in results { let mut stack = Vec::new(); for e in &result { match e { ExpressionElement::Operand(n) => stack.push((n.to_string(), None)), ExpressionElement::Operator(op) => { if let (Some((mut s0, o0)), Some((mut s1, o1))) = (stack.pop(), stack.pop()) { if o1.is_some() { s1 = format!("({s1})"); } if o0.is_some() { s0 = format!("({s0})"); } stack.push((format!("{s1}{op}{s0}"), Some(*op))); } } } } println!("{}", stack[0].0); } }
連結していくための String と、どの Operator で得られたものか(もしくは Operand か)、を保持しながら処理していく。簡単にすべて括弧をつけてしまうのなら上述のように書ける。
不要な括弧を除去して出力する場合は、左operandの場合と右operandの場合で処理が変わる(引き算・割り算は右operandに注意する必要がある)。matches! で判定してやってみる。
...
ExpressionElement::Operator(op) => {
if let (Some((mut s0, o0)), Some((mut s1, o1))) = (stack.pop(), stack.pop()) {
if matches!((op, o1), (Op::Mul | Op::Div, Some(Op::Add | Op::Sub))) {
s1 = format!("({s1})");
}
if matches!(
(op, o0),
(Op::Sub | Op::Mul, Some(Op::Add | Op::Sub)) | (Op::Div, Some(_))
) {
s0 = format!("({s0})");
}
stack.push((format!("{s1}{op}{s0}"), Some(*op)));
}
}
これで、得られた結果を HashSet などで重複排除することで、解説記事と同様の 81 件を約4秒強で列挙することができた。
((10+(9/8+7)*6*5)*4-3)*2-1 (10*9/((8-7)/(6*5))/(4/3)-2)*1 (10*9/((8-7)/(6*5))/(4/3)-2)/1 (10*9/((8-7)/(6*5))/4*3-2)*1 (10*9/((8-7)/(6*5))/4*3-2)/1 (10*9/((8-7)/(6*5)*4)*3-2)*1 (10*9/((8-7)/(6*5)*4)*3-2)/1 (10*9/((8-7)/(6*5)*4/3)-2)*1 (10*9/((8-7)/(6*5)*4/3)-2)/1 (10*9/((8-7)/(6*5/(4/3)))-2)*1 (10*9/((8-7)/(6*5/(4/3)))-2)/1 (10*9/((8-7)/(6*5/4))*3-2)*1 (10*9/((8-7)/(6*5/4))*3-2)/1 (10*9/((8-7)/(6*5/4)/3)-2)*1 (10*9/((8-7)/(6*5/4)/3)-2)/1 (10*9/((8-7)/(6*5/4*3))-2)*1 (10*9/((8-7)/(6*5/4*3))-2)/1 (10*9/((8-7)/6)*5/(4/3)-2)*1 (10*9/((8-7)/6)*5/(4/3)-2)/1 (10*9/((8-7)/6)*5/4*3-2)*1 (10*9/((8-7)/6)*5/4*3-2)/1 (10*9/((8-7)/6/(5/(4/3)))-2)*1 (10*9/((8-7)/6/(5/(4/3)))-2)/1 (10*9/((8-7)/6/(5/4))*3-2)*1 (10*9/((8-7)/6/(5/4))*3-2)/1 (10*9/((8-7)/6/(5/4)/3)-2)*1 (10*9/((8-7)/6/(5/4)/3)-2)/1 (10*9/((8-7)/6/(5/4*3))-2)*1 (10*9/((8-7)/6/(5/4*3))-2)/1 (10*9/((8-7)/6/5)/(4/3)-2)*1 (10*9/((8-7)/6/5)/(4/3)-2)/1 (10*9/((8-7)/6/5)/4*3-2)*1 (10*9/((8-7)/6/5)/4*3-2)/1 (10*9/((8-7)/6/5*4)*3-2)*1 (10*9/((8-7)/6/5*4)*3-2)/1 (10*9/((8-7)/6/5*4/3)-2)*1 (10*9/((8-7)/6/5*4/3)-2)/1 (10*9/(8-7)*6*5/(4/3)-2)*1 (10*9/(8-7)*6*5/(4/3)-2)/1 (10*9/(8-7)*6*5/4*3-2)*1 (10*9/(8-7)*6*5/4*3-2)/1 10*9/((8-7)/(6*5))/(4/3)-2*1 10*9/((8-7)/(6*5))/(4/3)-2/1 10*9/((8-7)/(6*5))/4*3-2*1 10*9/((8-7)/(6*5))/4*3-2/1 10*9/((8-7)/(6*5)*4)*3-2*1 10*9/((8-7)/(6*5)*4)*3-2/1 10*9/((8-7)/(6*5)*4/3)-2*1 10*9/((8-7)/(6*5)*4/3)-2/1 10*9/((8-7)/(6*5/(4/3)))-2*1 10*9/((8-7)/(6*5/(4/3)))-2/1 10*9/((8-7)/(6*5/4))*3-2*1 10*9/((8-7)/(6*5/4))*3-2/1 10*9/((8-7)/(6*5/4)/3)-2*1 10*9/((8-7)/(6*5/4)/3)-2/1 10*9/((8-7)/(6*5/4*3))-2*1 10*9/((8-7)/(6*5/4*3))-2/1 10*9/((8-7)/6)*5/(4/3)-2*1 10*9/((8-7)/6)*5/(4/3)-2/1 10*9/((8-7)/6)*5/4*3-2*1 10*9/((8-7)/6)*5/4*3-2/1 10*9/((8-7)/6/(5/(4/3)))-2*1 10*9/((8-7)/6/(5/(4/3)))-2/1 10*9/((8-7)/6/(5/4))*3-2*1 10*9/((8-7)/6/(5/4))*3-2/1 10*9/((8-7)/6/(5/4)/3)-2*1 10*9/((8-7)/6/(5/4)/3)-2/1 10*9/((8-7)/6/(5/4*3))-2*1 10*9/((8-7)/6/(5/4*3))-2/1 10*9/((8-7)/6/5)/(4/3)-2*1 10*9/((8-7)/6/5)/(4/3)-2/1 10*9/((8-7)/6/5)/4*3-2*1 10*9/((8-7)/6/5)/4*3-2/1 10*9/((8-7)/6/5*4)*3-2*1 10*9/((8-7)/6/5*4)*3-2/1 10*9/((8-7)/6/5*4/3)-2*1 10*9/((8-7)/6/5*4/3)-2/1 10*9/(8-7)*6*5/(4/3)-2*1 10*9/(8-7)*6*5/(4/3)-2/1 10*9/(8-7)*6*5/4*3-2*1 10*9/(8-7)*6*5/4*3-2/1 Completed 81 results in 4.229359166s
CLIアプリケーション化
ここまで幾つかの実装ができたので、折角なので引数でパラメータを変えながら全列挙できる CLI アプリケーションを作成してみた。
$ ./puzzle2023 --help Solvers for https://twitter.com/tkihira/status/1609313732034965506 Usage: puzzle2023 [OPTIONS] Options: -t, --target <TARGET> [default: 2023] -m, --max-num <MAX_NUM> [default: 10] -r, --rev <REV> [default: true] [possible values: true, false] -s, --searcher <SEARCHER> [default: fast] [possible values: default, fast, div8] -n, --normalize -v, --verbose -h, --help Print help information -V, --version Print version information
全パターン列挙
$ ./puzzle2023 -v ... 10-(9-(((8*(7*6))+(5-4))*(3*(2*1)))) 10-(9-(((8*(7*6))+(5-4))*(3*(2/1)))) 10-(9-(((8*(7*6))+(5-4))*(3+(2+1)))) 10-(9-(8*(((7*(6+(5/4)))*(3+2))-1))) 10-(9-(8*((7*((6+(5/4))*(3+2)))-1))) Completed 3370 results in 7.338064208s
9と8の間の割り算に限定
$ ./puzzle2023 -v --searcher div8 ... (10*(9/((8-7)/(6*((5/4)*3)))))-(2/1) (10*(9/((8-7)/(6*(5/(4/3))))))-(2*1) (10*(9/((8-7)/(6*(5/(4/3))))))-(2/1) Completed 530 results in 4.219031208s
正規化
$ ./puzzle2023 -v --searcher div8 --normalize ... 10*9/(8-7)*6*5/(4/3)-2/1 10*9/(8-7)*6*5/4*3-2*1 10*9/(8-7)*6*5/4*3-2/1 Completed 81 results in 4.239637041s
計算結果の確認
$ ./puzzle2023 --searcher div8 --normalize | python3 -c 'for s in open(0): print(f"{eval(s):.1f}")' | sort | uniq -c
81 2023.0
使うのを 1 から 8 の昇順にして 2024 を作るようにしてみる
$ ./puzzle2023 -m8 -rfalse -t2024 -nv (((1+2)*3*4+5)*6+7)*8 (1*2*(3+4*5*6)+7)*8 (1+(2+3*4)*(5+6+7))*8 (1+(2+3-(4-5))*6*7)*8 (1+(2+3-4+5)*6*7)*8 (1+2*(3+4)*(5+6+7))*8 (1+2*(3+4+5+6)*7)*8 (1+2*3+4)*(5*6-7)*8 (1+2/(3/((4+5)*6))*7)*8 (1+2/(3/((4+5)*6)/7))*8 (1+2/(3/((4+5)*6*7)))*8 (1+2/(3/(4+5))*6*7)*8 (1+2/(3/(4+5)/(6*7)))*8 (1+2/(3/(4+5)/6)*7)*8 (1+2/(3/(4+5)/6/7))*8 (1+2/3*(4+5)*6*7)*8 (1-(2-3*4))*(5*6-7)*8 (1-2*(3*4-5*6)*7)*8 (1-2*3*(4-5)*6*7)*8 (1-2*3/((4-5)/(6*7)))*8 (1-2*3/((4-5)/6)*7)*8 (1-2*3/((4-5)/6/7))*8 (1-2*3/(4-5)*6*7)*8 (1-2+3*4)*(5*6-7)*8 1*(2*(3+4*5*6)+7)*8 Completed 25 results in 131.605458ms
「8の前を割り算に限定」にしているのも、コマンドラインオプションで違う値で指定できるようにしたかったけど、複雑になりすぎる感じがしたのでそれは断念…
改善？
tkihiraさんの最適化ではstackを push / pop するのではなく固定長配列を用意して見るべきindexだけをズラしていく、といった工夫をしていた。真似して実装してみたが本実装においてはそこはあまり効果なさそうだった。
あとはこうして再帰的に探索した結果を一度 results という Vec に格納してしまっているのが実は非効率なのでは、と思ったが… Iterator として使いたかったが そうするためには探索の途中の状態を保持しておいて next() が呼ばれるたびに続きを探索していく、という処理にする必要があり、そのあたりの実装がうまくできなかった。何か良い方法あるのだろうか…
