今回は覆面算です

解説動画はこちら



さて覆面算とは、0から9の数字が対応する
別の記号に置き換えられた計算式を与えられて
どの記号が何の数字に対応しているかを推理して
完全な計算式を導き出すパズルのことです。

 
   A B C
+ A C B
————
   C B A

A=4,B=5,C=9


ルール
同じ文字には同じ数字
違う文字には違う数字が入る(0-9 , 最多で10種類)
一番左側の文字は0にはならない

これを解くプログラムを考えてみましょう。

1問目は

    S E N D
+   M O R E
------------------------
  M O N E Y


文字と数値の変換を行い
何も考えず総当たりでこの計算式が解けるかどうかで
判定してみます。
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)

{'D': 7, 'E': 5, 'M': 1, 'N': 6, 'O': 0, 'R': 8, 'S': 9, 'Y': 2}
9567
1085
-------
10652

6.051903963088989

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

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)
9567
1085
-------
10652

0.5969181060791016

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


2問目です。

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

  WWWDOT
ー GOOGLE
-----------------------
  DOTCOM

今度は引き算ですが
やることは一緒ですね。
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)
777589
188103
-------
589486

2.180610179901123


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

こんな感じにしてみました。
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)

777589
188103
-------
589486

777589
188106
-------
589483

0.25487303733825684


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

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

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

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

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

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

それでは。