Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!elroy.jpl.nasa.gov!ames!uhccux!virtue!comp.vuw.ac.nz!munnari.oz.au!mudla!ok
From: ok@mudla.cs.mu.OZ.AU (Richard O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Having a problem understanding the cut (arrgh!)
Message-ID: <4921@munnari.oz.au>
Date: 27 Jul 90 09:39:05 GMT
References: <90207.090559F0O@psuvm.psu.edu>
Sender: news@cs.mu.oz.au
Lines: 113

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.