今回は覆面算です

解説動画はこちら



さて覆面算とは、0から9の数字が対応する
文字と数値の変換を行い
何も考えず総当たりでこの計算式が解けるかどうかで
判定してみます。

import itertools
from time import time
tm=time()

d1 = "SEND"
d2 = "MORE"
d3 = "MONEY"

for n in itertools.permutations(range(10) , len({a for a in d1 + d2 + d3})):
    data = dict(zip(sorted({a for a in d1 + d2 + d3}),n))
    if data[d1[0]]*data[d2[0]]*data[d3[0]]!=0:
        a1 = int(''.join([str(data[d]) for d in d1]))
        a2 = int(''.join([str(data[d]) for d in d2]))
        a3 = int(''.join([str(data[d]) for d in d3]))
        if a1+a2 == a3:
            print(data)
            print(a1)
            print(a2)
            print("-------")
            print(a3)
            print()
            break
            
print(time()-tm)

とりあえずは答えが出ましたね。

10個の数字から8個を取り出した
数字の順列は結構な数があります。

このプログラムだと
結構時間かかっちゃう感じなので
少し改良してみましょう。

変数に直接数字を受けたり
文字列に直すのやめたり
少し条件を加えてみましょう。

import itertools
from time import time
tm=time() 

def calc(p,q,r,s,t):
    return p*10000 + q*1000 + r*100 + s*10 + t

"""
  SEND
+MORE
----------
MODEY
"""
for p in itertools.permutations(range(10),8):
    s,e,n,d,m,o,r,y=p
    if s*m!=0 and (d+e==y or d+e==10+y):
        send  = calc(0,s,e,n,d)
        more  = calc(0,m,o,r,e)
        money = calc(m,o,n,e,y)
        if send+more==money:
            print(send)
            print(more)
            print("-------")
            print(money)
            print("")
            break

print(time()-tm)

先ほどと比べると
10分の1くらいの時間で
終わるようになりました。


2問目です。

これはGoogleの入社試験の
問題らしいです。


今度は引き算ですが
やることは一緒ですね。

import itertools
from time import time
tm=time() 

"""
WWWDOT
GOOGLE
-------------
DOTCOM
"""
for p in itertools.permutations(range(10),9):
    W,D,O,T,G,L,E,C,M = p
    if W*G*D==0: continue
    wwwdot = 100000*W+10000*W+1000*W+100*D+10*O+T
    google = 100000*G+10000*O+1000*O+100*G+10*L+E
    dotcom = 100000*D+10000*O+1000*T+100*C+10*O+M
    if wwwdot-google==dotcom:
        print(wwwdot)
        print(google)
        print("-------")
        print(dotcom)
        print()
        break

print(time()-tm)

こいつもまあまあ時間かかっちゃうので
早くなるように改良してみましょう。

こんな感じにしてみました。

import itertools
from time import time
tm=time() 

"""
WWWDOT
GOOGLE
-------------
DOTCOM
"""

for q in itertools.permutations(range(10),3):
    T,E,M = q
    if (T-E==M) or (10+T-E==M):
        for p in itertools.permutations(list(set(range(10)) - set(q)),6):
            W,D,O,G,L,C = p
            if W*G*D==0: continue        
            wwwdot = 100000*W+10000*W+1000*W+100*D+10*O+T
            google = 100000*G+10000*O+1000*O+100*G+10*L+E
            dotcom = 100000*D+10000*O+1000*T+100*C+10*O+M
            if wwwdot - google==dotcom:
                print(wwwdot)
                print(google)
                print("-------")
                print(dotcom)
                print()

print(time()-tm)

1秒切るくらいに早くなりましたね。

注目すべきは1桁目です。
TからEを引いたらMになるはずなので
この3つの数字の関係性を先に計算し
合致するものだけ次に進みます。

残る6個の数字と組み合わせて
計算式を満たせば終了です。

そうすることで、だいぶ計算量が減りますね。

この覆面算パズルは
アルゴリズムを練習するのには
とても良い題材ですね。

色々改良して
早くしてみてください。

それでは。

タグ ：

プログラミング

Python

覆面算

パズル

Google

入社問題