crypt.cpp

% crypt
%
% Cryptomultiplication:
% Find the unique answer to:
%	OEE
%	 EE
% 	---
% EOEE
% EOE
% ----
% OOEE
%
% where E=even, O=odd.
% This program generalizes easily
% to any such problem.
% Written by Peter Van Roy
#ifndef	MERCURY
#include "harness.cpp"
benchmark(_Data, Out) :-
	crypt(Out).
data(_).
#else
:- module crypt.
:- interface.
:- import_module list, int, io, printlist.
:- pred benchmark(list(int)).
:- mode benchmark(out) is nondet.
:- pred main(io__state, io__state).
:- mode main(di, uo) is multidet.
:- implementation.
:- import_module require.
benchmark(Out) :-	
	crypt(Out).
main -->
	( { crypt(Out) } ->
		print_list(Out)
	;
		io__write_string("no solution\n")
	).
:- pred crypt(list(int)).
:- mode crypt(out) is nondet.
:- pred sum2(list(int), list(int), list(int)).
:- mode sum2(in, in, out) is det.
:- pred sum2(list(int), list(int), int, list(int)).
:- mode sum2(in, in, in, out) is det.
:- pred mult(list(int), int, list(int)).
:- mode mult(in, in, out) is det.
:- pred mult(list(int), int, int, list(int)).
:- mode mult(in, in, in, out) is det.
:- pred zero(list(int)).
:- mode zero(in) is semidet.
:- pred odd(int).
:- mode odd(in) is semidet.
:- mode odd(out) is multidet.
:- pred even(int).
:- mode even(in) is semidet.
:- mode even(out) is multidet.
:- pred lefteven(int).
:- mode lefteven(in) is semidet.
:- mode lefteven(out) is multidet.
#endif
#ifdef	AQUARIUS_DECLS
:- mode((sum2(AL, BL, CL) :-
		ground(AL),
		list(AL),
		ground(BL),
		list(BL)
	)).
:- mode((sum2(AL, BL, C, CL) :-
		ground(AL),
		list(AL),
		ground(BL),
		list(BL),
		ground(C),
		integer(C)
	)).
:- mode((mult(AL, B, CL) :-
		ground(AL),
		list(AL),
		ground(B),
		integer(B)
	)).
:- mode((mult(AL, B, C, CL) :-
		ground(AL),
		list(AL),
		ground(B),
		integer(B),
		ground(C),
		integer(C)
	)).
:- mode((zero(L) :-
		ground(L),
		list(L)
	)).
#endif
crypt([A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]) :-
	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).
	% write(' '), write(A), write(B), write(C), nl,
	% write(' '), write(D), write(E), nl,
	% write(F), write(G), write(H), write(I), nl,
	% write(J), write(K), write(L), nl,
	% write(M), write(N), write(O), write(P), nl.
% In the usual source this predicate is named sum. However, sum is a
% language construct in NU-Prolog, and cannot be defined as a predicate.
% If you try, nc comes up with an obscure error message.
#ifdef	NUPROLOG_DECLS
:- sum2(AL, BL, CL) when AL and BL.
#endif
#ifdef	SICSTUS_DECLS
:- block sum2(-, ?, ?), sum2(?, -, ?).
#endif
sum2(AL, BL, CL) :-
	sum2(AL, BL, 0, CL).
#ifdef	NUPROLOG_DECLS
:- sum2(AL, BL, C, CL) when AL and BL and C.
#endif
#ifdef	SICSTUS_DECLS
:- block sum2(-, ?, ?, ?), sum2(?, -, ?, ?), sum2(?, ?, -, ?).
#endif
#ifdef	MERCURY
sum2([], [], Carry, Cs) :-
	( Carry = 0 ->
		Cs = []
	;
		Cs = [Carry]
	).
sum2([], [B | BL], Carry, Cs) :-
	( Carry = 0 ->
		Cs = [B | BL]
	;
		X is B + Carry,
		NewCarry is X // 10,
		C is X mod 10,
		sum2([], BL, NewCarry, CL),
		Cs = [C | CL]
	).
sum2([A | AL], [], Carry, Cs) :-
	( Carry = 0 ->
		Cs = [A | AL]
	;
		X is A + Carry,
		NewCarry is X // 10,
		C is X mod 10,
		sum2([], AL, NewCarry, CL),
		Cs = [C | CL]
	).
sum2([A | AL], [B | BL], Carry, Cs) :-
	X is A + B + Carry,
	C is X mod 10,
	NewCarry is X // 10,
	sum2(AL, BL, NewCarry, CL),
	Cs = [C | CL].
#else
sum2([A | AL], [B | BL], Carry, [C | CL]) :- !,
	X is (A + B + Carry),
	C is X mod 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 mod 10,
	sum2([], BL, NewCarry, CL).
sum2([A | AL], [], Carry, [C | CL]) :- !,
	X is A + Carry,
	NewCarry is X // 10,
	C is X mod 10,
	sum2([], AL, NewCarry, CL).
sum2([], [], Carry, [Carry]).
#endif
#ifdef	NUPROLOG_DECLS
:- mult(AL, BL, CL) when AL and BL.
#endif
#ifdef	SICSTUS_DECLS
:- block mult(-, ?, ?), mult(?, -, ?).
#endif
mult(AL, D, BL) :- mult(AL, D, 0, BL).
#ifdef	NUPROLOG_DECLS
:- mult(AL, BL, C, CL) when AL and BL and C.
#endif
#ifdef	SICSTUS_DECLS
:- block mult(-, ?, ?, ?), mult(?, -, ?, ?), mult(?, ?, -, ?).
#endif
mult([A | AL], D, Carry, [B | BL] ) :-
	X is A * D + Carry,
	B is X mod 10,
	NewCarry is X // 10,
	mult(AL, D, NewCarry, BL).
mult([], _, Carry, [C, Cend]) :-
	C is Carry mod 10,
	Cend is Carry // 10.
#ifdef	NUPROLOG_DECLS
:- zero(L) when L.
#endif
#ifdef	SICSTUS_DECLS
:- block zero(-).
#endif
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).