/* 1 */

:- dynamic ps/2, cycle/2.
:- dynamic sizeY/1, sizeX/1.

findall(X1, Y1, X2, Y2, SX, SY, RES) :-
	SX > 0, SY > 0,
	retractall(sizeX(_)), retractall(sizeY(_)),
	assert(sizeX(SX)), assert(sizeY(SY)),
	testP(X1, Y1), testP(X2, Y2),
	retractall(ps(_, _)), retractall(cycle(_, _)),
	setof(R, search(X1, Y1, X2, Y2, R), RES).

testP(X, Y) :-
	X > 0, Y > 0,
	sizeX(XX), X =< XX,
	sizeY(YY), Y =< YY.

search(X, Y, X, Y, [X:Y]) :- cycle(_, _), !.
search(X, Y, X, Y, _) :- not(cycle(_, _)), !, fail.
search(X, Y, XX, YY, [X:Y|R]) :-
	cycle(_, _),
	assert(ps(X, Y)),
	nxtStep(X, Y, NX, NY),
	not(ps(NX, NY)),
	search(NX, NY, XX, YY, R).
search(X, Y, XX, YY, [X:Y|R]) :-
	not(cycle(_, _)),
	assert(ps(X, Y)),
	nxtStep(X, Y, NX, NY),
	tryTwo(NX, NY),
	search(NX, NY, XX, YY, R).
search(X, Y, _, _, _) :-
	ps(X, Y), not(cycle(X, Y)),
	!, retract(ps(X, Y)),
	fail.

tryTwo(NX, NY) :-
	ps(NX, NY),
	assert(cycle(NX, NY)).
tryTwo(NX, NY) :-
	cycle(NX, NY),
	!, retract(cycle(NX, NY)),
	fail.
tryTwo(NX, NY) :-
	not(ps(NX, NY)).

nxtStep(X, Y, XX, Y) :-
	sizeX(SX), X < SX,
	XX is X + 1.
nxtStep(X, Y, XX, Y) :-
	XX is X - 1,
	XX > 0.
nxtStep(X, Y, X, YY) :-
	sizeY(SY), Y < SY,
	YY is Y + 1.
nxtStep(X, Y, X, YY) :-
	YY is Y - 1,
	YY > 0.

/* 2 */

emptyT(leaf).

insval(V, leaf, node(V, leaf, leaf)).
insval(V, node(W, L, R), node(W, LL, R)) :-
	V < W, insval(V, L, LL).
insval(V, node(W, L, R),node(W, L, RR)) :-
	V > W, insval(V, R, RR).
insval(V, node(V, L, R), node(V, L, R)).

l2t([], leaf).
l2t([H|T], R) :-
	l2t(T, TR),
	insval(H, TR, R).

t2l(leaf, []).
t2l(node(V, L, R), ResL) :-
	t2l(L, LL),
	t2l(R, RL),
	append(LL, [V|RL], ResL).

tree2list(T, L) :-
	var(T), var(L), !, fail.
tree2list(T, L) :-
	var(T), l2t(T, L).
tree2list(T, L) :-
	var(L), t2l(T, L).
tree2list(T, L) :-	/* tady to slo ruzne, nic neni 100% */
	nonvar(L), nonvar(T),
	t2l(T, LL), LL = L.

/* 3 */

/* takovy trochu Haskell v Prologu */

revin([], _, []).
revin([H|T], S, RES) :-
	words([H|T], S, WRDS),
	revall(WRDS, REV),
	unwords(REV, S, RES).

words([], _, []).
words([H|_], H, _) :-
	!, fail.	/* an error */
words([H|T], S, [[H|W]|WS]) :-
	inw(T, S, x(W, R)),
	words(R, S, WS).

inw([], _, x([], [])).
inw([H|T], H, x([], T)) :- !.
inw([H|T], S, x([H|W], R)) :-
	inw(T, S, x(W, R)).

revall([L|LS], [RL|RLS]) :-
	reverse(L, RL),
	revall(LS, RLS).
revall([], []).

unwords([], _, []).
unwords([L|LS], _, L) :-
	nll(LS), !.
unwords([L|LS], S, UR) :-
	append(L, [S], LSP),
	unwords(LS, S, UW),
	append(LSP, UW, UR).

nll([]).
nll([_|_]) :- !, fail.	/* je ale zbytecny */

/* brutus Prolog */
/* inspirace v pisemece, upraveno pro spravnou funkcnost */

revn([], _, []).
revn(Str, Spc, Res) :-
	not(member(Spc, Str)), !,
	reverse(Str, Res).
revn(Str, Spc, Res) :-
	append(L, [Spc|Rest], Str),
	not(member(Spc, L)), !,
	reverse(L, RL),
	revn(Rest, Spc, InRes),
	append(RL, [Spc|InRes], Res).

/*

member(H,[H|_]).
member(X,[_|T]) :- member(X,T).

*/

/* EOF */