「jus共催 第46回人類はおそらくシェル芸に仕事を奪われるか奪われないかのどちらかであるシェル芸勉強会」の「Q8」で問題として出された覆面算についてPrologで解いてみました。
SEND + MORE = MONEYの各アルファベットに0から9の数字1字を割り当てて足し算を完成させてください。異なるアルファベッドには異なる数字を割り当ててください。S、Mには0を割り当てないでください。答えが分かるものであれば出力はなんでも構いません。
https://b.ueda.tech/?post=20200215_shellgei_46_q#q8
「Prologで良い感じに解けそう！」と思ったのですが、勉強会当日はPrologの構文を忘れておりこの問題は解け無かったので改めて解いてみました。
筆算の形式？にすると下記のような問題の各アルファベットに対応する数字を求める感じですね。
S E N D
+) M O R E
-----------
M O N E Y
環境
SWI Prologを使用しました。(SWI-Prolog version 7.6.4 for amd64)
OSはUbuntu 18.04です
解いてみる
問題の定義により M=1, S=9, O=0までは解けますね。
ちなみに勉強会当日はS、Mには0を割り当てないでください。の一文を読み飛ばしてしまい、気づくのに時間がかかってしまいましたが………
num([],0).
num([Head|Tail],Result) :- between(0,9,Head),num(Tail,V),Result is V * 10 + Head.
nums(L,X) :- reverse(L,R) , num(R,X).
goal :-
M=1, S=9, O=0,
use_module(library(clpfd)),
all_distinct([S,E,N,D,M,O,R,Y]),
nums([S,E,N,D],Send),
nums([M,O,R,E],More),
nums([M,O,N,E,Y],Money),
plus(Send,More,Money),
write([Send,More,Money]),nl,fail.
$ time swipl -q -t goal sample.pl
[9567,1085,10652]
real 0m0.356s
user 0m0.248s
sys 0m0.008s
特に何も考えなくてもPrologさんが答えを求めてくれます。すごい！
自分のノートPCだと0.3sくらいで計算が終わります。
numsで任意の覆面算に対応できるようにしていますが冗長な気がします。
愚直に解いてみる
実際には下記の方がシンプルで簡単な気がします。
しかし、is のあたりの構文が個人的に綺麗にみえないので苦手です。
goal :-
M=1, S=9, O=0,
use_module(library(clpfd)),
List=[S,E,N,D,M,O,R,Y],
maplist(call(between(0,9)),List),
all_distinct(List),
Send is S * 1000 + E * 100 + N * 10 + D,
More is 1000 + O * 100 + R * 10 + E,
Money is 10000 + O * 1000 + N * 100 + E * 10 + Y,
plus(Send,More,Money),
write([Send,More,Money]),nl,fail.
$ time swipl -q -t goal sample2.pl
[9567,1085,10652]
real 0m0.626s
user 0m0.514s
sys 0m0.012s
ちゃんと答えはでますが微妙に遅いです。
Prolog初心者なので遅い理由はわかりません。
無理やりワンライナーにしてみる
$ swipl -q -t goal -s <(echo 'goal :- M=1,S=9,O=0,use_module(library(clpfd)),List=[S,E,N,D,M,O,R,Y],maplist(call(between(0,9)),List),all_distinct(List),Send is S * 1000 + E * 100 + N * 10 + D,More is M * 1000 + O * 100 + R * 10 + E,Money is M * 10000 + O * 1000 + N * 100 + E * 10 + Y,plus(Send,More,Money),write([Send,More,Money]),nl,fail.')
これは……
こういう形で使う言語では無いですね……Prologが泣いています。
感想
1年ぶりにPrologを書きましたが、この言語は面白いですね。
書いてみて感じましたが、ワンライナーで書くのは難しそうですね。
ワンライナーとして使う機会はないと思いすが、Prolog自体は面白いので機会があればまた書きたいです。
参考にした記事
sample.plは頑張って自分で書いたのですが、sample2.plの回答は下記を参考にして書きました。
http://www.nct9.ne.jp/m_hiroi/prolog/prolog14.html#answer2
リンクによるとこの問題を考えたのは「ヘンリー・アーネスト・デュードニー」という人みたいです。なるほど。
他にも面白い問題がたくさんありますね。
おまけ
ちなみに問題文の S、Mには0を割り当てないでください。 の制限をなくした場合だと複数回答が発生しますが、
sample.plの１文を削除するだけでこれも求められます。すごい！
num([],0).
num([Head|Tail],Result) :- between(0,9,Head),num(Tail,V),Result is V * 10 + Head.
nums(L,X) :- reverse(L,R) , num(R,X).
goal :-
use_module(library(clpfd)),
all_distinct([S,E,N,D,M,O,R,Y]),
nums([S,E,N,D],Send),
nums([M,O,R,E],More),
nums([M,O,N,E,Y],Money),
plus(Send,More,Money),
write([Send,More,Money]),nl,fail.
$ time swipl -q -t goal sample3.pl
[3821,468,4289]
[7531,825,8356]
[5731,647,6378]
[6851,738,7589]
[3712,467,4179]
[8432,914,9346]
[5732,647,6379]
[8542,915,9457]
[7643,826,8469]
[6853,728,7581]
[8324,913,9237]
[6524,735,7259]
[7534,825,8359]
[6415,734,7149]
[7316,823,8139]
[2817,368,3185]
[9567,1085,10652]
[6419,724,7143]
[3719,457,4176]
[2819,368,3187]
[7429,814,8243]
[3829,458,4287]
[7539,815,8354]
[7649,816,8465]
[5849,638,6487]
real 2m19.913s
user 2m19.515s
sys 0m0.288s
しかし……かなり時間がかかりますね。