% OTTUCSAK GYORGY (AULMAG) DP-PROLOG Nagyhazi feladat % 2001.05.17 % :- type fLeiro ---> satrak(sSzS, sSzO, list(parc)). % :- type sSzS == list(int). % :- type sSzO == list(int). % :- type parc == int-int. % :- type irany ---> n % észak % ; e % kelet % ; s % dél % ; w. % nyugat % :- type sHelyek == list(irany). % :- pred satrak(fLeiro::in, sHelyek::out). % % A feladat specifikációnak megfelően a kapott adatokból visszaadaja az % megoldásokat. satrak(satrak(Ss,Os,F),Ki) :- kerthossza(Ss,N), kerthossza(Os,M), sator_helyek(N,M,F,F,Shl), kereses2(Shl,[0|Ss],Os,N,M,[],Ki,[]). %kerthossza(+L,?N) L lista hossza N kerthossza([_|L],N) :- kerthossza(L,N1),N is N1+1. kerthossza([],0). % kereses2(+Shl, +Ss, +Os, +N, +M, +S0, ?S, +Sl). % N sorok száma,M oszlopok száma % amiből visszaadjuk a S2-t a Sátrak elhelyezkedésének listáját % S0 akkumlátor % Sl az eddig elhelyezet sátrak listája % Sh sátor_helyek listája kereses2([[Y-X-Z|L1]|Sh], Ss, Os, N, M, S0, S, Sl ) :- holafaja(Y-Z,Y1), eddigjo(Y1,Ss,UjSs), lehelyez([Y-X-Z|L1], Sh, UjSs, Os, N, M, S0, S, Sl). kereses2([], [_|Ss], Os,_, _, S0, S, _) :- ellenorzes(Ss), ellenorzes(Os), reverse(S,S0). %lehelyez(+Satorlis,+MaradekSatorlis,+Ss,+Os,+N,+M,+S0,?S,+Sl) %Satorlis : Az aktuális fához tartozó sátorhelyek %MaradekSatorlis : A maradék fákhoz tartozó sátorlisták %N : kert magassága %M : kert hossza %S0: Akku %S : Eredmény %Sl: Az eddig letett sátrak listája lehelyez([Y-X-Z|_], Sh, Ss, Os, N, M, S0, S, Sl) :- sator_vizsgalat(Sl,Y-X), tag2(X, Os, Os2), tag3(Y, Ss, Ss2), kereses2(Sh,Ss2,Os2, N, M, [Z|S0],S,[Y-X|Sl]). lehelyez([_-_-_,Y-X-Z|_], Sh, Ss, Os, N, M, S0, S, Sl) :- sator_vizsgalat(Sl,Y-X), tag2(X, Os, Os2), tag3(Y, Ss, Ss2), kereses2(Sh,Ss2,Os2, N, M, [Z|S0],S,[Y-X|Sl]). lehelyez([_-_-_,_-_-_,Y-X-Z|_], Sh, Ss, Os, N, M, S0, S, Sl) :- sator_vizsgalat(Sl,Y-X), tag2(X, Os, Os2), tag3(Y, Ss, Ss2), kereses2(Sh,Ss2,Os2, N, M, [Z|S0],S,[Y-X|Sl]). lehelyez([_-_-_,_-_-_,_-_-_,Y-X-Z], Sh, Ss, Os, N, M, S0, S, Sl) :- sator_vizsgalat(Sl,Y-X), tag2(X, Os, Os2),tag3(Y,Ss, Ss2), kereses2(Sh,Ss2,Os2, N, M, [Z|S0],S,[Y-X|Sl]). % ellenorzes(+L) %L lista minden eleme kisebb,mint 1. ellenorzes([]) :- true. ellenorzes([A|L]) :- A=<0,!,ellenorzes(L). %eddigjo(+Y, +L, ?LevagottLista) %Ss lista Y-2 eleméig kisebb-e, mint 1, Y-2 alatti elemek levágásával kapott lista . eddigjo(Y,[Hely|Ss],LevagottSs) :- (Y>2 -> Ujhely is Y-2,Y1 is Ujhely-Hely,ures(Y1,Ss,Levagott),LevagottSs=[Ujhely|Levagott] %UjHely=hány elemet vágtunk le ;LevagottSs=[Hely|Ss],true ). %ures(+S, +L, ?Levagott) % L S eleméig kisebb-e, mint 1, ha igen első S elemet levágja. ures(S,[A|L],Levagott) :- S\==0,!,A=<0,!,S1 is S-1,ures(S1,L,Leva), Levagott=Leva. ures(0,L,L) :- true. % holfaja(+Y-Irany, ?Y1) % Y sátor y_koordinátája % Irany a sátor helyzete a fához képest % Y1 a fa y_koordinátája % Y és Irany segítségével kiszámolja Y1-et % (Y1=Y+(1,0,-1)) holafaja(Y-n,Y1) :- Y1 is Y+1. holafaja(Y-w,Y). holafaja(Y-e,Y). holafaja(Y-s,Y1) :- Y1 is Y-1. % tag2(+X, +L, ?V) L lista X. elemet nezi meg, ha az 0, akkor hamis erteket ad vissza, % ha nem, akkor V listat adja vissza V=[l1,l2..,lX-1,...], ami csak az az X. elemében %tér el a L listától VX=LX-1. tag2(S,[A|L],V) :- S\==1,!, S1 is S-1, tag2(S1,L,V1), V=[A|V1]. tag2(1,[A|L],V) :- A\==0,!, A1 is A-1, V=[A1|L]. %tag3(+X, +L, ?V) ugyanazt csinálja, mint tag2/3 csak itt az első tag a levagott elemek % számát jelenti tag3(S,[A|L],V) :- S1 is S-A,tag2(S1,L,V1),V=[A|V1]. % sator_vizsgalat(+Sl,+ U) A U sátorhelyet megviszgálja, hogy nincs-e túl közel egy a másik % sátorhoz, ha nincs, akkor igaz külöben hamis értéket ad. % --- % -S- % --- % -=itt nem lehet sátor sator_vizsgalat([Y-X|L],Y1-X1) :- (Y-Y1)*(Y-Y1)+(X-X1)*(X-X1)> 2,!,sator_vizsgalat(L,Y1-X1). sator_vizsgalat([],_-_) :- true. % :- type N == int. % :- type M == int. % :- type F == list(parc). % :- type Fe == list(parc). % :- type Shl == list(list(parc2)). % :- type parc2 == int-int-irany. % :- pred sator_helyek(N::in, M::in, F::in, Fe::in, Shl::out). % % N kert szélesség és M kert hosszúság segítségével kiszámolja az egyes fákhoz % (F) tartozó sátrak lehetséges helyeit ,csak azt vizsgálva, hogy a kert szélén % van-e vagy nem (a fa), majd még kihúzza azokat is melyek egy fára kerültek vol % -na, a memberfa2/3 predikátum segítségével. A meberfa2/3 perdikátum használata % miatt van szükség az Fe-re(eredeti falista), amely ezt használja a kereséshez. %balfelső sator_helyek(N,M,[1-1|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), memberfa2(Fe,[1-2-e,2-1-s],V), Sh=[V|Sh1],!. %balalsó sator_helyek(N,M,[N-1|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1),N1 is N-1, memberfa2(Fe,[N1-1-n,N-2-e],V),Sh=[V|Sh1],!. %jobbalsó sator_helyek(N,M,[N-M|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), N1 is N-1,M1 is M-1,memberfa2(Fe,[N1-M-n,N-M1-w],V),Sh=[V|Sh1],!. %jobbfelső sator_helyek(N,M,[1-M|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), M1 is M-1,memberfa2(Fe,[1-M1-w,2-M-s],V), Sh=[V|Sh1],!. %oldalakara % nyugati oldalon sator_helyek(N,M,[Y-1|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), Y1 is Y-1,Y2 is Y+1,memberfa2(Fe,[Y1-1-n,Y-2-e,Y2-1-s],V), Sh=[V|Sh1],!. % déli oldalon sator_helyek(N,M,[N-X|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), X1 is X-1,X2 is X+1,N1 is N-1,memberfa2(Fe,[N1-X-n,N-X1-w,N-X2-e],V), Sh=[V|Sh1],!. % keleti oldalon sator_helyek(N,M,[Y-M|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), Y1 is Y-1,Y2 is Y+1,M1 is M-1,memberfa2(Fe,[Y1-M-n,Y-M1-w,Y2-M-s],V), Sh=[V|Sh1],!. % északi oldalon sator_helyek(N,M,[1-X|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), X1 is X-1,X2 is X+1,memberfa2(Fe,[1-X1-w,1-X2-e,2-X-s],V), Sh=[V|Sh1],!. %középen sator_helyek(N,M,[Y-X|F],Fe,Sh) :- sator_helyek(N,M,F,Fe,Sh1), X1 is X-1, X2 is X+1, Y1 is Y-1, Y2 is Y+1, memberfa2(Fe,[Y1-X-n,Y-X1-w,Y-X2-e,Y2-X-s],V), Sh=[V|Sh1],!. %vége sator_helyek(_N,_M,[],_,[]). %memberfa2(+F,+Sl,?Msl) %A F és a Sl listában egyező A-B párokat kihagyja a Mslből(Maradék sátor listából). memberfa2([Y-X|S],[Y-X-_|L],V) :- memberfa2(S,L,V). %egyforma akkor kimarad memberfa2([A-B|S],[Y-X-Z|L],V) :- (A>Y -> memberfa2([A-B|S],L,V1), %következő fa jön V=[Y-X-Z|V1] ; A=Y -> (B>X,memberfa2([A-B|S],L,V1),V=[Y-X-Z|V1] %következő fa jön ;memberfa2(S,[Y-X-Z|L],V)%következő sátor jön ) ; memberfa2(S,[Y-X-Z|L],V) % A