屑俺日記

☆ お馬鹿な計算問題

適当に検索していたら、変な 四則演算の問題が 出ていた。
空欄に1から9を入れて、等式にせよ、ということらしい。
":"が 割り算の記号になることは、知らなかった。
解き方だか回答だかのページは、見ていない。

k + 13 * l / m + n + 12 * o - p - 11 + q * r / s - 10 == 66
というところか。

とりあえず解くスクリプト。
演算子の優先順位は一般的に、そして整数演算限定とする(途中で0.5を2倍する ような解も不採用とする)。
てけとーにpythonを走らせると、20種の解が出た(全部ではないと思われた)。
6分以上かかったが。

$ time python fool_9.py
3 2 1 5 4 7 8 9 6
3 2 1 5 4 7 9 8 6
5 2 1 3 4 7 8 9 6
5 2 1 3 4 7 9 8 6
5 3 1 7 2 6 8 9 4
5 3 1 7 2 6 9 8 4
5 4 1 9 2 7 3 8 6
5 4 1 9 2 7 8 3 6
5 9 3 6 2 1 7 8 4
5 9 3 6 2 1 8 7 4
6 3 1 9 2 5 7 8 4
6 3 1 9 2 5 8 7 4
6 9 3 5 2 1 7 8 4
6 9 3 5 2 1 8 7 4
7 3 1 5 2 6 8 9 4
7 3 1 5 2 6 9 8 4
9 3 1 6 2 5 7 8 4
9 3 1 6 2 5 8 7 4
9 4 1 5 2 7 3 8 6
9 4 1 5 2 7 8 3 6
 
real    6m2.076s
user    6m1.056s
sys     0m0.020s

同じ値でないことをチェックする関数で、配列から集合にぶちこむ(ここで データがuniqされる)のをやめて、 よりお馬鹿に(次のC言語同様に)書き直すと、 二倍近いスピードになりはしたが。

C言語でも同じ解になるようにしてみた。
こちらは同じ環境で4秒弱。

☆ 「すこし」インテリジェントにすると「えらく」遅くなった

前の続き。Cで余計なことを色々試す。

「場合の数」全てを列挙して一度に比較するのは流石に冗長と思えたので、 配列に入れて、配列に同じデータがないか確認するようにしてみた。
すると、同じ環境で同じ結果を出すまで2分ほどもかかるようになった。
同じデータが出たらループから抜けて、関数自体を 終わらせるようにしてみたが、それでも25-30秒くらい かかってしまうようだった。

☆ ついでに

検算するスクリプトも書いた。