views:

827

answers:

4

If I have the following predicate door, which declare that there is a door between the two rooms:

door(office, hall).
door(kitchen, office).
door(hall, "dining room").
door(kitchen, cellar).
door("dining room", kitchen).

And the predicate doorstate which declares the state of a door:

doorstate(hall, office, closed).
doorstate(hall, "dining room", opened).
doorstate("dining room", kitchen, opened).
doorstate(kitchen, office, opened).
doorstate(kitchen, cellar, opened).

There is a pathway between two rooms if all of the doors between them are open.

How can I write a rule to discover if there is such a pathway between two rooms?

+2  A: 

The abject horror of prolog returns too quickly.

wayopen(Room1,Room2) :- doorstate(Room1, Room2, opened).
wayopen(Room1,Room2) :- doorstate(Room1, RoomX, opened), wayopen(RoomX,Room2).

So I'm not just doing your homework for you, here's how to understand it:

  • The way is open between two rooms if they are joined by a door and the door is open.
  • The way is open between two rooms if the first way has a door open to another room, and there is a way from the other room to the second room.

Note that these rules can only go through doors in one direction. Your homework is to make it work in both directions.

Where can we get to from the hall?

?- wayopen(hall, X).
X = diningroom ;
X = kitchen ;
X = office ;
X = cellar ;
false.

Here are all the rooms you can get from and to:

?- wayopen(Room1,Room2).
Room1 = hall,
Room2 = diningroom ;
Room1 = diningroom,
Room2 = kitchen ;
Room1 = kitchen,
Room2 = office ;
Room1 = kitchen,
Room2 = cellar ;
Room1 = hall,
Room2 = kitchen ;
Room1 = hall,
Room2 = office ;
Room1 = hall,
Room2 = cellar ;
Room1 = diningroom,
Room2 = office ;
Room1 = diningroom,
Room2 = cellar ;
false.
geofftnz
I'm having a bit of a play - for a start you might want to take the space out of "dining room". The other thing is the code I've written only lets you go through a door one way.
geofftnz
Yeah, its working now but when for example i asked wayopen(hall,Room2) the answer should be hall and dinig room but instead its showing 4 ansewers (dinig room,office,cellar) why ? how i can make it only print the dinig room.
I removed the second rule ! :-)
I'm actually getting a Stack Overflow :( the irony...
geofftnz
With both rules you should expect 4 answers. The reason is that you can get to the kitchen from the dining room and from the kitchen you can reach the cellar.
geofftnz
Your doors seem to be only one-way. You should remember where you have been to avoid loops (and Stack Overflows :-).
starblue
@starblue: correct. But 11 years of not touching a language is a long time and we've got to leave the original poster something to do for homework :)
geofftnz
+1  A: 

You need to describe a relation (exists_way/2) that is symmetric and transitive.

% Base cases
exists_way_(hall, 'dining room').
exists_way_('dining room', kitchen).
exists_way_(kitchen, office).
exists_way_(kitchen, cellar).

% Symmetric
exists_way(R1, R2) :- exists_way_(R1, R2) ; exists_way_(R2, R1).

% Transitive
exists_way(R1, R2) :-
    exists_way_(R1, R3),
    exists_way(R3, R2).

This code over-generates solutions though. So you would need to filter out the duplicates later.

Kaarel
A: 

You need to describe a relation (exists_way/2) that is symmetric and transitive. In a Prolog that supports tabling (such as XSB), you can express these relations in a very natural way, i.e. as they are expressed in math books.

:- table exists_way/2.

% Open doors
exists_way(hall, 'dining room').
exists_way('dining room', kitchen).
exists_way(kitchen, office).
exists_way(kitchen, cellar).

% Symmetry
exists_way(R1, R2) :-
    exists_way(R2, R1).

% Transitivity
exists_way(R1, R2) :-
    exists_way(R1, R3),
    exists_way(R3, R2).

In this case, the query exists_way(R1, R2) delivers exactly 25 unique solutions.

Kaarel
A: 

In the spirit of learning: This is the same problem as the grandparent problem you probably did in the first week of your prolog course.

It turns out that quite a lot of the stuff you will do in prolog will be quite similar in structure. So make sure you grasp the ideas about recursive predicates, and how the order in which the clauses must go, for correction and performance.

For example, you should avoid non-tail-recursion where possible.

Matthew Schinckel