%	Breadth first search for path through a set of rooms
%	Very inefficient!
%	Run with at least 13000 units of stack space.
%	i.e. call $ prolog -s13000 short
%	Room layout taken from Siklossy: Let's Talk Lisp.


connects(30, 43).
connects(50, 49) :- !.
connects(R1, R2) :-  R1 > 42, R2 is R1 + 1.
connects(R1, R2) :- R1 > 43, !, R2 is R1 - 1.
connects(43, 30) :- !.
connects(R1, R2) :- R1 > 6, R2 is R1 - 6.
connects(R1, R2) :- R1 < 37, R2 is R1 + 6.
connects(R1, R2) :- M is R1 mod 6, M > 0, R2 is R1 + 1.
connects(R1, R2) :- M is R1 mod 6, M > 1, R2 is R1 - 1.
connects(R1, R2) :- R1 mod 6 == 0, R2 is R1 - 1.

member(X, [X, ..Y]) :- !.
member(X, [A, ..B]) :- member(X, B).

in(X, []) :- !, fail.
in(X, [X, ..Y]) :- !.
in(X, [A, ..B]) :- !, in(X, B).

mkfron([], X, Y) :- !.
mkfron([A, ..B], X, Y) :- in(A, Y), !, mkfron(B, X, Y), !.
mkfron([A, ..B] , X, Y) :- member(A, X), member(A, Y), mkfron(B, X, Y), !.

new([], X, Reached) :- !.
new([A, ..B], N, Reached) :-
	bagof(X, connects(A, X), L),
	mkfron(L, N, Reached),
	new(B, N, Reached).

path(Frontier, Goal, Reached) :-
	in(Goal, Frontier), !,
	print("Made it!").
path(Frontier, Goal, Reached) :-
	new(Frontier, F, Reached), !,
	print(F),
	path(F, Goal, Reached).

findpath(Start, Goal) :- path([Start], Goal, [Start, ..X]), !.

run :- findpath(28, 48).
