/* exercice 2 */

/* question 1 */

/* version concise */

desc(L,D):-aux1(L,0,D).

aux([],_,[],0).
aux([N|L],N,H,C):-!,aux(L,N,H,C1),C is C1+1.
aux([M|L],N,[M|H],C):-aux(L,N,H,C).

aux1([],_,[]):-!.
aux1(L,N,[C|G]):-aux(L,N,H,C),M is N+1,aux1(H,M,G).


/* version plus explicite */ 

desc1(L,D):-maximum(L,M), N is M+1, auxi(L,N,0,D).


/* maximum(+liste,-entier) calcule le max de la liste */
maximum([],0).
maximum([X|L],Z):-maximum(L,Z), Z>X, !.
maximum([X|_],X).

/* count(+elem, +liste,-nombreoccurrences) calcule le nombre d'occurrences de 
elem dans liste */
count(_,[],0).
count(N,[N|L],M):-!,count(N,L,M1),M is M1+1.
count(N,[_|L],M):-count(N,L,M). 


/*auxi(+liste,+indicemax,+indicecourant,-descroption)   calcule la description de liste a partire de indicecourant et jusqu'a indicemax */
auxi(_,M,M,[]):-!.
auxi(L,M,N,[C|G]):-count(N,L,C), N1 is N+1, auxi(L,M,N1,G).

/* question 2 */


is_cyclic(L):-desc(L,G), cycle(L,G)

cycle(L,L):-!.
cycle(L,G):-desc(G,H), cycle(L,H).

/*exercice 3 */

/* question 1

Pour le jeu soustractif 1-2-3, play1(4,Y) echoue car 4 est perdante, et donc
not(wins(Z)) echoue pour ses successeurs 3, 2 et 1. Au contraire, play1(4,Y)
reussit et donne Y=3 car le premier mouvement est "-1".

*/

/* question 2 */

move(X,Y):-(X>0,Y is X-1);(X>1,Y is X-2);(X>2,Y is X-3).

mex(L,N):-aux(0,L,N).
aux(X,L,N):-member(X,L)->(Y is X+1,aux(Y,L,N)); N is X.

/* question 3 */

 mapsg([],[]).
 mapsg([X|L],[Y|H]):-sg(X,Y),mapsg(L,H).

sg(X,N):-setofnew(Y,move(X,Y),L),mapsg(L,H),mex(H,N).

 setofnew(X,Y,Z):- (setof(X,Y,Z),!);Z=[].
/* warning: problème si setof(Y,move(X,Y),L) est la liste vide car dans ce cas
    setof échoue au lieu de réussir avec L=[]. Ce problème a été ignoré dans la correction. Pour que sg fonctionne il faut remplacer setof par le prédicat 
    setofnew(X,Y,Z):- (setof(X,Y,Z),!);Z=[]
    */

/* question 4 */


play3(X,Y):-setof(Z,move(X,Z),L),mapsg(L,H),minaux(L,H,[Y,_]).

minaux([Z],[V],[Z,V]):-!.
minaux([Z|L],[V|H],R):-minaux(L,H,[Z1,V1]), (V<V1 -> R=[Z,V];R=[Z1,V1]).