Hatena::Grouppython

Pythonで遊ぶよ

 | 

2010-12-25

SEND+MORE=MONEY

04:31

おもしろかった。リストの内包表記みたいだと思った。

digits = set(range(0,10))

def dig(*args):
  return reduce(lambda x,y: x*10 + y, args)

ans = [(dig(s,e,n,d), dig(m,o,r,e), dig(m,o,n,e,y))
    for s in digits
    for e in digits - set([s])
    for n in digits - set([s,e])
    for d in digits - set([s,e,n])
    for m in digits - set([s,e,n,d])
    for o in digits - set([s,e,n,d,m])
    for r in digits - set([s,e,n,d,m,o])
    for y in digits - set([s,e,n,d,m,o,r])
    if  s != 0
    and m != 0
    and dig(s,e,n,d) + dig(m,o,r,e) == dig(m,o,n,e,y)]

print(ans)

深さ優先探索。ただし全部列挙なのでオーダーは O(N!) かな?

何度も同じ計算をやってる部分をちょっと直すと実行時間40%オフになるけど。

digits = set(range(0,10))

def dig(*args):
  return reduce(lambda x,y: x*10 + y, args)

ans = [(send, more, dig(m,o,n,e,y))
    for s in digits - set([0])
    for e in digits - set([s])
    for n in digits - set([s,e])
    for d in digits - set([s,e,n])
    for send in [dig(s,e,n,d)]
    for m in digits - set([0,s,e,n,d])
    for o in digits - set([s,e,n,d,m])
    for r in digits - set([s,e,n,d,m,o])
    for more in [dig(m,o,r,e)]
    for y in digits - set([s,e,n,d,m,o,r])
    if send + more == dig(m,o,n,e,y)]

print(ans)
トラックバック - http://python.g.hatena.ne.jp/edvakf/20101225
 |