Rainbow U

(1)は0227の記述が抜けてますね

4つの数字の四則演算(+,-,*,/)と括弧を使って10を作る
例：0,0,2,5:○→0+0+2*5

1. 与えられた4つの数字と四則演算、括弧を使った場合の全パターンの式をすべて文字列として作成する
2. evalに1番の文字列たちを放り込んで評価し、10になるやつを出力
3. 再帰の分岐が多くて計算量が多そう(な雰囲気)だったのでデコレータを用いてメモ化再帰にした

@chokudaiが以前おしえてくれた方法を愚直に実践した

1. グラフにして、適当な方法で探索すればいいだけだよこの情弱どもが
2. 全探索なら深さ優先探索が楽だよ童貞
3. 深さ優先探索は計算量が爆発しがちだから、メモ化再帰とか動的計画法使えよベジータ

まず、evalを知っていたから#1、全パターンの式を文字列で作成することを考えた。
そして、教えに従い#1、グラフを考えた。括弧、四則演算、与えられた数字が分岐しているグラフを想像した。
それぞれの分岐には条件がある。これを再帰関数#1で思うままに書いた。
思ったより分岐の数が多かったので、メモ化#1して高速化した(別にデコレータ使わなくてもいいけど、デコレータ#1使ったほうがpythonistaっぽくてかっこいいからデコレータ使った)。
細かいところで言うと、除算時のZeroDivisionのエラーに対する例外処理は知識(常識)#1としてもっていた。

#1サピアウォーフの仮説が大事なことがよくわかる http://goo.gl/pFcu8
#かきなぐりなので変数名もろもろかなりの勢いで適当です。

args = ['0227','1269','6699','6889','1337']
calc = '+-*/'

def memorize(f):#メモ化のデコレータ用関数
    cache = {}
    def helper(answer,string):
        key = answer + 'and' + string
        if key not in cache :
            cache[key] = f(answer,string)
        return cache[key]
    return helper

@memorize#デコレータつけた
def dfs(answer,string):
    if len(string) == 0:
        while answer.count('(') > answer.count(')'):
            answer = answer + ')'
        try:
            if eval(answer) == 10.0:
                stock.append(answer)
        except ZeroDivisionError:
            pass
    else:
        for i,x in enumerate(string):
            length = len(answer)
            last = answer[length-1:length]
            if last == ')':
                for j in calc:
                    dfs(answer+j,string)
            elif last == '0':
                if answer.count('(') > answer.count(')'):
                    dfs(answer+')',string)
                for j in calc:
                    dfs(answer+j,string)
            elif last in calc: 
                temp = list(string)
                del temp[i]
                temp = ''.join(temp)
                dfs(answer+x+'.0',temp)
                dfs(answer+'(',string)
            elif last == '(':
                temp = list(string)
                del temp[i]
                temp = ''.join(temp)
                dfs(answer+x+'.0',temp)



for ls in args:
    stock = []
    dfs('(',ls)
    print ls 
    print list(set(stock))

