数式の全探索

しょうきさんの #数式めぐあーと に触発されてめぐさんの好きな数字を使った四則演算で数字を表す数式を探索するプログラムを書きました
C++11で実装しています。リンク先のreplのサイトでrunを押すとプログラムが走りますhttps://t.co/nIDVRAzDZuhttps://t.co/HvvcwK8CNk https://t.co/LIv6WThqep

— ぬるぬし (@00nuushi) 2020年6月1日

これの話。要はmake_tenパズル。make_tenパズルの全探索とかきっとどこかにアルゴリズム転がってるだろうと思ったけど探してみると意外と見つからなかったし意外と難しかった。
一部（特に括弧のあたり）整理されてないけど動くのでそのままにしてある。

やりたいこと

• 1,2,7,17,21,32の加減乗除でNを作る数式を生成する（順不同、括弧も使用可。階乗や累乗はなし）
• なるべく*1, /1を使わない

考えたこと

• まず数字の位置、演算子、括弧を別々に全探索して組み合わせる
• 不要な括弧を生成する式は消す
• もう既に計算した式と同値の式も消す
• *1, /1を使うか使わないかは別にフラグを立てる

実装

github.com

なんかちゃんと文章にするのが急にめんどくさくなったので気が向いたらまとめる。
数式の全探索は上に書いた方針でやって文字列として数式を作り、文字列の数式を計算する電卓を実装した。
（）内に＋かーがなかったり、（）の前後がどちらも×、÷でない数式を消している。
あとn番目の数の手前の演算子が＋か×（前後が可換）で1~n-1番目の数がn番目の数より大きい場合、既に計算した数式と同値になるので消している（数字の順列は昇順に探索している）。もうちょっと消せるはずだけどここまでで十分速くなったので止めた。
正直電卓の実装が一番大変だった。