blocked(XY) :- obj(wall(_),XY).
blocked(XY) :- obj(lava,XY). 
gap((X,Y),horizontal) :- 
	not blocked((X,Y)), blocked((X,Y-1)), blocked((X,Y+1)).
gap((X,Y),vertical) :- 
	not blocked((X,Y)), blocked((X-1,Y)), blocked((X+1,Y)).

alley((X,Y)) :- gap((X,Y),horizontal), gap((X+1,Y), horizontal). 
alley((X,Y)) :- gap((X,Y),horizontal), gap((X-1,Y), horizontal). 
alley((X,Y)) :- gap((X,Y),vertical), gap((X,Y+1), vertical). 
alley((X,Y)) :- gap((X,Y),vertical), gap((X,Y-1), vertical). 

pcp(U) :- blocked(U).
pcp(U) :- gap(U,_), not alley(U).

rtl((X,Y)) :- pcp((X,Y)), pcp((X+1,Y)), pcp((X,Y+1)).
rbl((X,Y)) :- pcp((X,Y)), pcp((X+1,Y)), pcp((X,Y-1)).
rtr((X,Y)) :- pcp((X,Y)), pcp((X-1,Y)), pcp((X,Y+1)).
rbr((X,Y)) :- pcp((X,Y)), pcp((X-1,Y)), pcp((X,Y-1)).

rect(((X1,Y1), (X2,Y2))) :- 
	rtl((X1,Y1)), rbl((X1,Y2)), 
	rtr((X2,Y1)), rbr((X2,Y2)), 
	X2-X1>0, Y2-Y1>0.
contains(((X11,Y11),(X12,Y12)), ((X21,Y21),(X22,Y22))) :- 
	rect(((X11,Y11),(X12,Y12))), rect(((X21,Y21),(X22,Y22))),
	X11<=X21, Y11<=Y21, X12>=X22, Y12>=Y22, 
	((X11,Y11),(X12,Y12))!=((X21,Y21),(X22,Y22)).
room(R) :- rect(R), not contains(R,_).

v(U) :- obj(door(_,_),U).
v(U) :- obj(goal,U).
v(U) :- obj(agent(_),U).
v(U) :- obj(key(_),U).
v(U) :- obj(ball(C),U), not C=blue.
v(U) :- gap(U,_), not alley(U).

inRoom((X,Y),((X1,Y1),(X2,Y2))) :- 
	v((X,Y)), room(((X1,Y1),(X2,Y2))), 
	X1<=X, Y1<=Y, X2>=X,Y2>=Y.
e(U,V) :- v(U), v(V), inRoom(U,R), inRoom(V,R), U!=V.

p(0,U) :- obj(agent(_),U).
0 { p(T+1,V) : e(U,V) } 1 :- p(T,U), T<#count{ X : v(X) }.
:- obj(goal,_), 0 = #count{ U : p(_,U), obj(goal,U) }, not terminal.
:~ p(T,_). [1@2,T]
:~ p(1,(X1,Y1)), obj(agent(_),(X2,Y2)), D=|X2-X1|+|Y2-Y1|. [D@1]

needsKeyBefore(C,T) :- p(T,U), obj(door(C,locked),U), not carries(key(C)).
keyOnPath(C,T) :- p(T,U), obj(key(C),U).
:- 0=#count{ T : keyOnPath(C,T), T<T1}, needsKeyBefore(C,T1).

nextOnPath(V) :- p(1,V).

adj((X+1,Y)) :- obj(agent(_),(X,Y)).
adj((X-1,Y)) :- obj(agent(_),(X,Y)).
adj((X,Y+1)) :- obj(agent(_),(X,Y)).
adj((X,Y-1)) :- obj(agent(_),(X,Y)).

fronting((X,Y-1)) :- obj(agent(north),(X,Y)).
fronting((X,Y+1)) :- obj(agent(south),(X,Y)).
fronting((X+1,Y)) :- obj(agent(east),(X,Y)).
fronting((X-1,Y)) :- obj(agent(west),(X,Y)).

dangerous(XY) :- obj(ball(blue),XY).
dangerous(XY) :- obj(lava,XY).

oriented(O) :- obj(agent(O),_).

xdir(west) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AX>GX.
xdir(east) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AX<GX.
xdir(on_axis) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AX=GX.

ydir(north) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AY>GY.
ydir(south) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AY<GY.
ydir(on_axis) :- obj(agent(_),(AX,AY)), nextOnPath((GX,GY)), AY=GY.

touching(goal) :- nextOnPath(G), adj(G), obj(goal,G).
touching(key) :- nextOnPath(G), adj(G), obj(key(_),G).
touching(door(S)) :- nextOnPath(G), adj(G), obj(door(_, S),G).
touching(gap) :- nextOnPath(G), adj(G), gap(G,_), not alley(G), 
	not touching(goal), not touching(door(_)), not touching(key).
touching(none) :- not touching(goal), not touching(door(_)), 
	not touching(gap), not touching(key).

in_gap(D) :- obj(agent(_),XY), gap(XY,D), not alley(XY).
in_gap(none) :- not in_gap(horizontal), not in_gap(vertical).