Division Cryptarithm Solver

Solves cryptarithms consisting of the division of two integers resulting in a repeated fraction. For example:

/*
  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).

LPA Index     Home Page

Valid HTML 4.0 Strict