Solves cryptarithms consisting of the division of two integers resulting in a repeated fraction. For example:
BIG / JOKE = 0.HAHAHA...
GORE / BUSH = 0.NONONO...
TIN / NEON = 0.COBALTCOBALT...
/* cry([[B,I,G], [J,O,K,E], [H,A]]). cry([[H,U,G,E], [J,O,K,E], [H,A]]). cry([[H,U,G,E], [J,O,K,E], [H,O]]). cry([[L,O,S,T], [H,E,R,O], [S,L,E,P,T]]). cry([[G,O,R,E], [B,U,S,H], [N,O]]). cry([[L,U,N,D,I], [M,A,R,D,I], [J,E,U,D,I]]). cry([[I,O,W,A], [O,H,I,O], [M,A,I,N,E]]). cry([[T,A,F,T], [T,Y,L,E,R], [P,O,L,K]]). cry([[T,I,N], [N,E,O,N], [C,O,B,A,L,T]]). cry([[X,I], [R,H,O], [L,A,M,B,D,A]]). cry([[P,I], [B,E,T,A], [R,H,O]]). */ cry([Cs,Bs,As]):- append(As, Cs, Zs), pad_right_with_zeros(Zs, Cs, Ds), sub_products(As, Bs, [], SubProducts), columns(SubProducts, [], Columns), reverse(Cs, Addend), reverse(Ds, Totals), solve(Totals, Columns, Addend, [0,1,2,3,4,5,6,7,8,9], 0), Cs \= [0|_], Bs \= [0|_], write([Cs,Bs,As]), nl, fail. /* pad_right_with_zeros(Xs, Ys, Zs) is true if the list Zs is the result */ /* of padding the list Ys on the right with zeros to the length of the */ /* list Xs. */ pad_right_with_zeros([], Ys, Ys). pad_right_with_zeros([_|Xs], [], [0|Zs]):- pad_right_with_zeros(Xs, [], Zs). pad_right_with_zeros([_|Xs], [Y|Ys], [Y|Zs]):- pad_right_with_zeros(Xs, Ys, Zs). sub_products([], _, Zss, Zss). sub_products([X|Xs], Ys, Zss0, Zss):- sub_products_1(Ys, X, Zs), sub_products(Xs, Ys, [Zs|Zss0], Zss). sub_products_1([], _, []). sub_products_1([Y|Ys], X, [p(X,Y)|Zs]):- sub_products_1(Ys, X, Zs). columns([], Yss, Zss):- reverse(Yss, Zss). columns([Xs|Xss], Yss0, Yss):- columns_1(Xs, [[]|Yss0], Yss1), columns(Xss, Yss1, Yss). columns_1([], Yss, Yss). columns_1([X|Xs], [], [[X]|Ys]):- columns_1(Xs, [], Ys). columns_1([X|Xs], [Ys|Yss], [[X|Ys]|Zss]):- columns_1(Xs, Yss, Zss). /* This is where all the work is done */ solve([], [], [], _, 0). solve([], [Xs|Xss], As, Digits, Carry):- solve([0], [Xs|Xss], As, Digits, Carry). solve([Z|Zs], [], As, Digits, Carry):- solve([Z|Zs], [[]], As, Digits, Carry). solve([Z|Zs], [Xs|Xss], [], Digits, Carry):- solve([Z|Zs], [Xs|Xss], [0], Digits, Carry). solve([Z|Zs], [Xs|Xss], [A|As], Digits, Carry):- column_sum(Xs, Digits, Digits1, Carry, Sum), select(A, Digits1, Digits2), Digit is (Sum + A) mod 10, select(Z, Digits2, Digits3), Digit = Z, Carry1 is (Sum + A) // 10, solve(Zs, Xss, As, Digits3, Carry1). column_sum([], Digits, Digits, Sum, Sum). column_sum([p(A,B)|Xs], Digits0, Digits, Sum0, Sum):- select(A, Digits0, Digits1), select(B, Digits1, Digits2), Sum1 is Sum0 + A * B, column_sum(Xs, Digits2, Digits, Sum1, Sum). /* select(X, Ys, Zs) is true either if X is bound and the list Zs is equal */ /* to the list Ys, or if X is not bound and the list Zs is the result of */ /* removing one occurrence of the element X from the list Ys. */ select(X, Ys, Ys):-nonvar(X), !. select(X, Ys, Zs):-remove(X, Ys, Zs).