%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Program: Hanojske veze
% Autor:   Ivan Kapustik
%
%--------------------------------------
% Problem hanojskych vezi pozostava z troch stlpcov
% a niekolkych kruhov roznej velkosti. Lubovolny
% kruh moze byt polozeny len na niektorom stlpci
% a to na jeho zakladni alebo na vacsom kruhu.
% Naraz je mozne prelozit len jeden kruh.
% Ulohou je prelozit vsetky kruhy z jedneho stlpca
% na iny, za dodrzania uvedenych podmienok.
%--------------------------------------
% Stlpec je reprezentovany usporiadanym zoznamom cisel,
% kde cislo 1 zodpoveda najmensiemu kruhu a nasledujuce
% cislo vzdy nasledujucemu vacsiemu. Zoznam zacina
% vrchnym kruhom v stlpci.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

hanojske_veze(stav(A,B,C),X):-
	max(AM,A),
	max(BM,B),
	max(CM,C),
	max(M,[AM,BM,CM]),
	hanojske_veze(stav(A,B,C),X,M),
	write('Uspech!'),
	nl.

hanojske_veze(_,_,0).
hanojske_veze(A,A,_).
hanojske_veze(ZAC,KON,M):-
	na_mieste(ZAC,KON,M),
	N is M - 1,
	hanojske_veze(ZAC,KON,N).
hanojske_veze(ZAC,KON,M):-
	mozny_presun(ZAC,KON,M,ZO,NA),
	presun(ZAC,NOV,M,ZO,NA),
	N is M - 1,
	hanojske_veze(NOV,KON,N).
hanojske_veze(ZAC,KON,M):-
	N is M - 1,
	presun_stlpec(ZAC,KON,VOL,M,N,ZO,NA),
	presun(VOL,NOV,M,ZO,NA),
	hanojske_veze(NOV,KON,N).

mozny_presun(ZAC,KON,M,ZO,NA):-
	na_vrchu(ZAC,M,ZO),
	nachadza_sa(KON,M,NA),
	( vrchny(ZAC,NA,V),!,
	  M < V
	  ;
	  true ).

presun(ZAC,KON,M,ZO,NA):-
	odstran(ZAC,NOV,ZO),
	pridaj(NOV,KON,M,NA),
	vypis(M,ZO,NA).

presun_stlpec(ZAC,KON,VOL,M,N,ZO,NA):-
	nachadza_sa(ZAC,M,ZO),
	nachadza_sa(KON,M,NA),
	urci_treti(ZO,NA,POM),
	odstran_mensie(ZAC,ZAC1,M),
	N is M - 1,
	pridaj_stlpec(ZAC1,VOL,N,POM),
	hanojske_veze(ZAC,VOL,N).

%--------------------------------------

na_mieste(stav(A,_,_),stav(B,_,_),M):- my_member(M,A), my_member(M,B).
na_mieste(stav(_,A,_),stav(_,B,_),M):- my_member(M,A), my_member(M,B).
na_mieste(stav(_,_,A),stav(_,_,B),M):- my_member(M,A), my_member(M,B).

na_vrchu(stav([M|_],_,_),M,1).
na_vrchu(stav(_,[M|_],_),M,2).
na_vrchu(stav(_,_,[M|_]),M,3).

nachadza_sa(stav(L,_,_),M,1):- my_member(M,L).
nachadza_sa(stav(_,L,_),M,2):- my_member(M,L).
nachadza_sa(stav(_,_,L),M,3):- my_member(M,L).

vrchny(stav([V|_],_,_),1,V).
vrchny(stav(_,[V|_],_),2,V).
vrchny(stav(_,_,[V|_]),3,V).

odstran(stav([_|A],B,C),stav(A,B,C),1).
odstran(stav(A,[_|B],C),stav(A,B,C),2).
odstran(stav(A,B,[_|C]),stav(A,B,C),3).

pridaj(stav(A,B,C),stav([M|A],B,C),M,1).
pridaj(stav(A,B,C),stav(A,[M|B],C),M,2).
pridaj(stav(A,B,C),stav(A,B,[M|C]),M,3).
                                    
urci_treti(1,2,3).
urci_treti(2,1,3).
urci_treti(3,1,2).
urci_treti(1,3,2).
urci_treti(2,3,1).
urci_treti(3,2,1).

odstran_mensie(stav(A,B,C),stav(A1,B1,C1),M):-
	odstran(A,A1,M),
	odstran(B,B1,M),
	odstran(C,C1,M).

odstran([N|T],L,M):-
	N < M,
	odstran(T,L,M).
odstran(A,A,_).

pridaj_stlpec(stav(A,B,C),stav(A1,B,C),N,1):- pridaj_stlpec(A,A1,N).
pridaj_stlpec(stav(B,A,C),stav(B,A1,C),N,2):- pridaj_stlpec(A,A1,N).
pridaj_stlpec(stav(C,B,A),stav(C,B,A1),N,3):- pridaj_stlpec(A,A1,N).

pridaj_stlpec(A,A,0).
pridaj_stlpec(A,A1,N):-
	N1 is N - 1,
	pridaj_stlpec([N|A],A1,N1).

vypis(M,ZO,NA):-
	write('Presuvam '),
	write(M),
	write(' zo stlpca '),
	write(ZO),
	write(' na stlpec '),
	write(NA),
	write('.'),
	nl.

max(0,[]).
max(M,[H|L]):- max(N,L), viac(N,H,M).

viac(N,H,N):- N >= H.
viac(N,H,H):- H > N.

my_member(M,[M|_]).
my_member(M,[_|L]):- my_member(M,L).