/* 

  Crypt benchmark in Picat.

  """
  Cryptomultiplication:
  Find the unique answer to:
	OEE
	 EE
 	---
       EOEE
       EOE
       ----
       OOEE

  where E=even, O=odd.
  """

  Prolog code from
  http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/06_bench/09_programs/02_crypt/01_crypt.p.html

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
import cp.

main => go.

% Prolog code
/**
 * Prolog code for the crypt riddle benchmark.
 *
 * This is problem 223 from:
 * Trigg, W. C. (1985): Mathematical Quickies,
 * Dover Publications, Inc., New York, 1985
 *
 * Copyright 2010, XLOG Technologies GmbH, Switzerland
 * Jekejeke Prolog 0.8.3 (a fast and small prolog interpreter)
 */
/*
sum2(AL, BL, CL) :-
      sum2(AL, BL, 0, CL).

sum2([A | AL], [B | BL], Carry, [C | CL]) :-
      X is (A + B + Carry),
      C is X rem 10,
      NewCarry is X // 10,
      sum2(AL, BL, NewCarry, CL).
sum2([], BL, 0, BL) :- !.
sum2(AL, [], 0, AL) :- !.
sum2([], [B | BL], Carry, [C | CL]) :-
      X is B + Carry,
      NewCarry is X // 10,
      C is X rem 10,
      sum2([], BL, NewCarry, CL).
sum2([A | AL], [], Carry, [C | CL]) :-
      X is A + Carry,
      NewCarry is X // 10,
      C is X rem 10,
      sum2([], AL, NewCarry, CL).
sum2([], [], Carry, [Carry]).

mult(AL, D, BL) :- mult(AL, D, 0, BL).

mult([], _, Carry, [C, Cend]) :-
      C is Carry rem 10,
      Cend is Carry // 10.
mult([A | AL], D, Carry, [B | BL] ) :-
      X is A * D + Carry,
      B is X rem 10,
      NewCarry is X // 10,
      mult(AL, D, NewCarry, BL).

zero([]).
zero([0 | L]) :- zero(L).

odd(1).
odd(3).
odd(5).
odd(7).
odd(9).

even(0).
even(2).
even(4).
even(6).
even(8).

lefteven(2).
lefteven(4).
lefteven(6).
lefteven(8).

crypt :-
      odd(A), even(B), even(C), even(E),
      mult([C, B, A], E, [I, H, G, F | X]),
      lefteven(F), odd(G), even(H), even(I), zero(X), lefteven(D),
      mult([C, B, A], D, [L, K, J | Y]),
      lefteven(J), odd(K), even(L), zero(Y),
      sum2([I, H, G, F], [0, L, K, J], [P, O, N, M | Z]),
      odd(M), odd(N), even(O), even(P), zero(Z).
*/


% Picat version
sum2(AL, BL, CL) =>
      sum2(AL, BL, 0, CL).

sum2([A | AL], BBL, Carry, CCL) =>
      BBL = [B | BL],
      CCL = [C | CL],
      X = (A + B + Carry),
      C = X rem 10,
      NewCarry = X // 10,
      sum2(AL, BL, NewCarry, CL).
sum2([], BL, 0, BL2) => BL2=BL.
sum2(AL, [], 0, AL2) => AL2=AL.
sum2([], BBL, Carry, CCL) =>
      BBL = [B | BL],
      CCL = [C | CL],
      X = B + Carry,
      NewCarry = X // 10,
      C = X rem 10,
      sum2([], BL, NewCarry, CL).
sum2(AAL, [], Carry, CCL) =>
      AAL=[A | AL],
      CCL=[C | CL],
      X = A + Carry,
      NewCarry = X // 10,
      C = X rem 10,
      sum2([], AL, NewCarry, CL).
sum2([], B, Carry, Carry2) => B=[], Carry2 = [Carry].

mult(AL, D, BL) => mult(AL, D, 0, BL).

mult([], _, Carry, CCendl) =>
      CCendl = [C, Cend],
      C = Carry rem 10,
      Cend = Carry // 10.
mult([A | AL], D, Carry, BBL) =>
      BBL = [B | BL],
      X = A * D + Carry,
      B = X rem 10,
      NewCarry = X // 10,
      mult(AL, D, NewCarry, BL).

table
zero([]) => true.
zero([0 | L]) => zero(L).

index(-)
oddx(1).
oddx(3).
oddx(5).
oddx(7).
oddx(9).

index(-)
evenx(0).
evenx(2).
evenx(4).
evenx(6).
evenx(8).

index(-)
leftevenx(2).
leftevenx(4).
leftevenx(6).
leftevenx(8).

crypt =>
      oddx(A), evenx(B), evenx(C), evenx(E),
      mult([C, B, A], E, [I, H, G, F | X]),
      leftevenx(F), oddx(G), evenx(H), evenx(I), zero(X), leftevenx(D),
      mult([C, B, A], D, [L, K, J | Y]),
      leftevenx(J), oddx(K), evenx(L), zero(Y),
      sum2([I, H, G, F], [0, L, K, J], [P, O, N, M | Z]),
      oddx(M), oddx(N), evenx(O), evenx(P), zero(Z),
      writeln([A,B,C,E,F,G,H,I,J,K,L,M,N,O,P]),
      writeln(ok).

crypt2 =>
      oddx(A), evenx(B), evenx(C), evenx(E),
      mult([C, B, A], E, [I, H, G, F | X]),
      leftevenx(F), oddx(G), evenx(H), evenx(I), zero(X), leftevenx(D),
      mult([C, B, A], D, [L, K, J | Y]),
      leftevenx(J), oddx(K), evenx(L), zero(Y),
      sum2([I, H, G, F], [0, L, K, J], [P, O, N, M | Z]),
      oddx(M), oddx(N), evenx(O), evenx(P), zero(Z).

go => crypt.

go2 => crypt2.