F0O@psuvm.psu.edu (07/26/90)
I'm just a beginning prolog programmer, and was trying an exercise in a book on using the cut. Below is a description of the problem: Players in a squash club are divided into three leagues, and players may only challenge members in their own league or the league below, if there is one. Write a prolog program that will display all possible matches between club players in the form: tom versus bill Use the cut to ensure for example, that Tom versus bill and bill versus tom are not both displayed. END OF PROBLEM DESCRIPTION Below is the program I wrote in PDC prolog on an ibm pc. PDC prolog used to be Turbo Prolog. I may have wrote the problem wrong, but putting the cut after the first member subgoal will on show all players ann can play. Putting the cut after the second member subgoal will only show one person ann can play. Where have I gone astray? [Tim] PROGRAM in PDC prolog: domains player = symbol league = integer predicates member(player,league) match clauses member(ann, 3). member(joyce, 3). member(ramona, 2). member(cynthia, 2). member(susan, 1). member(lisa, 1). match :- member(Player1, Level1), member(Player2, Level2), Player1 <> Player2, Level1 >= Level2, write(Player1, " versus ",Player2), nl, fail.
ok@mudla.cs.mu.OZ.AU (Richard O'Keefe) (07/27/90)
In article <90207.090559F0O@psuvm.psu.edu>, F0O@psuvm.psu.edu writes: > Players in a squash club are divided into three leagues, and players > may only challenge members in their own league or the league below, > if there is one. > Write a Prolog program that will display all possible matches between > club players in the form: > tom versus bill > Use the cut to ensure for example, that > Tom versus bill > and > bill versus tom > are not both displayed. > Where have I gone astray? (a) Why use Turbo Prolog when you could use ALS Prolog? (b) Why use a cut? > member(ann, 3). > member(joyce, 3). > member(ramona, 2). > member(cynthia, 2). > member(susan, 1). > member(lisa, 1). 1. It is just plain confusing to use member/2 here. member(X, L) is almost always used for "L is a list and X is a member of L". It's also a good idea to use two-pair names so that you can keep track of which argument is which. I'd use player_league(Player, League) player_league(ann, 3). player_league(joyce, 3). player_league(ramona, 2). player_league(cynthia, 2). player_league(susan, 1). player_league(lisa, 1). > match :- > member(Player1, League1), > member(Player2, League2), > Player1 <> Player2, > League1 >= League2, > write(Player1, " versus ",Player2), nl, fail. 2. We want may_challenge(Challenger, Challengee) to be true when Challenger and Challengee are names of players and Challenger may challenge Challengee. The original specification says quite clearly that C1 may challenge C2 only if C1 and C2 are in the same league, or if C2 is in THE league below C1, which I take to mean that C1 may challenge players C2 who are *ONE* rung lower but not two rungs lower. So a player in league 3 may challenge a player in league 2, but not a player in league 1. The specification thus needs to be clarified. As there are only three leagues, let's write permissible_leagues(3, 3). % same league permissible_leagues(3, 2). % or one league lower. permissible_leagues(2, 2). % same league permissible_leagues(2, 1). % or one league lower. permissible_leagues(1, 1). % same league (there is none lower). may_challenge(Challenger, Challengee) :- player(Challenger, HigherLeague), player(Challengee, LowerLeague), Challenger \== Challengee, permissible_leagues(HigherLeague, LowerLeague). To write out all permitted challenges: write_all_permissible_challenges :- forall( may_challenge(X, Y), format('~w challenges ~w.~n', [X,Y]) ). 3. Now, the definition above *will* produce both solutions ?- may_challenge(ann, joyce). ?- may_challenge(joyce, ann). but that's RIGHT because these two solutions say DIFFERENT things. The first says that "ann may challenge joyce" and the second says that "joyce may challenge ann" and these are different statements. (For example, the challenger might serve first or something like that, so we might be talking about different possible games.) If you want to consider the game (X against Y) as being the same as the game (Y against X), then the simplest way to eliminate one of them is to change the specification. Instead of talking about permitted challenges, let's talk about possible games, and now we are going to use a "canonical description" of a game: the canonical description of a game between X and Y is either X,Y or Y,X depending on whether X alphabetically precedes or follows Y. possible_game(Player1, Player2) :- player_league(Player1, League1), player_league(Player2, League2), Player1 @< Player2, % generate only canonical descriptions League1-League2 =< 1, % difference not too great one way League2-League1 =< 1. % difference not too great other way. write_all_games :- forall( possible_game(Player1, Player2) , format('~w versus ~w.~n', [Player1,Player2]) ). This is a good example of a problem where a cut should NOT be used. What we did was to eliminate duplicate solutions from the SPECIFICATION so that a logical implementation of the specification didn't _need_ a cut. I've spent about half an hour thinking about this, and I haven't thought of any natural or good way of coding it that involves a cut.
jgarland@kean.ucs.mun.ca (07/28/90)
In article <4921@munnari.oz.au>, ok@mudla.cs.mu.OZ.AU (Richard O'Keefe) writes: > In article <90207.090559F0O@psuvm.psu.edu>, F0O@psuvm.psu.edu writes: >> Players in a squash club are divided into three leagues, and players >> may only challenge members in their own league or the league below, >> if there is one. >> ** stuff deleted about not being able to do this using cuts as the ** book instructs >> Where have I gone astray? > (a) Why use Turbo Prolog when you could use ALS Prolog? matter of opinion, has been discussed before > (b) Why use a cut? > I've spent about half an hour thinking about this, and I haven't thought > of any natural or good way of coding it that involves a cut. quite right ****************************************************** I would like to point out that there is no reason to use cuts in Turbo (PDC) Prolog either. The User's Guide employs a bad example to make a point. ****************************************************** % This program picks out all legal challenges (i.e., x vs. y and y vs. x ). domains player = person(integer,symbol) % league name predicates nondeterm person(integer,symbol) % league name clauses % 3 Leagues, 3 Players / league % NOTE: Each league's list is sorted but programme does not depend on this. person(1,jim). person(1,kermit). person(1,larry). person(2,allen). person(2,barry). person(2,charles). person(3,xavier). person(3,yves). person(3,zachary). legal_challenges:- person(A,X), person(B,Y), X<>Y, % This discards possibility of playing self (A-B)<=0,(A-B)>=-1, % Note order of the conditionals here is impt. write(X," may challenge ",Y),nl, fail. goal legal_challenges. **************************************************************************** % This program picks out all legal games ( i.e., x and y may play). domains player = person(integer,symbol) % league name predicates nondeterm person(integer,symbol) % league name legal_games clauses % Three leagues, 3 Players / league % As above, sorted order within league is arbitrary person(1,jim). person(1,kermit). person(1,larry). person(2,allen). person(2,barry). person(2,charles). person(3,xavier). person(3,yves). person(3,zachary). legal_games:- % finds legal games in own league person(A,X),person(A,Y), X < Y, % discards reversed game (i.e. where X > Y) write(X," and ",Y," may play"),nl, fail. legal_games :- % finds legal games in lower league person(A,X),person(B,Y), A-B=-1, % Note that this *both* picks out lower league % *and* discards reversed game write(X," and ",Y," may play"),nl, fail. goal legal_games. ************************************************************************* If you still need help on your first problem, give me a shout by e-mail. John Garland Bitnet: jgarland@mun Internet: jgarland@kean.ucs.mun.ca