「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を割り当てないでください。の一文を読み飛ばしてしまい、気づくのに時間がかかってしまいましたが………

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 :-
    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 のあたりの構文が個人的に綺麗にみえないので苦手です。

sample2.pl

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の１文を削除するだけでこれも求められます。すごい！

sample3.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

しかし……かなり時間がかかりますね。