%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

prod([],1).
prod([X|L],P):- prod(L,P1), P is P1*X.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

pescalar([],[],0).
pescalar([X|L1],[Y|L2],P):- pescalar(L1,L2,P1), P is P1+X*Y.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

interseccio([],_,[]).
interseccio([X|L1],L2,[X|L3]):- pert(X,L2),!, interseccio(L1,L2,L3).
interseccio([_|L1],L2,   L3 ):-               interseccio(L1,L2,L3).

unio([],L,L).
unio([X|L1],L2,   L3 ):- pert(X,L2),!, unio(L1,L2,L3).
unio([X|L1],L2,[X|L3]):-               unio(L1,L2,L3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ultim(L,X):- concat(_,[X],L).

invers([],[]).
invers(L,[X|L1]):- concat(L2,[X],L), invers(L2,L1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fib(1,1):-!.
fib(2,1):-!.
fib(N,F):-
        %N>2,
        N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

daus(0,0,[]).
daus(P,N,[X|L]):-
        N>0,
        pert(X,[1,2,3,4,5,6]), Q is P-X, M is N-1, daus(Q,M,L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

simplifica(E,E1):- unpaso(E,E2),!, simplifica(E2,E1).
simplifica(E,E).

unpaso(A+B,A+C):- unpaso(B,C).
unpaso(B+A,C+A):- unpaso(B,C).
unpaso(A*B,A*C):- unpaso(B,C).
unpaso(B*A,C*A):- unpaso(B,C).
unpaso(0*_,0).
unpaso(_*0,0).
unpaso(1*X,X).
unpaso(X*1,X).
unpaso(0+X,X).
unpaso(X+0,X).
unpaso(N1+N2,N3):- number(N1), number(N2), N3 is N1+N2.
unpaso(N1*N2,N3):- number(N1), number(N2), N3 is N1*N2.
unpaso(N1*X+N2*X,N3*X):- number(N1), number(N2), N3 is N1+N2.
unpaso(N1*X+X*N2,N3*X):- number(N1), number(N2), N3 is N1+N2.
unpaso(X*N1*X+N2*X,N3*X):- number(N1), number(N2), N3 is N1+N2.
unpaso(X*N1*X+X*N2,N3*X):- number(N1), number(N2), N3 is N1+N2.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ord([],[]).
ord([X|L],L1):- ord(L,L2), inserccio(X,L2,L1).
insercion(X,[],[X]).
insercion(X,[Y|L],[X,Y|L]):- X=<Y.
insercion(X,[Y|L],[Y|L1]):-  X> Y, insercion(X,L,L1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

dicc(A,N):-  nmembers(A,N,S), escribir(S), fail.
dicc(_,_) :- nl.

pert(X,[X|_]).
pert(X,[_|Y]) :- pert(X,Y). 

nmembers(_,0,[]):-!.
nmembers(L,N,[X|S]):- pert(X,L), N1 is N-1, nmembers(L,N1,S).

escribir([]):-write(' ').
escribir([X|L]):- write(X), escribir(L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

suma([],[],[],C,C).
suma([X1|L1],[X2|L2],[X3|L3],Cin,Cout) :-
	X3 is (X1 + X2 + Cin) mod 10,
	C  is (X1 + X2 + Cin) //  10,
	suma(L1,L2,L3,C,Cout).


send_more_money1 :-

	L = [S, E, N, D, M, O, R, Y, _, _],
	permutacion(L, [0,1,2,3,4,5,6,7,8,9]),
	suma([D, N, E, S], [E, R, O, M], [Y, E, N, O], 0, M),

	write('S = '), write(S), nl,
	write('E = '), write(E), nl,
	write('N = '), write(N), nl,
	write('D = '), write(D), nl,
	write('M = '), write(M), nl,
	write('O = '), write(O), nl,
	write('R = '), write(R), nl,
	write('Y = '), write(Y), nl,
	write('  '), write([S,E,N,D]), nl,
	write('  '), write([M,O,R,E]), nl,
	write('-------------------'), nl,
	write([M,O,N,E,Y]), nl.


send_more_money2 :-

	L = [0,1,2,3,4,5,6,7,8,9],
	pertany_amb_resta(M,  [0,1], _),
	pertany_amb_resta(M,  L,  L0),
	pertany_amb_resta(O, L0, L1),
	pertany_amb_resta(R, L1, L2),
	pertany_amb_resta(Y, L2, L3),
	pertany_amb_resta(S, L3, L4),
	pertany_amb_resta(E, L4, L5),
	pertany_amb_resta(N, L5, L6),
	pertany_amb_resta(D, L6, _),
	suma([D, N, E, S], [E, R, O, M], [Y, E, N, O], 0, M),

	write('S = '), write(S), nl,
	write('E = '), write(E), nl,
	write('N = '), write(N), nl,
	write('D = '), write(D), nl,
	write('M = '), write(M), nl,
	write('O = '), write(O), nl,
	write('R = '), write(R), nl,
	write('Y = '), write(Y), nl,
	write('  '), write([S,E,N,D]), nl,
	write('  '), write([M,O,R,E]), nl,
	write('-------------------'), nl,
	write([M,O,N,E,Y]), nl.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% pert(X,[X|_]).
% pert(X, [_|L]) :- pert(X, L). % OK!

concat([],L,L).
concat([X|L1],L2,[X|L3]) :- concat(L1, L2, L3).

pert(X,L) :- concat(_, [X|_], L).

fact(0, 1) :- !.
fact(N, F) :-
	N1 is N-1,
	fact(N1, F1),
	F is N*F1.

nat(0).
nat(N) :- nat(N1), N is N1 + 1.

mcm(X,Y,M) :- nat(N), N>0, M is N*X, 0 is M mod Y.

pert_amb_resta(X,L,R) :- concat(L1,[X|L2],L), concat(L1,L2,R).

long([], 0).
long([_|L1], N) :- long(L1, N1), N is N1 + 1.

factors_primers(1, []) :- !.
factors_primers(N, [F|L]) :-
	nat(F),
	F > 1,
	0 is N mod F,
	N1 is N // F,
	factors_primers(N1, L),
	!.

perm([], []).
perm(L, [X|P]) :- pert_amb_resta(X,L,R), perm(R,P).

%subcjt([], []). % subcjt(L,S): S es subconjunt d'L
%subcjt([_|_], []).
%subcjt(L,[X|S]) :- pert_amb_resta(X,L,R), subcjt(R,S).

subcjt([], []).
subcjt([X|C], [X|S]) :- subcjt(C, S).
subcjt([_|C], S) :- subcjt(C, S).

% --- PROG. EXEMPLE: ---
expr([X], X).
expr(L,E1+E2) :- concat(L1,L2,L), L1 \= [], L2 \= [], expr(L1,E1), expr(L2,E2).
expr(L,E1-E2) :- concat(L1,L2,L), L1 \= [], L2 \= [], expr(L1,E1), expr(L2,E2).
expr(L,E1*E2) :- concat(L1,L2,L), L1 \= [], L2 \= [], expr(L1,E1), expr(L2,E2).

xifres(L,N) :- subcjt(L, S), perm(S,P), expr(P, E), N is E, write(E), nl, fail.

% --- EXERCICIS: ---

prod([], 1).
prod([X|L], P) :- prod(L, P1), P is P1*X.

pescalar([], [], 0).
pescalar([X1|L1], [X2|L2], P) :- pescalar(L1, L2, P1), P is P1 + X1*X2.

intersecc([], _, []).
intersecc([X|L1], L2, [X|L]) :- pert(X, L2), !, intersecc(L1, L2, L).
intersecc([_|L1], L2, L) :- intersecc(L1, L2, L).

unio([], L, L).
unio([X|L1], L2, L3) :- pert(X, L2), !, unio(L1, L2, L3).
unio([X|L1], L2, [X|L3]) :- unio(L1, L2, L3).

% ultim([X], X) :- !.
% ultim([_|L], U) :- ultim(L, U).

ultim(L, X) :- concat(_, [X], L), !.

inversa([], []).
inversa(L, [X|L1]) :- concat(L2, [X], L), inversa(L2, L1).

%fib(N, 1) :- N =< 2, !.
fib(1, 1) :- !.
fib(2, 1) :- !.
fib(N, F) :- N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1+F2.

daus(0, 0, []).
daus(P, N, [X|L]) :- N > 0, pert(X, [1,2,3,4,5,6]), P1 is P-X, N1 is N-1, daus(P1, N1, L).

suma([], 0).
suma([X|L], N) :- suma(L, N1), N is X+N1.
suma_demes(L) :- pert(X,L), suma(L, S1), S is S1-X, X = S, !.

suma_anteriors(L) :- concat(L1, [X|_], L), suma(L1, X).

uniq([], []).
uniq([X|L], L1) :- pert(X, L), !, uniq(L, L1).
uniq([X|L], [X|L1]) :- uniq(L, L1).
count(_, [], 0).
count(X, [X|L], N) :- count(X, L, N1), N is N1+1, !.
count(X, [_|L], N) :- count(X, L, N).
card(L) :- uniq(L, U), pert(X, U), count(X, L, N), write([X, N]), nl, fail.
card(_).

% Albert B.:
% card([], []).
% card([X|L],[[X,M]|R]) :- pert(X, L), !, card(L, L2),
%                          pert_amb_resta([X,N], L2, R), M is N+1.
% card([X|L], [[X,1]|L2]) :- card(L, L2).

esta_ordenada([]).
esta_ordenada([_]) :- !.
esta_ordenada([X,Y|L]) :- X =< Y, esta_ordenada([Y|L]), !.

ordenada(L1, L2) :- perm(L1, L2), esta_ordenada(L2), !.
% Pitjor cas: fact mida(L1)

insert(X, [], [X]) :- !.
insert(X, [Y|L], [X,Y|L]) :- X =< Y, !.
insert(X, [Y|L1], [Y|Li]) :- insert(X, L1, Li).
ordenada2([], []).
ordenada2([X|L1], L2) :- ordenada2(L1, L3), insert(X, L3, L2).
% Pitjor cas: N^2 (polinomica: quadratica)

%ordenada3([], []) :- !.
%ordenada3([X], [X]) :- !.
%ordenada3(L, Lo) :- L = [_,_|_], concat(L1, L2, L), !, ordenada3(L1, Lo1),
%	ordenada3(L2, Lo2), concat(Lo1, Lo2, Lo), !.
% Pitjor cas: N*log(N)
% FAIL!!!!!

nmembers(_, 0, []) :- !.
nmembers(A, N, [X|L]) :- pert(X, A), N1 is N-1, nmembers(A, N1, L).
writeword([]) :- write(' '), !.
writeword([X|L]) :- write(X), writeword(L).
dict(A, N) :- nmembers(A, N, L), writeword(L), fail.

es_palindrom([]) :- !.
es_palindrom([_]) :- !.
es_palindrom(L) :- concat([X|L1], [X], L), es_palindrom(L1), !.
palind(L) :- perm(L, P), es_palindrom(P), write(P), nl, fail.
% FAIL: elements repetits!

catchall(_).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%