在 Prolog 中更快地实现口头算术 [英] Faster implementation of verbal arithmetic in Prolog

问题描述

我已经在 Prolog 中制作了一个通用的 verbal 算术求解器，但它太慢了.运行简单的表达式 S E N D + M O R E = M O N E Y 需要 8 分钟.有人可以帮我让它运行得更快吗?

I already made a working generalized verbal arithmetic solver in Prolog but it's too slow. It takes 8 minutes just to run the simple expression S E N D + M O R E = M O N E Y. Can someone help me make it run faster?

/* verbalArithmetic(List,Word1,Word2,Word3) where List is the list of all 
   possible letters in the words. The SEND+MORE = MONEY expression would then
   be represented as
    verbalArithmetic([S,E,N,D,M,O,R,Y],[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]). */

validDigit(X) :- member(X,[0,1,2,3,4,5,6,7,8,9]).
validStart(X) :- member(X,[1,2,3,4,5,6,7,8,9]).
assign([H|[]]) :- validDigit(H).         
assign([H|Tail]) :- validDigit(H), assign(Tail), fd_all_different([H|Tail]).

findTail(List,H,T) :- append(H,[T],List).

convert([T],T) :- validDigit(T).
convert(List,Num) :- findTail(List,H,T), convert(H,HDigit), Num is (HDigit*10+T).

verbalArithmetic(WordList,[H1|Tail1],[H2|Tail2],Word3) :- 
    validStart(H1), validStart(H2), assign(WordList), 
    convert([H1|Tail1],Num1),convert([H2|Tail2],Num2), convert(Word3,Num3), 
    Sum is Num1+Num2, Num3 = Sum.

推荐答案

这里表现不佳是由于在检查是否可行之前形成所有可能的字母分配.

Poor performance here is due to forming all possible letter assignments before checking if any are feasible.

我的建议是尽早失败，经常失败".也就是说，尽早将尽可能多的失败检查推送到分配步骤中，从而修剪搜索树.

My advice is "fail early, fail often". That is, push as many checks for failure as early as possible into the assignment steps, thus pruning the search tree.

Klas Lindbäck 提出了一些很好的建议.作为概括，当添加两个数字时，每个位置最多有一个进位.因此，可以检查从左到右对字母的不同数字的分配，并考虑在最右边的位置可能存在尚未确定的进位.(当然在最后的单位"处，是没有进位的.)

Klas Lindbäck makes some good suggestions. As a generalization, when adding two numbers the carry is at most one in each place. So the assignment of distinct digits to letters from left to right can be checked with allowance for the possibility of an as-yet-undetermined carry in the rightmost places. (Of course in the final "units" place, there is no carry.)

要考虑的事情很多，这就是为什么约束逻辑，正如 mat 所建议的那样(您已经用 fd_all_different/1 讨论过)如此方便.

It's a lot to think about, which is why constraint logic, as mat suggests (and which you've already broached with fd_all_different/1), is such a convenience.

补充:这是一个没有约束逻辑的Prolog解决方案，只使用一个辅助谓词omit/3:

Added: Here's a Prolog solution without constraint logic, using just one auxiliary predicate omit/3:

omit(H,[H|T],T).
omit(X,[H|T],[H|Y]) :- omit(X,T,Y).

它既从列表中选择一个项目，又生成没有该项目的缩短列表.

which both selects an item from a list and produces the shortened list without that item.

下面是 sendMoreMoney/3 的代码，它通过从左到右求和来进行搜索:

Here then is the code for sendMoreMoney/3 that searches by evaluating the sum from left to right:

