% -*- fundamental -*-

:- use_module(library(clpfd)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1. Variante (ein Praedikat fuer send und receive)
% klassisches backtracking
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

element_von_rest(X, [X|Xs], Xs).
element_von_rest(Y, [X|Xs], [X|Zs]) :-
   element_von_rest(Y, Xs, Zs).

weg_zeit_hier_dort([], 0, [], _Ds).
weg_zeit_hier_dort([X+Y], Y, Hs, _Ds) :-
   X #=< Y,
   element_von_rest(X, Hs, [Y]).
weg_zeit_hier_dort([X+Y,-Z|Ws], T, Hs0, Ds0) :-
   X #=< Y,
   T #= T0+Y+Z,
   element_von_rest(X, Hs0, Hs1),
   element_von_rest(Y, Hs1, Hs),
   element_von_rest(Z, [X,Y|Ds0], Ds),
   weg_zeit_hier_dort(Ws, T0, [Z|Hs], Ds).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2. Variante (jeweils ein Praedikat fuer send bzw. receive)
% klassisches backtracking
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

wegP_zeit_hier_dort([], 0, [], _Ds).
wegP_zeit_hier_dort([X+Y|Ws], T, Hs0, Ds) :-
   X #=< Y,
   T0 #>= 0,
   T #= T0+Y,
   element_von_rest(X, Hs0, Hs1),
   element_von_rest(Y, Hs1, Hs),
   wegN_zeit_hier_dort(Ws, T0, Hs, [X,Y|Ds]).

wegN_zeit_hier_dort([], 0, [], _Ds).
wegN_zeit_hier_dort([-Z|Ws], T, Hs, Ds0) :-
   T0 #>= 0,
   T #= T0+Z,
   element_von_rest(Z, Ds0, Ds),
   wegP_zeit_hier_dort(Ws, T0, [Z|Hs], Ds).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3. Variante (jeweils ein Praedikat fuer send bzw. receive)
% clpfd mit relation/2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/*
 1+2		= 3
 1+5		= 6
 2+5		= 7
 1+2+5		= 8
 1+10		= 11
 2+10		= 12
 1+2+10		= 13
 5+10		= 15
 1+5+10 	= 16
 2+5+10 	= 17
 1+2+5+10 	= 18

=> Beobachtung: Jede moegliche Summe hat eindeutige Zerlegung 
   in entsprechende Summanden.

   Spezielle Codierung der Listen Hier,Dort moeglich.
   Rolle von element_von_rest/3 uebernimmt relation/2 und #=/2.
*/


/*
usage:

?- Hier=[1, 2, 5, 10], 
   Ws = [_,_,_,_,_],
   wegP_zeit_hier_dort_(Ws, K, 18, 0, Vars),
   labeling([], Vars).
*/

% domain-consistent addition
plusd(X,Y,T) +:				% X+Y #= T
   X in dom(T) - dom(Y),
   Y in dom(T) - dom(X),
   T in dom(X) + dom(Y).

wegP_zeit_hier_dort_([], 0, 0, 18, []).
wegP_zeit_hier_dort_([X+Y|Ws], T, Hs0, Ds0, [X,Y|Zs]) :-
   plusd(T0,Y,T),		% T0+Y #= T,
   relation(X,
	    [1-({3}\/{6}\/{8}\/{11}\/{13}\/{16}\/{18}),
	     2-((7..8)\/(12..13)\/(17..18)),
	     5-(15..18)],
	    Hs0),
   relation(Y,
	    [2-({3}\/{8}\/{13}\/{18}),
	     5-((6..8)\/(16..18)),
	     10-((11..13)\/(15..18))],
	    Hs0),
   X #< Y,
   plusd(X,Y,XY),  		% X + Y #= XY
   plusd(Hs,XY,Hs0),		% Hs + XY #= Hs0
   plusd(Ds0,XY,Ds),		% Ds0 + XY #= Ds
   wegN_zeit_hier_dort_(Ws, T0, Hs, Ds, Zs).

wegN_zeit_hier_dort_([], 0, 0, 18, []).
wegN_zeit_hier_dort_([-Z|Ws], T, Hs0, Ds0, [Z|Zs]) :-
   plusd(T0,Z,T),		% T0+Z #= T,
   relation(Z,
	    [1-({3}\/{6}\/{8}\/{11}\/{13}\/{16}\/{18}),
	     2-({3}\/(7..8)\/(12..13)\/(17..18)),
	     5-((6..8)\/(15..18)),
	     10-((11..13)\/(15..18))], 
	    Ds0),
   plusd(Hs0,Z,Hs),		% Hs0 + Z #= Hs
   plusd(Ds,Z,Ds0),		% Ds + Z #= Ds0
   wegP_zeit_hier_dort_(Ws, T0, Hs, Ds, Zs).



%%%%%%%%%%%%
% Ergebnisse
%%%%%%%%%%%%

/*
?- K in 1..100, indomain(K), weg_zeit_hier_dort(Ws, K, [1,2,5,10], []), write(costs_solution(K, Ws)),nl,false.

costs_solution(17,[1+2,-(1),5+10,-(2),1+2])
costs_solution(17,[1+2,-(2),5+10,-(1),1+2])
costs_solution(19,[1+2,-(1),1+5,-(1),1+10])
costs_solution(19,[1+2,-(1),1+10,-(1),1+5])
costs_solution(19,[1+5,-(1),1+2,-(1),1+10])
costs_solution(19,[1+5,-(1),1+10,-(1),1+2])
costs_solution(19,[1+10,-(1),1+2,-(1),1+5])
costs_solution(19,[1+10,-(1),1+5,-(1),1+2])
costs_solution(20,[1+2,-(1),1+5,-(2),2+10])
costs_solution(20,[1+2,-(1),1+10,-(2),2+5])
costs_solution(20,[1+2,-(2),2+5,-(1),1+10])
costs_solution(20,[1+2,-(2),2+10,-(1),1+5])
costs_solution(20,[1+5,-(1),1+2,-(2),2+10])
costs_solution(20,[1+5,-(1),2+10,-(2),1+2])
costs_solution(20,[1+10,-(1),1+2,-(2),2+5])
costs_solution(20,[1+10,-(1),2+5,-(2),1+2])
costs_solution(20,[2+5,-(2),1+2,-(1),1+10])
costs_solution(20,[2+5,-(2),1+10,-(1),1+2])
costs_solution(20,[2+10,-(2),1+2,-(1),1+5])
costs_solution(20,[2+10,-(2),1+5,-(1),1+2])
costs_solution(21,[1+2,-(2),2+5,-(2),2+10])
costs_solution(21,[1+2,-(2),2+10,-(2),2+5])
costs_solution(21,[2+5,-(2),2+10,-(2),1+2])
costs_solution(21,[2+5,-(2),1+2,-(2),2+10])
costs_solution(21,[2+10,-(2),2+5,-(2),1+2])
costs_solution(21,[2+10,-(2),1+2,-(2),2+5])
costs_solution(23,[1+2,-(1),1+5,-(5),5+10])
costs_solution(23,[1+2,-(1),5+10,-(5),1+5])
costs_solution(23,[1+5,-(1),1+2,-(5),5+10])
costs_solution(23,[1+5,-(5),5+10,-(1),1+2])
costs_solution(23,[5+10,-(5),1+5,-(1),1+2])
costs_solution(23,[5+10,-(5),1+2,-(1),1+5])
costs_solution(24,[1+2,-(2),2+5,-(5),5+10])
costs_solution(24,[1+2,-(2),5+10,-(5),2+5])
costs_solution(24,[2+5,-(2),1+2,-(5),5+10])
costs_solution(24,[2+5,-(5),5+10,-(2),1+2])
costs_solution(24,[5+10,-(5),1+2,-(2),2+5])
costs_solution(24,[5+10,-(5),2+5,-(2),1+2])
costs_solution(26,[1+5,-(1),1+10,-(5),2+5])
costs_solution(26,[1+5,-(1),2+10,-(5),1+5])
costs_solution(26,[1+5,-(5),2+5,-(1),1+10])
costs_solution(26,[1+5,-(5),2+10,-(1),1+5])
costs_solution(26,[1+10,-(1),1+5,-(5),2+5])
costs_solution(26,[1+10,-(1),2+5,-(5),1+5])
costs_solution(26,[2+5,-(5),1+5,-(1),1+10])
costs_solution(26,[2+5,-(5),1+10,-(1),1+5])
costs_solution(27,[1+5,-(5),2+5,-(2),2+10])
costs_solution(27,[1+5,-(5),2+10,-(2),2+5])
costs_solution(27,[2+5,-(2),2+10,-(5),1+5])
costs_solution(27,[2+5,-(2),1+10,-(5),2+5])
costs_solution(27,[2+5,-(5),1+5,-(2),2+10])
costs_solution(27,[2+5,-(5),1+10,-(2),2+5])
costs_solution(27,[2+10,-(2),2+5,-(5),1+5])
costs_solution(27,[2+10,-(2),1+5,-(5),2+5])
costs_solution(30,[1+5,-(5),5+10,-(5),2+5])
costs_solution(30,[1+5,-(5),2+5,-(5),5+10])
costs_solution(30,[2+5,-(5),5+10,-(5),1+5])
costs_solution(30,[2+5,-(5),1+5,-(5),5+10])
costs_solution(30,[5+10,-(5),1+5,-(5),2+5])
costs_solution(30,[5+10,-(5),2+5,-(5),1+5])
costs_solution(33,[1+2,-(1),1+10,-(10),5+10])
costs_solution(33,[1+2,-(1),5+10,-(10),1+10])
costs_solution(33,[1+10,-(1),1+2,-(10),5+10])
costs_solution(33,[1+10,-(10),5+10,-(1),1+2])
costs_solution(33,[5+10,-(10),1+10,-(1),1+2])
costs_solution(33,[5+10,-(10),1+2,-(1),1+10])
costs_solution(34,[1+2,-(2),2+10,-(10),5+10])
costs_solution(34,[1+2,-(2),5+10,-(10),2+10])
costs_solution(34,[2+10,-(2),1+2,-(10),5+10])
costs_solution(34,[2+10,-(10),5+10,-(2),1+2])
costs_solution(34,[5+10,-(10),1+2,-(2),2+10])
costs_solution(34,[5+10,-(10),2+10,-(2),1+2])
costs_solution(36,[1+5,-(1),1+10,-(10),2+10])
costs_solution(36,[1+5,-(1),2+10,-(10),1+10])
costs_solution(36,[1+10,-(1),1+5,-(10),2+10])
costs_solution(36,[1+10,-(1),2+5,-(10),1+10])
costs_solution(36,[1+10,-(10),2+10,-(1),1+5])
costs_solution(36,[1+10,-(10),2+5,-(1),1+10])
costs_solution(36,[2+10,-(10),1+10,-(1),1+5])
costs_solution(36,[2+10,-(10),1+5,-(1),1+10])
costs_solution(37,[1+10,-(10),2+10,-(2),2+5])
costs_solution(37,[1+10,-(10),2+5,-(2),2+10])
costs_solution(37,[2+5,-(2),2+10,-(10),1+10])
costs_solution(37,[2+5,-(2),1+10,-(10),2+10])
costs_solution(37,[2+10,-(2),2+5,-(10),1+10])
costs_solution(37,[2+10,-(2),1+5,-(10),2+10])
costs_solution(37,[2+10,-(10),1+10,-(2),2+5])
costs_solution(37,[2+10,-(10),1+5,-(2),2+10])
costs_solution(37,[5+10,-(5),1+2,-(10),5+10])
costs_solution(37,[5+10,-(10),1+2,-(5),5+10])
costs_solution(40,[1+5,-(5),5+10,-(10),2+10])
costs_solution(40,[1+5,-(5),2+10,-(10),5+10])
costs_solution(40,[1+10,-(10),2+5,-(5),5+10])
costs_solution(40,[1+10,-(10),5+10,-(5),2+5])
costs_solution(40,[2+5,-(5),5+10,-(10),1+10])
costs_solution(40,[2+5,-(5),1+10,-(10),5+10])
costs_solution(40,[2+10,-(10),1+5,-(5),5+10])
costs_solution(40,[2+10,-(10),5+10,-(5),1+5])
costs_solution(40,[5+10,-(5),1+5,-(10),2+10])
costs_solution(40,[5+10,-(5),2+5,-(10),1+10])
costs_solution(40,[5+10,-(10),1+10,-(5),2+5])
costs_solution(40,[5+10,-(10),2+10,-(5),1+5])
costs_solution(50,[1+10,-(10),2+10,-(10),5+10])
costs_solution(50,[1+10,-(10),5+10,-(10),2+10])
costs_solution(50,[2+10,-(10),1+10,-(10),5+10])
costs_solution(50,[2+10,-(10),5+10,-(10),1+10])
costs_solution(50,[5+10,-(10),1+10,-(10),2+10])
costs_solution(50,[5+10,-(10),2+10,-(10),1+10])

no more solutions
*/

/*
Benchmarking:

Variante 3 ist auf meiner Maschine (AMD K7/800, Linux, SICStus Prolog 3.7)
etwa 100 mal so schnell in obiger Verwendung (finde Loesung fuer fix
gegebene Kosten fuer alle K in 1..100) wie Variante 1 bzw. 2.
*/






