順列の総当りでSEND MORE MONEYを解く

ドラマ『闇金ウシジマくん』
登場するお金に苦しんでいる人たちのほとんどは、どうしようもなく落ちるところまで落ちてしまい、凄惨な結末を迎えることが多いのですが、自業自得なところがあるので、視聴していても後味が悪いってことがないです。
それどころか、こうならないように堅実に頑張らければなんて思ってしまうので、視聴後は清々しく感じます。

タイトルの計算式はイギリスのパズル作家H. E. Dudeney(デュードニー)が発表した覆面算です。 総当たりするスクリプトで解いてみましょう。

各文字がどれぐらい使われているかコマンドを使い把握してみます(コマンド使わずとも目視でも十分ですが)。

~$ echo SENDMOREMONEY | grep -o '.'
S
E
N
D
M
O
R
E
M
O
N
E
Y
~$ echo SENDMOREMONEY | grep -o '.' | sort | uniq -c
      1 D
      3 E
      2 M
      2 N
      2 O
      1 R
      1 S
      1 Y
~$ 

ところどころで同じ文字が使われていますね。

次は順列を求めるスクリプトを書きます。pythonスクリプトです。

~$ cat -n perm.py
     1	import itertools
     2	for pm in itertools.permutations([0,1,2,3,4,5,6,7,8,9]):
     3		print pm
~$ 
~$ python perm.py | sed 10q
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
(0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
(0, 1, 2, 3, 4, 5, 6, 8, 7, 9)
(0, 1, 2, 3, 4, 5, 6, 8, 9, 7)
(0, 1, 2, 3, 4, 5, 6, 9, 7, 8)
(0, 1, 2, 3, 4, 5, 6, 9, 8, 7)
(0, 1, 2, 3, 4, 5, 7, 6, 8, 9)
(0, 1, 2, 3, 4, 5, 7, 6, 9, 8)
省略

send + more = moneyになればよいので、 forの中で生成される数字の順列を、各計算式に当てはめます。

send = c[0]*1000 + c[1]*100 + c[2]*10 + c[3]
more = c[4]*1000 + c[5]*100 + c[6]*10 + c[1]
money = c[4]*10000 + c[5]*1000 + c[2]*100 + c[1]*10 + c[7]

スクリプト全体です。

~$ cat -n sendmoremoney.py 
     1	import itertools
     2	for c in itertools.permutations([0,1,2,3,4,5,6,7,8,9]):
     3		send = c[0]*1000 + c[1]*100 + c[2]*10 + c[3]
     4		more = c[4]*1000 + c[5]*100 + c[6]*10 + c[1]
     5		money = c[4]*10000 + c[5]*1000 + c[2]*100 + c[1]*10 + c[7]
     6	
     7		if (send + more) == money and 10000 < money:
     8			print "  ",c[0],c[1],c[2],c[3]
     9			print "+ ",c[4],c[5],c[6],c[1]
    10			print "",c[4],c[5],c[2],c[1],c[7]
    11			break
    12	
~$ 

スクリプトを実行するとこのように答えが表示されます。

~$ python sendmoremoney.py 
   9 5 6 7
+  1 0 8 5
 1 0 6 5 2
~$ 

もうひとつ有名な問題を解いてみましょう。(本当にgoogleの入社試験なんでしょうか)

~$ cat google.py
import itertools
for c in itertools.permutations([0,1,2,3,4,5,6,7,8,9]):
	wwwdot = c[0]*100000 + c[0]*10000 + c[0]*1000 + c[1]*100 + c[2]*10 + c[3]
	google = c[4]*100000 + c[2]*10000 + c[2]*1000 + c[4]*100 + c[5]*10 + c[6]
	dotcom = c[1]*100000 + c[2]*10000 + c[3]*1000 + c[7]*100 + c[2]*10 + c[8]

	if (wwwdot - google) == dotcom:
		print " ",wwwdot
		print "-",google
		print " ",dotcom
		print

実行結果です。

~$ python google.py
  777589
- 188103
  589486

  777589
- 188106
  589483

~$