sendMoreMoney([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :-
    M = 1,
    omit(S,[2,3,4,5,6,7,8,9],PoolO),
    (CarryS = 0 ; CarryS = 1),
    %% CarryS + S + M =      M*10 + O
    O is (CarryS + S + M) - (M*10), 
    omit(O,[0|PoolO],PoolE),
    omit(E,PoolE,PoolN),
    (CarryE = 0 ; CarryE = 1),
    %% CarryE + E + O = CarryS*10 + N
    N is (CarryE + E + O) - (CarryS*10),
    omit(N,PoolN,PoolR),
    (CarryN = 0 ; CarryN = 1),
    %% CarryN + N + R = CarryE*10 + E
    R is (CarryE*10 + E) - (CarryN + N),
    omit(R,PoolR,PoolD),
    omit(D,PoolD,PoolY),
    %%          D + E = CarryN*10 + Y
    Y is (D + E) - (CarryN*10),
    omit(Y,PoolY,_).

我们通过观察 M 必须是最左边数字和的非零进位来快速开始，因此是 1，并且 S 必须是其他一些非零数字.注释显示了可以根据已经做出的选择确定性地为附加字母分配值的步骤.

We get off to a quick start by observing that M must be the nonzero carry from the leftmost digits sum, hence 1, and that S must be some other nonzero digit. The comments show steps where additional letters may be deterministically assigned values based on choices already made.

已添加(2):这是一个用于两个加法的通用"密码算法求解器，它们不需要具有相同的位置"长度/数量.length/2 的代码作为一个相当常见的内置谓词被省略，并接受 Will Ness 的建议，对 omit/3 的调用被替换为 select/3 方便 SWI-Prolog 用户.

Added(2): Here is a "general" cryptarithm solver for two summands, which need not have the same length/number of "places". Code for length/2 is omitted as a fairly common built-in predicate, and taking up the suggestion by Will Ness, calls to omit/3 are replaced by select/3 for convenience of SWI-Prolog users.

我已经用 Amzi 测试过了！和 SWI-Prolog 使用那些字母表示例来自 Cryptarithms.com，其中涉及两个加法，每个加法都有一个独特的解决方案.我还用十几个解决方案组成了一个示例，I + AM = BEN，以测试正确的回溯.

I've tested this with Amzi! and SWI-Prolog using those alphametics examples from Cryptarithms.com which involve two summands, each of which has a unique solution. I also made up an example with a dozen solutions, I + AM = BEN, to test proper backtracking.

solveCryptarithm([H1|T1],[H2|T2],Sum) :-
    operandAlign([H1|T1],[H2|T2],Sum,AddTop,AddPad,Carry,TSum,Pool),
    solveCryptarithmAux(H1,H2,AddTop,AddPad,Carry,TSum,Pool).

operandAlign(Add1,Add2,Sum,AddTop,AddPad,Carry,TSum,Pool) :-
    operandSwapPad(Add1,Add2,Length,AddTop,AddPad),
    length(Sum,Size),
    (   Size = Length
     -> ( Carry = 0, Sum = TSum , Pool = [1|Peel] )
     ;  ( Size is Length+1, Carry = 1, Sum = [Carry|TSum], Pool = Peel )
    ),
    Peel = [2,3,4,5,6,7,8,9,0].

operandSwapPad(List1,List2,Length,Longer,Padded) :-
    length(List1,Length1),
    length(List2,Length2),
    (   Length1 >= Length2
     -> ( Length = Length1, Longer = List1, Shorter = List2, Pad is Length1 - Length2 )
     ;  ( Length = Length2, Longer = List2, Shorter = List1, Pad is Length2 - Length1 )
    ),
    zeroPad(Shorter,Pad,Padded).

zeroPad(L,0,L).
zeroPad(L,K,P) :-
    K > 0,
    M is K-1,
    zeroPad([0|L],M,P).

solveCryptarithmAux(_,_,[],[],0,[],_).
solveCryptarithmAux(NZ1,NZ2,[H1|T1],[H2|T2],CarryOut,[H3|T3],Pool) :-
    ( CarryIn = 0 ; CarryIn = 1 ),   /* anticipatory carry */
    (   var(H1)
     -> select(H1,Pool,P_ol)
     ;  Pool = P_ol
    ),
    (   var(H2)
     -> select(H2,P_ol,P__l)
     ;  P_ol = P__l
    ),
    (   var(H3)
     -> ( H3 is H1 + H2 + CarryIn - 10*CarryOut, select(H3,P__l,P___) )
     ;  ( H3 is H1 + H2 + CarryIn - 10*CarryOut, P__l = P___ )
    ),
    NZ1 == 0,
    NZ2 == 0,
    solveCryptarithmAux(NZ1,NZ2,T1,T2,CarryIn,T3,P___).

我认为这说明了从左到右搜索/评估的优势可以在通用"求解器中获得，与早期的定制"代码相比，推理的数量大约增加了两倍.

I think this illustrates that the advantages of left-to-right search/evaluation can be attained in a "generalized" solver, increasing the number of inferences by roughly a factor of two in comparison with the earlier "tailored" code.

这篇关于在 Prolog 中更快地实现口头算术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！