/* accesseurs sur ligne et colonne*/
:-use_module(library(assoc)).

/* [d,b,g,h] */
    piece(ro,[[(2,0),(2,1)],[(0,2),(1,2)],[(-1,0),(-1,1)],[(0,-1),(1,-1)]],
	  [[(0,0),(0,1)],[(0,0),(1,0)],[(1,0),(1,1)],[(0,1),(1,1)]]).
    piece(j1,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
	  [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
    piece(j2,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
	  [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
    piece(n1,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
	  [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
    piece(n2,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
	  [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
    piece(bl,[[(2,0)],[(0,1),(1,1)],[(-1,0)],[(0,-1),(1,-1)]],
	  [[(0,0)],[(0,0),(1,0)],[(1,0)],[(0,0),(1,0)]]).
    piece(b1,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
	  [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
    piece(b2,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
	  [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
    piece(m1,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
	  [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
    piece(m2,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
	  [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
    
direction(d,0,(1,0)).
direction(b,1,(0,1)).
direction(g,2,(-1,0)).
direction(h,3,(0,-1)).

    
case(Conf,Coord,P) :- 
    gen_assoc(P,Conf,Coord).


plus_binaire((X1,Y1),(X2,Y2),(Xp,Yp)):-
    Xp is X1 + X2,
    Yp is Y1 + Y2.

est_vide(v1).
est_vide(v2).

deplace_vide(Conf,Conf,[],[]).
deplace_vide(Conf,ConR,[V|Lvide],[Coord|Lcoord]):-
    deplace_vide(Conf,ConRp,Lvide,Lcoord),
    put_assoc(V,ConRp,Coord,ConR).


/*tous les glissements */
glissement(P,D,Conf1,Conf2):-
    piece(P,TestVides,NouvVides),      
    case(Conf1,Coord,P),
    direction(D,Idx,DeltaCoord),
    nth0(Idx,TestVides,Delta),
    nth0(Idx,NouvVides,NVp),
    plus_binaire(DeltaCoord,Coord,NCoord),
    maplist(plus_binaire(Coord),Delta,L),
    maplist(plus_binaire(Coord),NVp,Lp),
    maplist(case(Conf1),L,LVp),
    maplist(est_vide,LVp),
    put_assoc(P,Conf1,NCoord,Conf1b),
    deplace_vide(Conf1b,Conf2,LVp,Lp).
    
    

gl_time(P,D,Confa,Confb):-
    get_time(T2),
    glissement(P,D,Confa,Confb),
    get_time(T3),
    DT3 is T3 - T2,
    write('depl : '),writeln(DT3).
    
    /* Tous les successeurs d une configuration */
    successeurs(Confa-Chemins,L):-
    findall(
	Confb-[(P,D)|Chemins],
	glissement(P,D,Confa,Confb),
	L).

successeurs_liste(L,Sl):-
    maplist(successeurs,L,Lp),
    flatten(Lp,Lpp),
    list_to_assoc(Lpp,A),
    assoc_to_list(A,Sl).



/* regarde si le premier parametre appartient 
     à la liste donné en second parametre. Si c est le cas,
    retourne le chemin */






appartient(Conf1-_,[Conf1-_|_]):-!.
appartient(Conf1-C,[_|L]):-
    appartient(Conf1-C,L).


difference([],_,[]).
difference([El|L1],L2,Res):-
    appartient(El,L2),
    !,
    difference(L1,L2,Res).
difference([El|L1],L2,[El|Res]):-
    difference(L1,L2,Res).






but([Conf-Chemin|_],Chemin):-final(Conf),!.
but([_|L],Chemin):-but(L,Chemin).


largeur(Atraiter,_,_,Res):-
    but(Atraiter,Res),
    !.
largeur(Atraiter,Visites,C,Res):-
    Cp is C+1,
    write('boucle'), writeln(C),
    get_time(T0),
    successeurs_liste(Atraiter,Succ),
    length(Succ,Taille),
    write('taille succ : '),writeln(Taille),
    get_time(T1),
    DT1 is T1 - T0,
    append(Atraiter,Visites,Visites2),
    get_time(T2),
    difference(Succ,Visites2,Atraiter2),
    get_time(T3),
    DT3 is T3 - T2,
    write('successeur : '),writeln(DT1),
    write('difference : '),writeln(DT3),
    largeur(Atraiter2,Visites2,Cp,Res).

resoud(Res):-
    init(X),
    largeur([X-[]],[],0,Res).


/*
init(X):-
    list_to_assoc([
	j1-(0,0),
	j2-(3,0),       
	ro-(1,0),
	n1-(0,2),
	n2-(3,2),
	bl-(1,2),
	m1-(0,4),
	m2-(3,4),
	b1-(1,3),
	b2-(2,3),
	v1-(1,4),
	v2-(2,4)],X).
*/

init(X):-
    list_to_assoc([
	j1-(0,0),
	j2-(3,0),       
	ro-(1,0),
	n1-(0,2),
	n2-(3,2),
	bl-(1,2),
	m1-(0,4),
	m2-(3,4),
	b1-(1,3),
	b2-(2,3),
	v1-(1,4),
	v2-(2,4)],X).


final(X):-
    gen_assoc(n1,X,(1,3)),
    gen_assoc(n2,X,(2,3)),!.
final(X):-
    gen_assoc(n2,X,(1,3)),
    gen_assoc(n1,X,(2,3)).



/*final(X):-
    gen_assoc(bl,X,(2,2)),
    gen_assoc(m2,X,(2,4)),
    gen_assoc(n2,X,(3,3)).
*/




/*
init([
    [j1,r1,ro,j1],
    [ja,ro,ro,ja],
    [n1,b1,bl,n1],
    [no,bo,bo,no],
    [ma,vi,vi,ma]]).

final([
    [_,_,_,_],
    [_,_,_,_],
    [_,_,_,_],
    [_,_,_,_],
    [_,b1,bl,_]]).

final([
    [_,_,_,_],
    [_,_,_,_],
    [_,_,_,_],
    [_,_,_,_],
    [_,b1,bl,_]]).


final([
    [j1,r1,ro,j1],
    [ja,ro,ro,ja],
    [n1,bo,b1,bl],
    [no,ma,vi,n1],
    [ma,vi,bo,no]]).
    */