0227
['(2.0)*(0.0+(7.0)-2.0)', '(7.0-2.0)*(0.0+(2.0))', '(7.0+(0.0)-2.0)*2.0', '(2.0*(7.0-(2.0)-0.0))', '(7.0-2.0)*(2.0-(0.0))', '(7.0-2.0)*(2.0)+(0.0)', '(2.0)*(7.0+(0.0-(2.0)))', '(2.0)*(7.0-2.0)+(0.0)', '(2.0)*(7.0-2.0-0.0)', '(0.0)-(2.0-7.0)*(2.0)', '(7.0-(2.0)+0.0)*(2.0)', '(2.0-7.0)*(0.0-2.0)', '(2.0*(7.0-(2.0-0.0)))', '(0.0)+(2.0)*(7.0-(2.0))', '(2.0)*(7.0-(2.0-(0.0)))', '(0.0-2.0+7.0)*2.0', '(2.0*(7.0-(2.0-(0.0))))', '(2.0)*(7.0-(2.0)+(0.0))', '(2.0*(0.0+(7.0)-2.0))', '(7.0-2.0)*(2.0)-(0.0)', '(0.0)-(2.0*(2.0-(7.0)))', '(0.0)+(2.0)*(7.0-2.0)', '(0.0+(7.0-2.0)*(2.0))', '(2.0*(7.0-2.0-0.0))', '(2.0)*(0.0-(2.0-7.0))', '(7.0-2.0)*(2.0)-0.0', '(0.0-(2.0-7.0)*(2.0))', '(2.0-7.0)*(0.0-(2.0))', '(7.0-2.0)*2.0-0.0', '(2.0)*(7.0-(0.0)-2.0)', '(2.0*(0.0+7.0-2.0))', '(2.0)*(7.0+0.0-(2.0))', '(7.0-2.0)*(0.0+2.0)', '(0.0-2.0)*(2.0-7.0)', '(7.0-(0.0)-2.0)*2.0', '(2.0*(7.0-(2.0)-(0.0)))', '(0.0+(2.0)*(7.0-(2.0)))', '(0.0)-(2.0)*(2.0-(7.0))', '(7.0-(2.0)+0.0)*2.0', '(0.0)+(2.0*(7.0-2.0))', '(0.0)-(2.0-7.0)*2.0', '(0.0+2.0)*(7.0-(2.0))', '(0.0)+(2.0*(7.0-(2.0)))', '(7.0-(2.0)-0.0)*2.0', '(2.0*(0.0-(2.0-7.0)))', '(2.0*(7.0-(2.0)+(0.0)))', '(7.0+(0.0)-2.0)*(2.0)', '(2.0*(7.0-0.0-2.0))', '(0.0)+(7.0-2.0)*2.0', '(2.0*(0.0+(7.0)-(2.0)))', '(0.0+(7.0)-2.0)*(2.0)', '(2.0)*(0.0+7.0-(2.0))', '(7.0-2.0)*(2.0+0.0)', '(7.0-2.0+0.0)*(2.0)', '(2.0*(0.0-2.0+(7.0)))', '(2.0)*(7.0-2.0-(0.0))', '(2.0)*(7.0+(0.0)-(2.0))', '(7.0-(0.0)-2.0)*(2.0)', '(7.0+0.0-2.0)*(2.0)', '(0.0)+(7.0-2.0)*(2.0)', '(0.0-(2.0)*(2.0-7.0))', '(2.0-0.0)*(7.0-2.0)', '(2.0)*(0.0+(7.0)-(2.0))', '(2.0*(0.0-(2.0-(7.0))))', '(0.0+7.0-2.0)*(2.0)', '(2.0+0.0)*(7.0-(2.0))', '(7.0-2.0)*(2.0)+0.0', '(2.0)*(7.0-(2.0+(0.0)))', '(7.0-2.0-0.0)*(2.0)', '(2.0*(7.0-2.0+(0.0)))', '(2.0*(0.0+7.0-(2.0)))', '(2.0)*(7.0-(2.0)-(0.0))', '(2.0*(7.0-2.0)+(0.0))', '(0.0-2.0*(2.0-7.0))', '(2.0*(7.0-2.0-(0.0)))', '(0.0-(2.0*(2.0-7.0)))', '(2.0)*(0.0+7.0-2.0)', '(0.0)-(2.0)*(2.0-7.0)', '(7.0-2.0)*2.0+0.0', '(2.0*(7.0-(2.0+0.0)))', '(2.0)*(7.0-2.0)-(0.0)', '(7.0-0.0-2.0)*2.0', '(0.0+2.0*(7.0-2.0))', '(2.0*(7.0-(2.0)+0.0))', '(2.0*(7.0+(0.0)-(2.0)))', '(2.0*(7.0+(0.0-(2.0))))', '(2.0)*(7.0-0.0-2.0)', '(7.0-2.0)*2.0-(0.0)', '(0.0+(2.0*(7.0-2.0)))', '(0.0+(7.0)-2.0)*2.0', '(2.0*(0.0-(2.0)+(7.0)))', '(2.0)*(0.0-2.0+7.0)', '(0.0-(2.0)+7.0)*(2.0)', '(7.0-0.0-2.0)*(2.0)', '(2.0)*(7.0-(2.0)-0.0)', '(0.0-(2.0-7.0)*2.0)', '(2.0)*(7.0+(0.0-2.0))', '(2.0)*(7.0-(0.0)-(2.0))', '(2.0)*(7.0-(2.0+0.0))', '(0.0-2.0+7.0)*(2.0)', '(0.0-(2.0)*(2.0-(7.0)))', '(2.0)*(7.0-(0.0+2.0))', '(2.0)*(7.0-(2.0)+0.0)', '(0.0)-2.0*(2.0-(7.0))', '(2.0*(0.0-(2.0)+7.0))', '(0.0+7.0-2.0)*2.0', '(2.0)*(7.0+(0.0)-2.0)', '(2.0*(7.0-2.0)-0.0)', '(0.0-2.0)*(2.0-(7.0))', '(2.0)*(0.0-(2.0)+(7.0))', '(7.0+0.0-2.0)*2.0', '(2.0)*(7.0-2.0)-0.0', '(0.0+2.0*(7.0-(2.0)))', '(0.0+(7.0-2.0)*2.0)', '(2.0)*(0.0-(2.0)+7.0)', '(0.0+2.0)*(7.0-2.0)', '(2.0*(0.0+(7.0-2.0)))', '(2.0*(7.0-2.0+0.0))', '(2.0)*(7.0-2.0+(0.0))', '(2.0*(7.0-(0.0+(2.0))))', '(0.0+(2.0)*(7.0-2.0))', '(2.0*(7.0-(0.0)-(2.0)))', '(0.0-2.0*(2.0-(7.0)))', '(2.0)*(0.0-2.0+(7.0))', '(2.0*(7.0-(0.0+2.0)))', '(2.0)*(0.0+(7.0-(2.0)))', '(2.0)*(7.0-(0.0+(2.0)))', '(2.0*(7.0+(0.0)-2.0))', '(2.0*(7.0-(0.0)-2.0))', '(7.0-2.0)*2.0+(0.0)', '(2.0*(7.0+0.0-(2.0)))', '(2.0*(0.0-2.0+7.0))', '(2.0*(0.0+(7.0-(2.0))))', '(2.0)*(7.0-(2.0-0.0))', '(7.0-2.0+0.0)*2.0', '(2.0*(7.0-(2.0+(0.0))))', '(2.0)*(7.0-2.0)+0.0', '(2.0-0.0)*(7.0-(2.0))', '(2.0)*(7.0-2.0+0.0)', '(0.0-(2.0*(2.0-(7.0))))', '(2.0)*(0.0-(2.0-(7.0)))', '(0.0+(2.0*(7.0-(2.0))))', '(2.0*(7.0-2.0)+0.0)', '(0.0)+2.0*(7.0-(2.0))', '(2.0)*(7.0+0.0-2.0)', '(2.0*(7.0+(0.0-2.0)))', '(0.0)-(2.0*(2.0-7.0))', '(2.0*(7.0-2.0)-(0.0))', '(0.0)+2.0*(7.0-2.0)', '(2.0)*(7.0-0.0-(2.0))', '(2.0*(7.0-0.0-(2.0)))', '(7.0-2.0)*(2.0-0.0)', '(7.0-(2.0)-0.0)*(2.0)', '(0.0)-2.0*(2.0-7.0)', '(2.0)*(0.0+(7.0-2.0))', '(2.0+0.0)*(7.0-2.0)', '(7.0-2.0-0.0)*2.0', '(0.0-(2.0)+7.0)*2.0', '(2.0*(7.0+0.0-2.0))', '(7.0-2.0)*(2.0+(0.0))']
1269
['(2.0)*(9.0-1.0)-(6.0)', '(6.0+(9.0-1.0)/(2.0))', '(2.0*(9.0-1.0)-(6.0))', '(6.0+(9.0-1.0)/2.0)', '(9.0-1.0)/(2.0)+(6.0)', '(6.0-(1.0-9.0)/2.0)', '(2.0*(9.0-1.0)-6.0)', '(6.0)-(1.0-9.0)/2.0', '(6.0)+(9.0-1.0)/(2.0)', '(9.0-1.0)/(2.0)+6.0', '(6.0-(1.0-9.0)/(2.0))', '(9.0-1.0)/2.0+(6.0)', '(9.0-1.0)*2.0-(6.0)', '(9.0-1.0)*(2.0)-6.0', '(9.0-1.0)/2.0+6.0', '(9.0-1.0)*2.0-6.0', '(6.0)+(9.0-1.0)/2.0', '(6.0)-(1.0-9.0)/(2.0)', '(9.0-1.0)*(2.0)-(6.0)', '(2.0)*(9.0-1.0)-6.0']
6699
['(6.0/9.0)*(9.0+(6.0))', '(6.0/(9.0)*(9.0+6.0))', '(6.0/(9.0/(6.0+(9.0))))', '(6.0)/(9.0)*(9.0+6.0)', '(6.0)*(9.0+6.0)/9.0', '(6.0*(6.0+9.0)/9.0)', '(6.0)/9.0*(6.0+9.0)', '(6.0)/(9.0)*(9.0+(6.0))', '(9.0+6.0)*6.0/9.0', '(9.0+6.0)*6.0/(9.0)', '(6.0)/9.0*(9.0+6.0)', '(6.0)/(9.0/(6.0+9.0))', '(6.0)/(9.0/(9.0+(6.0)))', '(9.0+6.0)/9.0*6.0', '(6.0/9.0)*(9.0+6.0)', '(9.0+6.0)*(6.0)/(9.0)', '(9.0+6.0)*(6.0/9.0)', '(6.0+9.0)/(9.0)*6.0', '(6.0/(9.0/(9.0+6.0)))', '(6.0)/(9.0)*(6.0+9.0)', '(6.0+9.0)*(6.0/(9.0))', '(6.0/9.0*(9.0+6.0))', '(6.0/(9.0/(9.0+(6.0))))', '(6.0/9.0*(6.0+9.0))', '(6.0)/(9.0/(6.0+(9.0)))', '(6.0/9.0*(9.0+(6.0)))', '(6.0/9.0)*(6.0+9.0)', '(6.0+9.0)*(6.0)/(9.0)', '(6.0+9.0)*6.0/9.0', '(9.0+6.0)/(9.0)*(6.0)', '(6.0)/(9.0)*(6.0+(9.0))', '(6.0/(9.0)*(6.0+9.0))', '(6.0+9.0)/(9.0)*(6.0)', '(9.0+6.0)*(6.0)/9.0', '(9.0+6.0)/9.0*(6.0)', '(6.0+9.0)/(9.0/(6.0))', '(6.0+9.0)*(6.0)/9.0', '(6.0)*(6.0+9.0)/9.0', '(6.0)*(6.0+9.0)/(9.0)', '(6.0)/9.0*(6.0+(9.0))', '(6.0)/(9.0/(9.0+6.0))', '(6.0)/9.0*(9.0+(6.0))', '(6.0/(9.0)*(6.0+(9.0)))', '(6.0+9.0)*6.0/(9.0)', '(6.0/(9.0/(6.0+9.0)))', '(6.0+9.0)/9.0*6.0', '(6.0+9.0)/9.0*(6.0)', '(9.0+6.0)*(6.0/(9.0))', '(6.0+9.0)*(6.0/9.0)', '(9.0+6.0)/(9.0/6.0)', '(6.0/(9.0)*(9.0+(6.0)))', '(6.0*(9.0+6.0)/9.0)', '(6.0*(6.0+9.0)/(9.0))', '(6.0/9.0)*(6.0+(9.0))', '(9.0+6.0)/(9.0)*6.0', '(6.0*(9.0+6.0)/(9.0))', '(6.0)*(9.0+6.0)/(9.0)', '(6.0+9.0)/(9.0/6.0)', '(6.0/9.0*(6.0+(9.0)))', '(9.0+6.0)/(9.0/(6.0))']
6889
['(8.0*8.0)-9.0*6.0', '(8.0*8.0-6.0*(9.0))', '(8.0*8.0)-(6.0)*(9.0)', '(8.0*8.0)-6.0*9.0', '(8.0*8.0)-(9.0)*6.0', '(8.0*8.0)-(6.0)*9.0', '(8.0)*(8.0)-9.0*(6.0)', '(9.0*(8.0-6.0)-(8.0))', '(8.0)*(8.0)-(9.0*(6.0))', '(8.0*8.0-(9.0*(6.0)))', '(8.0*8.0)-(6.0*9.0)', '(8.0*(8.0)-(9.0)*6.0)', '(8.0*(8.0)-(6.0)*9.0)', '(8.0*8.0)-(9.0*6.0)', '(8.0)*8.0-(6.0*(9.0))', '(8.0)*8.0-(6.0*9.0)', '(8.0*8.0-(9.0*6.0))', '(8.0)*8.0-6.0*(9.0)', '(9.0)*(8.0-6.0)-(8.0)', '(8.0*(8.0)-9.0*(6.0))', '(8.0)*(8.0)-(6.0*(9.0))', '(8.0)*(8.0)-(9.0)*6.0', '(8.0)*(8.0)-9.0*6.0', '(8.0)*8.0-9.0*6.0', '(8.0)*(8.0)-(6.0)*(9.0)', '(8.0*8.0-(6.0)*9.0)', '(8.0*(8.0)-6.0*(9.0))', '(8.0*(8.0)-(6.0*(9.0)))', '(8.0)*8.0-6.0*9.0', '(8.0)*8.0-(9.0)*6.0', '(8.0*(8.0)-(9.0*6.0))', '(8.0*8.0-(6.0*9.0))', '(8.0*8.0-(6.0)*(9.0))', '(8.0*8.0-9.0*(6.0))', '(8.0-6.0)*9.0-(8.0)', '(8.0)*8.0-9.0*(6.0)', '(8.0)*(8.0)-(6.0)*9.0', '(8.0*8.0-(6.0*(9.0)))', '(8.0)*8.0-(6.0)*(9.0)', '(8.0)*8.0-(9.0*(6.0))', '(8.0*(8.0)-(9.0*(6.0)))', '(8.0)*8.0-(9.0*6.0)', '(8.0)*(8.0)-(6.0*9.0)', '(8.0)*8.0-(6.0)*9.0', '(8.0)*(8.0)-6.0*(9.0)', '(8.0*(8.0)-(6.0)*(9.0))', '(8.0*(8.0)-(6.0*9.0))', '(8.0*8.0-(9.0)*(6.0))', '(9.0)*(8.0-6.0)-8.0', '(8.0)*(8.0)-6.0*9.0', '(8.0*8.0)-(9.0*(6.0))', '(8.0*8.0-9.0*6.0)', '(8.0*(8.0)-6.0*9.0)', '(9.0*(8.0-6.0)-8.0)', '(8.0*(8.0)-9.0*6.0)', '(8.0)*(8.0)-(9.0*6.0)', '(8.0*8.0-(9.0)*6.0)', '(8.0*8.0-6.0*9.0)', '(8.0-6.0)*(9.0)-(8.0)', '(8.0*8.0)-(6.0*(9.0))', '(8.0-6.0)*9.0-8.0', '(8.0-6.0)*(9.0)-8.0', '(8.0*8.0)-6.0*(9.0)', '(8.0*8.0)-(9.0)*(6.0)', '(8.0*(8.0)-(9.0)*(6.0))', '(8.0*8.0)-9.0*(6.0)', '(8.0)*(8.0)-(9.0)*(6.0)', '(8.0)*8.0-(9.0)*(6.0)']
1337
['(3.0*(1.0+7.0/(3.0)))', '(3.0*(7.0/(3.0)+(1.0)))', '(1.0+(7.0)/3.0)*3.0', '(3.0)*(7.0/3.0+1.0)', '(7.0/(3.0)+1.0)*(3.0)', '(3.0)*(1.0+(7.0/(3.0)))', '(1.0+7.0/3.0)*(3.0)', '(3.0)*(7.0/(3.0)+(1.0))', '(3.0*(1.0+(7.0/(3.0))))', '(3.0*(1.0+(7.0/3.0)))', '(3.0)*(1.0+(7.0)/3.0)', '(7.0/3.0+1.0)*3.0', '(7.0/3.0+1.0)*(3.0)', '(3.0)*(1.0+(7.0)/(3.0))', '(7.0/(3.0)+1.0)*3.0', '(3.0*(1.0+(7.0)/3.0))', '(3.0*(7.0/3.0+1.0))', '(3.0)*(1.0+7.0/(3.0))', '(3.0*(7.0/3.0+(1.0)))', '(3.0*(1.0+(7.0)/(3.0)))', '(3.0*(1.0+7.0/3.0))', '(3.0)*(1.0+(7.0/3.0))', '(1.0+7.0/3.0)*3.0', '(3.0)*(7.0/(3.0)+1.0)', '(3.0*(7.0/(3.0)+1.0))', '(1.0+(7.0)/3.0)*(3.0)', '(3.0)*(7.0/3.0+(1.0))', '(3.0)*(1.0+7.0/3.0)']
|