2015-04-22

　今更感はありますが、Google アナリティクスで10 Puzzleの記事が上位の方に来ていたので、0000〜9999まで、すべての解を求めるPythonのプログラムの続きを書いてみました。(^_^;
　辞書式順序は壊してしまいますが、set()を使って同じものを含む順列にして、発見した解の記録用の変数をリストにしてみました。1.5倍以上速くなりましたが、同じものを含む順列にした効果です。また、括弧をはずすときにも、重複してしまう場合があるようなので、発見した解の重複チェックは必要なようです。
P.S.
　数値計算誤差のために漏れがあるようなので、「if eval(sExpr)==10.0:」から、「if round(eval(sExpr),10)==10.0:」等に修正しました。(^_^;

● 10PuzzleAll2.py

# coding: UTF-8
# 10PuzzleAll2.py

import itertools
from time import time

def delBracket(s):
    t = round(eval(s),10)
    r = s[:]
    iLen = len(r)

    for i in range(0,iLen):
        if r[i]!='(': continue
        c = 0
        for j in range(i+1,iLen):
            if   r[j]=='(': c+=1
            elif r[j]==')': c-=1
            if c>=0: continue
            r = r[:i]+' '+r[i+1:j]+' '+r[j+1:]      # ()を外す
            if round(eval(r),10)!=t:
                r = r[:i]+'('+r[i+1:j]+')'+r[j+1:]  # 駄目なら戻す
            break
    return r.replace(' ','')

def main():
    tm=time()  # Timer Start

    NUM = '0123456789'
    OPR = '+-*/'
    BRACKET = [ "%s.0%s(%s.0%s(%s.0%s%s.0))",   # 外側の（）を外してみた
                "%s.0%s((%s.0%s%s.0)%s%s.0)",
                "(%s.0%s%s.0)%s(%s.0%s%s.0)",
                "(%s.0%s(%s.0%s%s.0))%s%s.0",
                "((%s.0%s%s.0)%s%s.0)%s%s.0"]
    for m in itertools.product(NUM,repeat=4):           # m loop
        if not(m[0]<=m[1]<=m[2]<=m[3]) : continue
        print("<<--- ","".join(m)," --->>")
        lAns = []    # 発見した解の記録用
        for o in itertools.product(OPR,repeat=3):       # o loop
            for n in set(itertools.permutations(m)):    # n loop 同じものを含む順列
                for b in BRACKET:                       # b loop
                    sExpr = b % (n[0],o[0],n[1],o[1],n[2],o[2],n[3])
                    try:
                        if round(eval(sExpr),10)==10.0:
                            sExpr = delBracket(sExpr).replace('.0', '')
                            if not sExpr in lAns:       # 既出でなければ表示
                                print(sExpr+'=10')
                                lAns.append(sExpr)      # 発見した解を記録
                    except:
                        continue

    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

<<---  0000  --->>
<<---  0001  --->>
<<---  0002  --->>

…(省略)…

<<---  8999  --->>
8+(9+9)/9=10
(9+9)/9+8=10
<<---  9999  --->>
(9+9*9)/9=10
(9*9+9)/9=10
Runtime : 136.860 [sec]

※参考URL
●同じ物を含む順列 - メモ
●配列操作の比較表: Ruby, Python, JavaScript, Perl, C++

●10 Puzzleを解くプログラムをJavaで作ってみた。
●10 Puzzleを解くプログラムをPythonで作ってみた。
●10 Puzzleを解くプログラムをPythonで作ってみた。 (2)

パーフェクトPython (PERFECT SERIES 5)

Amazon

rscのブログ

10 Puzzleを解くプログラムをPythonで作ってみた。 (3)