As in homework 7, all programs should come with test cases, either automated or in comments.
Adventure in Prolog chap. 8 exercises 3 and 4: improve the genealogical database
Define a predicate dayInYear with three parameters: a
month number (1-12), a day in the month (1-31), and a day in the year
(1-365); it succeeds iff all three numbers are in the legal range and
the day in the year correctly reflects the specified date. For example,
dayInYear(2,5,36).should succeed because February 5th is the 36th day of the year, and
dayInYear(2,30,61).should fail because Feburary has no 30th.
Hint: you may want to use recursion on numbers, but you don't have to.
Your predicate should work correctly if all three parameters are bound; if any one of the three parameters is unbound; or if both the month and the dayInMonth are unbound. That is,
dayInYear(2,5,What).should return
What=36;
dayInYear(2,What,36).should return
What=5;
dayInYear(What,5,36).should return
What=2; and
dayInYear(Month,Day,36).should return
Month=2, Day=5.
The game "Six Degrees of Kevin Bacon" goes like this: you pick the name of a movie actor, and try to find a chain of connections from that actor to Kevin Bacon. A "connection" consists of two actors appearing in the same movie. For example, Harrison Ford was in "Star Wars" with Carrie Fisher, who was in "The Blues Brothers" with John Belushi, who was in "Animal House" with Kevin Bacon, so Harrison Ford is three degrees away from Kevin Bacon.
More generally, one could pick the names of any two movie actors (or directors or producers or whatever), and try to find how closely they are related to one another. Two actors who were in the same movie are one "degree" apart; two actors who were not in the same movie together, but they were each in a movie with the same other actor, are two "degrees" apart; and so on.
(If you're not interested in movies, you can do the same thing with rock bands, or even classes at Adelphi University.)
Write a predicate named in/2 expressing that a particular person was in a particular movie (or band, or Adelphi class, or whatever). Represent the person's name, and the name of the movie, both as Prolog atoms. Give at least a dozen examples, including at least one pair of people who are one degree apart, at least one pair of people who are two degrees apart, and at least one pair of people who are not related at all. (If you'd like, you can also add some facts about relationships other than appearing in movies, e.g. "these two actors are married to one another".)
(This part of the assignment should be extremely easy; it doesn't require any actual programming, only coming up with examples.)
Test your examples by asking a variety of queries: some with both arguments bound, some with only the person bound (i.e. "list all the movies this person was in"), some with only the movie bound ("list all the people who were in this movie"), etc.
Write a predicate named related/2 expressing that two actors were in a movie together (or married, or whatever), i.e. they are one "degree" apart.
Test your definition by asking a variety of queries: some with both arguments bound ("are these two people related?"), some with one argument bound ("who is related to this person?"), etc. Check that there are no asymmetries, situations in which Joe is related to Mary but Mary isn't related to Joe.
Write a predicate named degrees/3 expressing that two actors are a specified number of degrees apart.
For your first attempt, get this to work for degree 1, and then degrees 1 and 2. Once we've discussed arithmetic and recursion in Prolog, try to get it to work for any degree.
Test your definition by asking a variety of queries: some with all three arguments bound ("are these two people 2 degrees apart?"), some with both actors bound but the number unbound ("how far apart are these two people?"), some with one actor and the number bound ("who is one degree apart from this person?"), etc.
What happens when both actors in the query are the same? What happens when you ask Prolog for further answers after the first? What do you think should happen in these cases?
In the following problems, we'll define a
data structure posn representing an (x,y)
coordinate pair. Define the following predicates:
posn+ which takes in three posns and succeeds iff
the third is the coordinate-wise sum of the first two (for example,
posn+(posn(3,4),posn(5,-1),posn(8,3)).should succeed). You don't have to handle the case that either or both of the first two are unbound variables, but your definition should work whether the third is either bound or unbound.
posn- which takes in three posns and succeeds iff
the third is the coordinate-wise difference of the first two. As
before, you may assume the first two are bound, but not whether the
third is bound.posn* which takes in a number and two posns, and
succeeds iff the second posn is the number times the first posn. As
before, you may assume the number and the first posn are bound; for
extra credit, handle any one of the arguments being
unbound.posn-magnitude which takes in a posn and a number,
and succeeds iff the number is the magnitude of the posn. As before,
you may assume the posn is bound.
If you want to make things look a little more "natural",
consider that Prolog "knows" about infix operators like +, -,
*, etc. It only knows what they "mean" as applied to numbers
with the is built-in rule, but you can define your own rule
that allows you to write algebraic expressions on posns too.
evalPosn rule that takes in an
"expression" and a posn, and succeeds if the expression
"evaluates to" the posn. An "expression" can be
either
evalPosn(2*posn(3,4)-3*(posn(5,2)-posn(2,1)), What).and get the answer
What = posn(-3,5)
I think it's not much more difficult to also handle mixed-type expressions, i.e. each expression can be either a posn or a number. But I haven't done this yet, so I won't promise that it's easy; call it extra credit.