Encoding opendoors.lp

Name	opendoors.lp
Class Tree	[Root] Puzzles (51) OpenDoors (3)
Submitter	Hannes Schröder
Author	Hannes Schröder
Description
Created	2010-02-26 11:06
Modified	2010-02-26 11:06
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Optimization Choice rules Weight constraints
Compatible Instance Classes	OpenDoors
Input Predicates
Output Predicates
Encoding Parameter
Standalone	No
Tags
Attributes
Content	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% A solver for the flashgame OpenDoors 2 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% Names: %% %% T :- Time %% %% O :- Orientation , Opening %% %% N :- numeric value %% %% X , Y :- Coordinates %% %% %% %% Meanings of Alterings: %% %% %% %% Every type of variables: %% %% X , Y :- constant value throughout the predicate %% %% XN, YN :- number(N). Somehow different value %% %% %% %% Coordinates only: %% %% XS, YS :- (X,Y) of Startfield of Step %% %% XE, YE :- (X,Y) of Endfield of Step %% %% XB, YB :- (X,Y) of Field between Start and End of Step %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% delta(u,1,0). delta(d,-1,0). delta(r,0,1). delta(l,0,-1). swall(X1,Y1,X2,Y2) :- wall(X1,Y1,X2,Y2). swall(X2,Y2,X1,Y1) :- wall(X1,Y1,X2,Y2). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Own predicates % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x(1..X) :- field(X,Y). y(1..Y) :- field(X,Y). time(1..N) :- steps(N). orientation(u). orientation(d). orientation(l). orientation(r). orientation(n). %* complementary_orientation(u,d). complementary_orientation(d,u). complementary_orientation(l,r). complementary_orientation(r,l). % opening(open). opening(closed). other_opening(open, closed). other_opening(closed, open). sign(0,0). sign(1,1..X) :- x(X). sign(1,1..Y) :- y(Y). sign(-1,-X..-1) :- x(X). sign(-1,-Y..-1) :- y(Y). % (XB, YB) between and in line with (XS, YS) and (XE, YE) in_between(XB,Y,XS,Y,XE,Y) :- x(XB), field(XS,Y) , field(XE,Y), sign(N,XS-XB) , sign(N,XB-XE). in_between(X,YB,X,YS,X,YE) :- y(YB), field(X,YS) , field(X,YE), sign(N,YS-YB) , sign(N,YB-YE). % O1 one orientation of a door, O2 the other orientation other_orientation(X,Y,O1,O2) :- angle(X,Y,O1) , angle(X,Y,O2) , O1 != O2. % Orientation of door when it's being opened, according to move-direction. % Returns the orientation only if it's an possible angle of the door. opening_orientation(O,XS,YS,XE,YE) :- field(XS,YS) , field(XE,YE) , sign(N1,XS-XE) , sign(N2,YS-YE) , delta(O1,N1,N2) , other_orientation(XE,YE,O1,O). % Returns the orientation of the door when closing it behind the player. closing_orientation(O,XS,YS,XE,YE) :- opening_orientation(O1,XE,YE,XS,YS) , other_orientation(XS,YS,O1,O). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Main-Encoding % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Initial Step at(X,Y,0) :- init(X,Y). % Max one step per time/1. { at(X,Y,T) : field(X,Y) }1 :- time(T). % Time of reaching the goal % (needed for the minimize-statement) max_at(T) :- at(X,Y,T), goal(X,Y), time(T). % Don't choose a step if there's been none right before. :- at(X1,Y1,T) , not at(X2,Y2,T-1) : field(X2,Y2), time(T). % Don't let the goal be unreached. :- not 1{ at(X,Y,T) : goal(X,Y) : time(T) }1. % Don't make a step after the goal was reached. :- 1{at(X1,Y1,T1) : field(X1,Y1) }, at(X2,Y2,T2), goal(X2,Y2) , time(T1), time(T2) , T1 > T2. % That's sometimes faster, but not as ground-efficient. %:- at(X1,Y1,T1) , at(X2,Y2,T2):goal(X2,Y2), time(T2), T1 > T2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % State-Handling % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Switches % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % It's only a change if it wasn't in the position before. state_change_switch(XS,YS,O,T+1) :- at(XS,YS,T), at(XE,YE,T+1), sign(N1,XE-XS), sign(N2,YE-YS), delta(O,N1,N2), position(XS,YS,O), not current_state_switch(XS,YS,O,T). state_change_switch(XB,YB,O,T+1) :- at(XS,YS,T), at(XE,YE,T+1), in_between(XB,YB,XS,YS,XE,YE), sign(N1,XE-XS), sign(N2,YE-YS), delta(O,N1,N2), position(XB,YB,O), not current_state_switch(XB,YB,O,T). state_change_switch(XE,YE,O,T+1) :- at(XS,YS,T), at(XE,YE,T+1), sign(N1,XE-XS), sign(N2,YE-YS), delta(O,N1,N2), position(XE,YE,O), not current_state_switch(XE,YE,O,T). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Doors % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%% % "Normal" Doors % %%%%%%%%%%%%%%%%%%%% %%%% % Closing doors %%%% % ...when leaving a field state_change_door(XS,YS,O,T+1) :- at(XS,YS,T) , at(XE,YE,T+1) , not switched_door(XS,YS,O1) : orientation(O1), closing_orientation(O,XS,YS,XE,YE). % ...when crossing a field between start and end state_change_door(XB,YB,O,T+1) :- at(XS,YS,T), at(XE,YE,T+1) , not switched_door(XB,YB,O1) : orientation(O1), in_between(XB,YB,XS,YS,XE,YE) , closing_orientation(O,XB,YB,XE,YE). %%%% % Opening doors %%%% % ...when crossing a field between start and end state_change_door(XB,YB,O,T+1) :- at(XS,YS,T), at(XE,YE,T+1) , not switched_door(XB,YB,O1) : orientation(O1), in_between(XB,YB,XS,YS,XE,YE) , opening_orientation(O,XS,YS,XB,YB). % ...when steping on a field state_change_door(XE,YE,O,T+1) :- at(XS,YS,T) , at(XE,YE,T+1), not switched_door(XE,YE,O1) : orientation(O1), opening_orientation(O,XS,YS,XE,YE). %%%% % Moved by another door %%%% % state_change_door(X1,Y1,O,T) :- current_state_door(X1,Y1,O1,T-1), delta(O1,A,B), complementary_orientation(O1,O2), state_change_door(X1+A,Y1+B,O2,T), other_orientation(X1,Y1,O1,O), not switched_door(X1,Y1,O3) : orientation(O3), angle(X1,Y1,O1), angle(X1+A,Y1+B,O2), time(T). % state_change_door(X1,Y1,O,T) :- current_state_door(X1,Y1,O1,T-1), delta(O1,A,B), delta(O2,-A,-B), state_change_door(X1+A,Y1+B,O2,T), other_orientation(X1,Y1,O1,O), not switched_door(X1,Y1,O3) : orientation(O3), angle(X1,Y1,O1), angle(X1+A,Y1+B,O2), time(T). %%%%%%%%%%%%%%%%%%%% % Switched Doors % %%%%%%%%%%%%%%%%%%%% % Even number doesn't change anything state_change_door(X,Y,O,T) :- 2N{ state_change_switch(X1,Y1,O1,T):switch(X1,Y1,O3):orientation(O1) }2N, N = 1..5 , current_state_door(X,Y,O,T-1) , orientation(O), switched_door(X,Y,O2) , time(T). % Odd number flips the state state_change_door(X,Y,O,T) :- (2N)+1{ state_change_switch(X1,Y1,O2,T):switch(X1,Y1,O4):orientation(O2) }(2N)+1, N = 0..5 , current_state_door(X,Y,O1,T-1) , other_orientation(X,Y,O1,O) , switched_door(X,Y,O3) , time(T). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Holes % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%% % Switched holes % %%%%%%%%%%%%%%%%%%%% % All switched holes are switched simultaneously % Even number doesn't change anything state_change_hole(X,Y,O,T) :- 2N{ state_change_switch(X1,Y1,O1,T):switch(X1,Y1,O3):orientation(O1) }2N, N = 1..5 , current_state_hole(X,Y,O,T-1) , opening(O), switched_hole(X,Y,O2) , time(T). % Odd number flips the state state_change_hole(X,Y,O,T) :- (2N)+1{ state_change_switch(X1,Y1,O2,T):switch(X1,Y1,O4):orientation(O2) }(2N)+1, N = 0..5 , current_state_hole(X,Y,O1,T-1) , other_opening(O1,O) , switched_hole(X,Y,O3) , time(T). %%%%%%%%%%%%%%%%%%%% % Static holes % %%%%%%%%%%%%%%%%%%%% state_change_hole(X,Y,open,T) :- at(X,Y,T-1), hole(X,Y), time(T). state_change_hole(X,Y,open,T) :- at(XS,YS,T-1), at(XE,YE,T), in_between(X,Y,XS,YS,XE,YE), hole(X,Y). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Refreshing states % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Initial State current_state_door(X,Y,O,0) :- state(X,Y,O). current_state_door(X,Y,O,0) :- switched_door(X,Y,O). current_state_switch(X,Y,O,0) :- switch(X,Y,O). current_state_hole(X,Y,O,0) :- switched_hole(X,Y,O). current_state_hole(X,Y,closed,0) :- hole(X,Y). % Taking the changed if something happened current_state_door(X,Y,O,T) :- state_change_door(X,Y,O,T). current_state_switch(X,Y,O,T) :- state_change_switch(X,Y,O,T). current_state_hole(X,Y,O,T) :- state_change_hole(X,Y,O,T). % Taking the old if nothing happened current_state_door(X,Y,O,T) :- current_state_door(X,Y,O,T-1) , angle(X,Y,O) , time(T), not state_change_door(X,Y,O1,T) : orientation(O1). current_state_switch(X,Y,O,T) :- current_state_switch(X,Y,O,T-1), position(X,Y,O), time(T), not state_change_switch(X,Y,O1,T) : orientation(O1). current_state_hole(X,Y,O,T) :- current_state_hole(X,Y,O,T-1), switched_hole(X,Y,O1), time(T), opening(O), not state_change_switch(X1,Y1,O2,T) : orientation(O2) : switch(X1,Y1,O3). current_state_hole(X,Y,O,T) :- current_state_hole(X,Y,O,T-1), hole(X,Y), time(T), opening(O), not state_change_hole(X,Y,O1,T):opening(O1). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Constraints % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% % Steps %%%% % Don't "stand still" on a field. :- at(X,Y,T) , at(X,Y,T+1). % Don't jump out of line. :- at(XS,YS,T) , at(XE,YE,T+1) , XS != XE , YS != YE . %%%% % Blocked by walls %%%% % Directly :- at(XS,YS,T) , at(XE,YE,T+1) , swall(XS,YS,XE,YE). % Wall between a field between start/end and another field % in the direction of the jump. :- at(XS,Y,T) , at(XE,Y,T+1) , swall(XB,Y,XB1,Y) , in_between(XB,Y,XS,Y,XE,Y). :- at(X,YS,T) , at(X,YE,T+1) , swall(X,YB,X,YB1) , in_between(X,YB,X,YS,X,YE). % Jump over a non-existent field :- at(XS,YS,T) , at(XE,YE,T+1) , not field(XB,YB) , in_between(XB,YB,XS,YS,XE,YE). %%%% % Blocking by doors %%%% % Step through closed door % closing_orientation/4 returns angle, in which the door should be closed % If it is already in this angle, we can't step through from this direction % start :- at(XS,YS,T) , at(XE,YE,T+1) , closing_orientation(O,XS,YS,XE,YE) , current_state_door(XS,YS,O,T). % field between start and end :- at(XS,YS,T) , at(XE,YE,T+1) , in_between(XB,YB,XS,YS,XE,YE) , closing_orientation(O,XB,YB,XE,YE) , current_state_door(XB,YB,O,T). %%%% % switched door between start and end %%%% %% % ... which switches back / stays in a blocking orientation %% % ... direction which could be normally pushed open :- at(XS,YS,T) , at(XE,YE,T+1) , in_between(XB,YB,XS,YS,XE,YE) , switched_door(XB,YB,O), sign(N1,XS-XE), sign(N2,YS-YE), delta(O1,N1,N2), current_state_door(XB,YB,O1,T), 2N{ state_change_switch(XB1,YB1,O2,T+1):orientation(O2):in_between(XB1,YB1,XS,YS,XB,YB):switch(XB1,YB1,O4) , state_change_switch(XS,YS,O3,T+1):orientation(O3) }2N, N = 0..5 . % ... direction which is in the blocking position :- at(XS,YS,T) , at(XE,YE,T+1) , in_between(XB,YB,XS,YS,XE,YE) , switched_door(XB,YB,O), sign(N1,XE-XS), sign(N2,YE-YS), delta(O1,N1,N2), current_state_door(XB,YB,O1,T), 2N{ state_change_switch(XB1,YB1,O2,T+1):orientation(O2):in_between(XB1,YB1,XS,YS,XB,YB):switch(XB1,YB1,O4) , state_change_switch(XS,YS,O3,T+1):orientation(O3) }2N, N = 0..5 . %% % ... which is switched in a blocking orientation %% % ... direction which could be normally pushed open :- at(XS,YS,T) , at(XE,YE,T+1) , in_between(XB,YB,XS,YS,XE,YE) , switched_door(XB,YB,O), sign(N1,XS-XE), sign(N2,YS-YE), delta(O1,N1,N2), other_orientation(XB,YB,O1,O2), current_state_door(XB,YB,O2,T), (2N)+1{ state_change_switch(XB1,YB1,O3,T+1):orientation(O3):in_between(XB1,YB1,XS,YS,XB,YB):switch(XB1,YB1,O5) , state_change_switch(XS,YS,O4,T+1):orientation(O4) }(2N)+1, N = 0..5 . % ... direction which is in the blocking position :- at(XS,YS,T) , at(XE,YE,T+1) , in_between(XB,YB,XS,YS,XE,YE) , switched_door(XB,YB,O), sign(N1,XE-XS), sign(N2,YE-YS), delta(O1,N1,N2), other_orientation(XB,YB,O1,O2), current_state_door(XB,YB,O2,T), (2N)+1{ state_change_switch(XB1,YB1,O3,T+1):orientation(O3):in_between(XB1,YB1,XS,YS,XB,YB):switch(XB1,YB1,O5) , state_change_switch(XS,YS,O4,T+1):orientation(O4) }(2N)+1, N = 0..5 . % switched door closed at the end % ... which switches back / stays in a blocking orientation :- at(XS,YS,T) , at(XE,YE,T+1) , switched_door(XE,YE,O), sign(N1,XS-XE), sign(N2,YS-YE), delta(O1,N1,N2), current_state_door(XE,YE,O1,T), 2N{ state_change_switch(XB1,YB1,O2,T+1):orientation(O2):in_between(XB1,YB1,XS,YS,XE,YE):switch(X1,Y1,O4) , state_change_switch(XS,YS,O3,T+1):orientation(O3) }2N, N = 0..5 . % ... which is switched in a blocking orientation :- at(XS,YS,T) , at(XE,YE,T+1) , switched_door(XE,YE,O), sign(N1,XS-XE), sign(N2,YS-YE), delta(O1,N1,N2), other_orientation(XE,YE,O1,O2), current_state_door(XE,YE,O2,T), (2N)+1{ state_change_switch(XB1,YB1,O3,T+1):orientation(O3):in_between(XB1,YB1,XS,YS,XE,YE):switch(X1,Y1,O5) , state_change_switch(XS,YS,O4,T+1):orientation(O4) }(2N)+1, N = 0..5 . %%%% % Blocking by holes %%%% %% Static % Don't step in holes. :- at(X,Y,T) , current_state_hole(X,Y,open,T). :- at(XS,YS,T) , at(XE,YE,T+1), in_between(XB,YB,XS,YS,XE,YE), current_state_hole(XB,YB,open,T), hole(XB,YB). %% Switched % Open previously, even number of switches on way to it :- at(XS,YS,T), at(XE,YE,T+1), in_between(XB,YB,XS,YS,XE,YE), switched_hole(XB,YB,O), current_state_hole(XB,YB,open,T), (2N){ state_change_switch(XB1,YB1,O1,T+1):orientation(O1):in_between(XB1,YB1,XS,YS,XE,YE):switch(XB1,YB1,O3) , state_change_switch(XS,YS,O2,T+1):orientation(O2) }(2N), N = 0..5. % Closed previously, odd number of switches on way to it :- at(XS,YS,T), at(XE,YE,T+1), in_between(XB,YB,XS,YS,XE,YE), switched_hole(XB,YB,O), current_state_hole(XB,YB,closed,T), (2N)+1{ state_change_switch(XB1,YB1,O1,T+1):orientation(O1):in_between(XB1,YB1,XS,YS,XE,YE):switch(XB1,YB1,O3) , state_change_switch(XS,YS,O2,T+1):orientation(O2) }(2*N)+1, N = 0..5. % In der Abgabeversion unbedingt angeben!! #minimize [ max_at(T) : time(T) = T ]. #hide. #show at/3.

Actions

Navigation

Encoding opendoors.lp