例のベトナムの算数問題をPython3に解いてもらう

こんばんは。

www.gizmodo.jp

こんなのあったので、練習がてらPython3に解いてもらうことにしました。自分で解くのめんどくさいですもんね―。

効率の面は放っておいて、とりあえず組み合わせ全部出して計算してみます。

import itertools

num_combination_list = list(itertools.permutations(range(1, 10)))

for c in num_combination_list:
    if c[0] + 13 * c[1] / c[2] + c[3] + 12 * c[4] - c[5] - 11 + c[6] * c[7] / c[8] - 10 ==66:
        print("{0} + 13 * {1} / {2} + {3} + 12 * {4} - {5} - 11 + {6} * {7} / {8} - 10 =66"
              .format(c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8]))
        break

我ながら紛うことなき糞コード（ここ俳句）だと思うんですが、出力結果はこんな感じ。

1 + 13 * 2 / 6 + 4 + 12 * 7 - 8 - 11 + 3 * 5 / 9 - 10 = 66

13 * 2 / 6の時点で少数になっていますが、実際計算してみると確かに66でした。わーい。
元々の問題では途中で少数になっていいかどうか書いてないので、これが正解なのかどうか分かりませんが、数式としては正しいみたいです。

せっかくなので、元ページに載っていたように、わり算の部分が割り切れるかどうかも判定して、途中で少数での計算が出ないようにしてみます。
更にコードを汚くするとこんな感じ。

import itertools

num_combination_list = list(itertools.permutations(range(1, 10)))

for c in num_combination_list:
    if c[1] % c[2] != 0:
        continue

    if c[6] * c[7] % c[8] != 0:
        continue

    if c[0] + 13 * c[1] / c[2] + c[3] + 12 * c[4] - c[5] - 11 + c[6] * c[7] / c[8] - 10 == 66:
        print("{0} + 13 * {1} / {2} + {3} + 12 * {4} - {5} - 11 + {6} * {7} / {8} - 10 = 66"
              .format(c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8]))
        break

にしても汚いなぁ。出力はこんなかんじでした。

3 + 13 * 2 / 1 + 5 + 12 * 4 - 7 - 11 + 8 * 9 / 6 - 10 = 66

見るからに割りきれております。よろしい。

今回はやらないんですけど、この問題、効率的に計算するためにはどうすればいいんでしょうね。今のところバカの一つ覚え的に全探索しかしてないんですが、多分途中までの計算結果を元にして計算すれば、早くはなるんだろうなぁ。