:- use_module(library(lists), [nth/4]).

% `nth(?N, ?LIST, ?ELEMENT, ?REST)'
%     ELEMENT is in position N in the LIST and REST is all elements in
%     LIST except ELEMENT.

% satrak(+Leiro, -SatorHelyek): A Leiro által meghatározott sátor-feladvány
% megoldása a SatorHelyek égtájlista.
satrak(satrak(Sorosszegek, Oszloposszegek, Fahelyek), SatorHelyek) :-
	fatol1messze(Sorosszegek, Oszloposszegek, Fahelyek, Fahelyek, Szobajohet),
	kivalaszt(Sorosszegek, Oszloposszegek, Szobajohet, SatorHelyek).

% fatol1messze(+Sorosszegek, +Oszloposszegek, +Fahelyek, +MaradekFahelyek, -FakoruliHelyekLista):
% A MaradekFahelyek a fák helyeinek listája, a FakoruliHelyekLista az ennek megfelelö mezölisták listája,
% ahol a mezölista tartalmazza a megfelelö fa körüli lehetséges sátorhelyeket (0..4 elemü int-int list).
% Lehetséges sátorhelyek: a fával közös oldala van, nincs rajta fa, és a sorösszeg és oszlopösszeg is 0.
% A sátorhelyeket S-O-Et hármassal adjuk meg, ahol S a sor, O az oszlop, Et az égtáj.
fatol1messze(_, _, _, [], []).
fatol1messze(Sorosszegek, Oszloposszegek, Fahelyek, [Fa|Maradekfa], [Helyfakorul|Tobbifakorul]) :-
	length(Sorosszegek, Sorokszama), length(Oszloposszegek, Oszlopszam),
	fakorul4fele(Fa, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Sorokszama, Helyfakorul),
	fatol1messze(Sorosszegek, Oszloposszegek, Fahelyek, Maradekfa, Tobbifakorul).

% fakorul4fele(+FaHely, +Sorosszegek, +Oszloposszegek, +Fahelyek, +Oszlopszam, +Sorokszama, -Helyfakorul):
% A FaHely (int-int)-tel megadott fa körüli lehetséges sátorhelyek listáját tartalmazza a Helyfakorul.
% Lehetséges sátorhelyek: lásd feljebb.
fakorul4fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Sorokszama, Helyfakorul):-
	SS is FaS+1, SO is FaO, SS =< Sorokszama,
	\+ nth(SS, Sorosszegek, 0, _), \+ nth(SO, Oszloposszegek, 0, _),
	\+ nth(_, Fahelyek, SS-SO, _), !,
	Helyfakorul=[SS-SO-s|Hely3fele], fakorul3fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Hely3fele).
fakorul4fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, _, Fak):-
	fakorul3fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Fak).

% fakorul3fele(+FaHely, +Sorosszegek, +Oszloposszegek, +Fahelyek, +Oszlopszam, -Hely3fele):
% A FaHely (int-int)-tel megadott fa körüli olyan lehetséges sátorhelyek listáját tartalmazza a Hely3fele,
% amik a fától nyugatra, keletre vagy északra vannak.
fakorul3fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Hely3fele):-
	SS is FaS-1, SO is FaO, 1 =< SS,
	\+ nth(SS, Sorosszegek, 0, _), \+ nth(SO, Oszloposszegek, 0, _),
	\+ nth(_, Fahelyek, SS-SO, _), !,
	Hely3fele=[SS-SO-n|Hely2fele], fakorul2fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Hely2fele).
fakorul3fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Fak):-
	fakorul2fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Fak).

% fakorul2fele(+FaHely, +Sorosszegek, +Oszloposszegek, +Fahelyek, +Oszlopszam, -Hely2fele):
% A FaHely (int-int)-tel megadott fa körüli olyan lehetséges sátorhelyek listáját tartalmazza a Hely2fele,
% amik a fától nyugatra vagy keletre vannak.
fakorul2fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Oszlopszam, Hely2fele):-
	SS is FaS, SO is FaO+1, SO =< Oszlopszam,
	\+ nth(SS, Sorosszegek, 0, _), \+ nth(SO, Oszloposszegek, 0, _),
	\+ nth(_, Fahelyek, SS-SO, _), !,
	Hely2fele=[SS-SO-e|Helynyugatra], fatolnyugatra(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Helynyugatra).
fakorul2fele(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, _, Fak):-
	fatolnyugatra(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Fak).

% fatolnyugatra(+FaHely, +Sorosszegek, +Oszloposszegek, +Fahelyek, -Helynyugatra):
% A Helynyugatra tartalmazza a FaHely (int-int)-tel megadott fától nyugatra levö mezöt,
% ha az lehetséges sátorhely (nincs ott fa és a sorösszeg és oszlopösszeg ott nem 0).
% Különben a Helynyugatra egy üres lista marad.
fatolnyugatra(FaS-FaO, Sorosszegek, Oszloposszegek, Fahelyek, Helynyugatra):-
	SS is FaS, SO is FaO-1, 1 =< SO,
	\+ nth(SS, Sorosszegek, 0, _), \+ nth(SO, Oszloposszegek, 0, _),
	\+ nth(_, Fahelyek, SS-SO, _), !,
	Helynyugatra=[SS-SO-w].
fatolnyugatra(_, _, _, _, []).


% kivalaszt(+Sorosszegek, +Oszloposszegek, +FakoruliHelyekLista, -Satorhelyek):
% A FakoruliHelyekListáról feltételezzük, hogy leírja a szóbajöhetö fák körüli helyeket.
% Igy minden fához tartozik egy hozzá szóbajöhetö sátorveröhely-lista. A FakoruliHelyekLista ezek listája.
% A Satorhelyek visszaad ehhez egy helyes sátorelrendezést jellemző égtájlistát.
kivalaszt(Sorosszegek, Oszloposszegek, [], []):-
	nincspozitiv(Sorosszegek), nincspozitiv(Oszloposszegek).
kivalaszt(Sorosszegek, Oszloposszegek, [Helyfakorul|Szobajohet], [Egtaj|Satorhelyek]):-
	member(SatorS-SatorO-Egtaj, Helyfakorul),
	nth(SatorS, Sorosszegek, IndexS, _), nth(SatorO, Oszloposszegek, IndexO, _),
	IndexSuj is IndexS-1, IndexOuj is IndexO-1,
	nincskozel(SatorS-SatorO, IndexSuj, IndexOuj, Szobajohet, SzobajonUj),
	tagcsere(SatorS, Sorosszegek, UjSorosszeg), tagcsere(SatorO, Oszloposszegek, UjOszloposszeg),
	kivalaszt(UjSorosszeg, UjOszloposszeg, SzobajonUj, Satorhelyek).

% nincskozel(+Satorhely, +IndexS, +IndexO, +FakoruliHelyekLista, -Satorhelyek):
% A Satorhely egy (int-int)-tel megadott mezö, az IndexS a sorösszeg, az IndexO az oszlopösszeg abban a sorban/oszlopban.
% A FakoruliHelyekLista a többi fához tartozó helylista-lista, ami a Sátrohelyre való sátorverés előtt szóbajöhet,
% a Satorhelyek ugyanez a lista, de már csak azok a helyek vannak benne, amik a sátorverés után is szóba jöhetnek.
nincskozel(_, _, _, [], []).
nincskozel(SatS-SatO, IdxS, IdxO, [Helyfakorul|Szobajohet], [JoHelyek|SzobajonUj]):-
	csakjohely(SatS-SatO, IdxS, IdxO, Helyfakorul, JoHelyek),
	member(_, JoHelyek), !,
	nincskozel(SatS-SatO, IdxS, IdxO, Szobajohet, SzobajonUj).

% csakjohely(+Satorhely, +IdxS, +IdxO, +FakoruliHelyek, -JoHelyek):
% A Satorhely egy (int-int)-tel megadott mezö, az IndexS a sorösszeg, az IndexO az oszlopösszeg abban a sorban/oszlopban.
% A FakoruliHelyek egy bizonyos fa körüli jó sátorveröhely-lista, a JoHelyek ugyanez a lista, ha a Satorhelyre sátor került.
csakjohely(_, _, _, [], []).
csakjohely(SatS-SatO, IdxS, IdxO, [HS-HO-Egtaj|Helyfakorul], [HS-HO-Egtaj|JoHelyek]):-
	Tav1 is SatS-HS, Tav2 is SatO-HO,
	(abs(Tav1)>1; abs(Tav2)>1),
	(SatS \= HS; IdxS\=0),
	(SatO \= HO; IdxO\=0), !,
	csakjohely(SatS-SatO, IdxS, IdxO, Helyfakorul, JoHelyek).
csakjohely(SatS-SatO, IdxS, IdxO, [_|Helyfakorul], JoHelyek):-
	csakjohely(SatS-SatO, IdxS, IdxO, Helyfakorul, JoHelyek).

% tagcsere(+N, +Lista, -UjLista):
% Ha a Lista N-edik eleméböl 1-et kivonunk, akkor megkapjuk az UjListát.
tagcsere(1, [X|L], [E|L]):-
	E is X-1, !.
tagcsere(N, [X|L], [X|Luj]):-
	N1 is N-1,
	tagcsere(N1, L, Luj).

% nincspozitiv(+Lista): a Listában minden elem <=0.
nincspozitiv([]).
nincspozitiv([X|L]) :- X =< 0, nincspozitiv(L).

%member(?E, ?Lista): E tagja a Listának.
member(E, [E|_]).
member(E, [_|L]):- member(E, L).