tpProlog/anerouge/anerougeAssoc.pl

   1 /* accesseurs sur ligne et colonne*/
   2 :-use_module(library(assoc)).
   3
   4 /* [d,b,g,h] */
   5     piece(ro,[[(2,0),(2,1)],[(0,2),(1,2)],[(-1,0),(-1,1)],[(0,-1),(1,-1)]],
   6           [[(0,0),(0,1)],[(0,0),(1,0)],[(1,0),(1,1)],[(0,1),(1,1)]]).
   7     piece(j1,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
   8           [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
   9     piece(j2,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
  10           [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
  11     piece(n1,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
  12           [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
  13     piece(n2,[[(1,0),(1,1)],[(0,2)],[(-1,0),(-1,1)],[(0,-1)]],
  14           [[(0,0),(0,1)],[(0,0)],[(0,0),(0,1)],[(0,1)]]).
  15     piece(bl,[[(2,0)],[(0,1),(1,1)],[(-1,0)],[(0,-1),(1,-1)]],
  16           [[(0,0)],[(0,0),(1,0)],[(1,0)],[(0,0),(1,0)]]).
  17     piece(b1,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
  18           [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
  19     piece(b2,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
  20           [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
  21     piece(m1,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
  22           [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
  23     piece(m2,[[(1,0)],[(0,1)],[(-1,0)],[(0,-1)]],
  24           [[(0,0)],[(0,0)],[(0,0)],[(0,0)]]).
  25
  26 direction(d,0,(1,0)).
  27 direction(b,1,(0,1)).
  28 direction(g,2,(-1,0)).
  29 direction(h,3,(0,-1)).
  30
  31
  32 case(Conf,Coord,P) :-
  33     gen_assoc(P,Conf,Coord).
  34
  35
  36 plus_binaire((X1,Y1),(X2,Y2),(Xp,Yp)):-
  37     Xp is X1 + X2,
  38     Yp is Y1 + Y2.
  39
  40 est_vide(v1).
  41 est_vide(v2).
  42
  43 deplace_vide(Conf,Conf,[],[]).
  44 deplace_vide(Conf,ConR,[V|Lvide],[Coord|Lcoord]):-
  45     deplace_vide(Conf,ConRp,Lvide,Lcoord),
  46     put_assoc(V,ConRp,Coord,ConR).
  47
  48
  49 /*tous les glissements */
  50 glissement(P,D,Conf1,Conf2):-
  51     piece(P,TestVides,NouvVides),
  52     case(Conf1,Coord,P),
  53     direction(D,Idx,DeltaCoord),
  54     nth0(Idx,TestVides,Delta),
  55     nth0(Idx,NouvVides,NVp),
  56     plus_binaire(DeltaCoord,Coord,NCoord),
  57     maplist(plus_binaire(Coord),Delta,L),
  58     maplist(plus_binaire(Coord),NVp,Lp),
  59     maplist(case(Conf1),L,LVp),
  60     maplist(est_vide,LVp),
  61     put_assoc(P,Conf1,NCoord,Conf1b),
  62     deplace_vide(Conf1b,Conf2,LVp,Lp).
  63
  64
  65
  66 gl_time(P,D,Confa,Confb):-
  67     get_time(T2),
  68     glissement(P,D,Confa,Confb),
  69     get_time(T3),
  70     DT3 is T3 - T2,
  71     write('depl : '),writeln(DT3).
  72
  73     /* Tous les successeurs d une configuration */
  74     successeurs(Confa-Chemins,L):-
  75     findall(
  76         Confb-[(P,D)|Chemins],
  77         glissement(P,D,Confa,Confb),
  78         L).
  79
  80 successeurs_liste(L,Sl):-
  81     maplist(successeurs,L,Lp),
  82     flatten(Lp,Lpp),
  83     list_to_assoc(Lpp,A),
  84     assoc_to_list(A,Sl).
  85
  86
  87
  88 /* regarde si le premier parametre appartient
  89      à la liste donné en second parametre. Si c est le cas,
  90     retourne le chemin */
  91
  92
  93
  94
  95
  96
  97 appartient(Conf1-_,[Conf1-_|_]):-!.
  98 appartient(Conf1-C,[_|L]):-
  99     appartient(Conf1-C,L).
 100
 101
 102 difference([],_,[]).
 103 difference([El|L1],L2,Res):-
 104     appartient(El,L2),
 105     !,
 106     difference(L1,L2,Res).
 107 difference([El|L1],L2,[El|Res]):-
 108     difference(L1,L2,Res).
 109
 110
 111
 112
 113
 114
 115 but([Conf-Chemin|_],Chemin):-final(Conf),!.
 116 but([_|L],Chemin):-but(L,Chemin).
 117
 118
 119 largeur(Atraiter,_,_,Res):-
 120     but(Atraiter,Res),
 121     !.
 122 largeur(Atraiter,Visites,C,Res):-
 123     Cp is C+1,
 124     write('boucle'), writeln(C),
 125     get_time(T0),
 126     successeurs_liste(Atraiter,Succ),
 127     length(Succ,Taille),
 128     write('taille succ : '),writeln(Taille),
 129     get_time(T1),
 130     DT1 is T1 - T0,
 131     append(Atraiter,Visites,Visites2),
 132     get_time(T2),
 133     difference(Succ,Visites2,Atraiter2),
 134     get_time(T3),
 135     DT3 is T3 - T2,
 136     write('successeur : '),writeln(DT1),
 137     write('difference : '),writeln(DT3),
 138     largeur(Atraiter2,Visites2,Cp,Res).
 139
 140 resoud(Res):-
 141     init(X),
 142     largeur([X-[]],[],0,Res).
 143
 144
 145 /*
 146 init(X):-
 147     list_to_assoc([
 148         j1-(0,0),
 149         j2-(3,0),
 150         ro-(1,0),
 151         n1-(0,2),
 152         n2-(3,2),
 153         bl-(1,2),
 154         m1-(0,4),
 155         m2-(3,4),
 156         b1-(1,3),
 157         b2-(2,3),
 158         v1-(1,4),
 159         v2-(2,4)],X).
 160 */
 161
 162 init(X):-
 163     list_to_assoc([
 164         j1-(0,0),
 165         j2-(3,0),
 166         ro-(1,0),
 167         n1-(0,2),
 168         n2-(3,2),
 169         bl-(1,2),
 170         m1-(0,4),
 171         m2-(3,4),
 172         b1-(1,3),
 173         b2-(2,3),
 174         v1-(1,4),
 175         v2-(2,4)],X).
 176
 177
 178 final(X):-
 179     gen_assoc(n1,X,(1,3)),
 180     gen_assoc(n2,X,(2,3)),!.
 181 final(X):-
 182     gen_assoc(n2,X,(1,3)),
 183     gen_assoc(n1,X,(2,3)).
 184
 185
 186
 187 /*final(X):-
 188     gen_assoc(bl,X,(2,2)),
 189     gen_assoc(m2,X,(2,4)),
 190     gen_assoc(n2,X,(3,3)).
 191 */
 192
 193
 194
 195
 196 /*
 197 init([
 198     [j1,r1,ro,j1],
 199     [ja,ro,ro,ja],
 200     [n1,b1,bl,n1],
 201     [no,bo,bo,no],
 202     [ma,vi,vi,ma]]).
 203
 204 final([
 205     [_,_,_,_],
 206     [_,_,_,_],
 207     [_,_,_,_],
 208     [_,_,_,_],
 209     [_,b1,bl,_]]).
 210
 211 final([
 212     [_,_,_,_],
 213     [_,_,_,_],
 214     [_,_,_,_],
 215     [_,_,_,_],
 216     [_,b1,bl,_]]).
 217
 218
 219 final([
 220     [j1,r1,ro,j1],
 221     [ja,ro,ro,ja],
 222     [n1,bo,b1,bl],
 223     [no,ma,vi,n1],
 224     [ma,vi,bo,no]]).
 225     */