テンパズル(make10)の解法プログラム [その他]
自動車のナンバープレートを見ると4つの数字から四則演算で10にする遊びをついやってしまいます。この遊びはテンパズル(10パズル)若しくは make10 と呼ぶようで wikipadia にも載っています。
Twitter で下記のメッセージを見かけ面白そうなのでプログラムを作ってみました。
こういう探索系で目的は単純明快だけれどもどう実装するか色々考えさせられそうな問題は結構好きです ^^
このような処理の結果を欲しがる人はほとんど居ないと思いますが、上記のようなパターンの縮退(枝刈り)処理はそれほど時間が掛からないので長時間かかりそうな探索処理をする場合等に有効な概念ではないかと思います。
また、ソースコードが膨大に蓄積されたネットから使えそうなソースを探して動かすことよりも、このように自分で考えたロジックを組み立てて動かすことの方がプログラミングの醍醐味を(私は)感じます。
★追記 2022/10/21 {
バグ発見につき見直し中 ^^;;;;;
}
★変更 2022/10/24 {
RPNから展開した式を正規化する際に分数の表現に揺らぎがありました。このバグを修正し、下記の内容に反映しました。
}
結果から先に書くと作成したプログラムの処理が間違っていなければ上記のメッセージへの回答は1314 1170 通りで、このパターンを用いて 0000 から 9999 までの1万通り中で 10 にできるものを確認すると 8147 通り検出され上記の wikipedia の数値と一致します。
始めは括弧の配置パターンを考えてみたりしましたが括弧式と言えばスタックを使った逆ポーランド記法と言うことで下記の方針で処理してみました。
★追記 2022/10/25 {
テンパズルの回答を表示する簡単な CGI を作成してみました。順番を入れ替えない回答を表示します。縮退データを利用しているのでサーバに優しい処理になっていますw
}
★追記 2024/02/06 {
今回実施した手法では正規化する際にまだ未発見の揺らぎが残存した場合、縮退数は更に小さくなるので真の値は今回求めた縮退数以下と言えます。
一方で冒頭で紹介した Twitter メッセージの投稿者は全ての RPN 式に対して各変数を0~9にした場合の計算結果が等しい場合、同じグループに分類するという手法を使用したとのことです。この場合、変数が0~9の範囲外の時、同一グループでも計算結果が異なる可能性もあるので真の値はグルーピング数以上ということになります。
以上から、真の値は縮退数以下で、かつグルーピング数以上ということになり、結果として「縮退数=グルーピング数」だったので「今回求めた縮退数は真の値である」と言えます。
}
以上が今回実装した処理の概要になります。参考としてサイズは大きいですが縮退後の全パターンを貼っておきます。
Twitter で下記のメッセージを見かけ面白そうなのでプログラムを作ってみました。
make10がらみで、4変数の四則演算だけの式って本質的にいくつあるんだろうと思ってコードを書いて調べてみ。本質的にというのは例えばa/b/cとa/(b*c)を同一視するということ。間違ってなければ1170通りあるみたい。誰か正解を知らないかな? |
---|
こういう探索系で目的は単純明快だけれどもどう実装するか色々考えさせられそうな問題は結構好きです ^^
このような処理の結果を欲しがる人はほとんど居ないと思いますが、上記のようなパターンの縮退(枝刈り)処理はそれほど時間が掛からないので長時間かかりそうな探索処理をする場合等に有効な概念ではないかと思います。
また、ソースコードが膨大に蓄積されたネットから使えそうなソースを探して動かすことよりも、このように自分で考えたロジックを組み立てて動かすことの方がプログラミングの醍醐味を(私は)感じます。
★追記 2022/10/21 {
バグ発見につき見直し中 ^^;;;;;
}
★変更 2022/10/24 {
RPNから展開した式を正規化する際に分数の表現に揺らぎがありました。このバグを修正し、下記の内容に反映しました。
}
結果から先に書くと作成したプログラムの処理が間違っていなければ上記のメッセージへの回答は
始めは括弧の配置パターンを考えてみたりしましたが括弧式と言えばスタックを使った逆ポーランド記法と言うことで下記の方針で処理してみました。
- 逆ポーランド記法( RPN 式)での全パターンの抽出
4 つの数字(a,b,c,d)を使った四則演算(+,-,*,/)の式を網羅すればいいので数字の順列のそれぞれパターンに対して 3 つの演算子を注入していく処理をすればいいことになります。
数字の順列は単純な再起呼出しで作成できますし、それぞれの数字の順列パターンに対して先頭から数値または演算子(重複可)を並べていくように再帰呼出しすれば全パターンが作成できます。
数字を選択したらスタック数をインクリメントし、演算子を選択したらスタックをデクリメントします。演算子は全て二項演算なのでスタックに 2 個以上のデータがある場合に選択できるという条件を付けます。合計で7文字に達することがリターンの条件です。この条件で再帰呼出しすれば全てのパターン( 7680 通り)が得られます。
例:ad-c+b/
- RPN 式の括弧式変換
RPN 式を括弧に展開します。一般式と違い RPN 式は非常に扱い易いですね。
例:ad-c+b/ ⇒ ((a-d)+c)/b
- 括弧の展開
上記の括弧式をできるだけ括弧を使わない式に展開します。一般式と違い二項演算部は必ず括弧で囲まれているので両端の項の外部との結合を気にする必要がないので楽です。
下記の 3 パターンに場合分けして処理しました。w, x, y, z が変数 [a-d] で @ は演算子 [+-*/] です。式からカッコ内に括弧を含まない最も内側の純粋な括弧式を抽出して展開するという処理を除算の分母以外の括弧が無くなるまで繰り返しました。
- x @ ( y @ z )
- ( x @ y ) @ z
- ( w @ x ) @ ( y @ z )
例:((a-d)+c)/b ⇒ a/b-d/b+c/b
- 式の正規化(ソート)
冒頭に書いた Twitter のメッセージにあるように異なる数式でも本質的に同じ場合は一つにまとめるために多項式の場合は項の順番を一定の規則で並び替える必要があります。また項内に複数の変数がある場合にも項内の変数を並び替える必要があります。下記のように処理することで本質的に同一な計算式は同じ式に正規化されます。
- 項内ソート
乗算演算子を前方に置き、除算演算子は後方になるように並び替えた後、乗算群と除算群のそれぞれに対して変数の順番をソートしました。
- 項のソート
数式を '+','-' の二つの演算子で項に分離し、'-' の項を式の後方に配置し直した後、'+' 群と '-' 群のそれぞれに対して項をソートして並び替えました。
- 分数の変換 ★追記 2022/10/24
分母にマイナスの演算子を含み、分数全体がマイナス項であった場合、分母と分子に -1 を掛け、分数全体をプラスの項に変換しました。
また、分母の式に分数項があった場合、分数項の分母を分母と分子に掛け分母の式に分数が入らないようにしました。
- 項内ソート
- 正規化した式での縮退
全ての RPN 式について導出された正規化した式で同じものをグルーピングしてグループ数(=縮退数)を求めました。このグループ数が冒頭に書いた Twitter のメッセージへの回答となるはずです。
例:((a-d)+c)/b ⇒ a/b-d/b+c/b ⇒ a/b+c/b-d/b
(a-d)/(c-b) ⇒ a/(c-b)-d/(c-b) ⇒ a/(c-b)+d/(b-c)
★追記 2022/10/25 {
テンパズルの回答を表示する簡単な CGI を作成してみました。順番を入れ替えない回答を表示します。縮退データを利用しているのでサーバに優しい処理になっていますw
}
★追記 2024/02/06 {
今回実施した手法では正規化する際にまだ未発見の揺らぎが残存した場合、縮退数は更に小さくなるので真の値は今回求めた縮退数以下と言えます。
一方で冒頭で紹介した Twitter メッセージの投稿者は全ての RPN 式に対して各変数を0~9にした場合の計算結果が等しい場合、同じグループに分類するという手法を使用したとのことです。この場合、変数が0~9の範囲外の時、同一グループでも計算結果が異なる可能性もあるので真の値はグルーピング数以上ということになります。
以上から、真の値は縮退数以下で、かつグルーピング数以上ということになり、結果として「縮退数=グルーピング数」だったので「今回求めた縮退数は真の値である」と言えます。
}
以上が今回実装した処理の概要になります。参考としてサイズは大きいですが縮退後の全パターンを貼っておきます。
RPN 式の正規化後の縮退結果 |
|
コメント 0