- [25 points] Write and test a Prolog program pl that deals with family relations. Assume that the predicate parent(X,Y), meaning that X is a parent of Y has al- ready been defined (and that the definition is loaded separately).
Your program’s job is to define the following predicates:
|
ancestor(X,Y), meaning that X is an ancestor of Y, i.e. either X is a parent of Y or X is an ancestor of someone who is a parent of Y;
|
common ancestor(X,Y,Z), meaning that X is a common ancestor of Y
and Z, i.e. X is an ancestor of both Y and Z;
|
closest common ancestor(X,Y,Z), meaning that X is a closest com- mon ancestor of Y and Z, i.e. X is a common ancestor of Y and Z and no child of X is a common ancestor of Y and Z;
|
ancestorList(X,Y,L), which holds iff X is an ancestor of Y and L is a list of the decendants of X (i.e., people whose ancestor is X) that are an- cestors of Y ordered from the closest to the farthest from X; e.g. if john is a parent of paul who is a parent of henry who is a parent of helen, then
ancestorList(john,helen,L) should succeed with L = [paul,henry]
being returned;
|
descendantTree(X,L), which holds iff L is a list structure representing the tree of all descendants of X; each node in the tree of descendants should be represented by a list whose first element is the node label and the remaining el- ements are the representations of its children if any; e.g. if john’s children are paul and mary, paul’s children are henry and june, henry’s only child is helen, mary’s only child is adam, and neither adam nor june nor helen have any children, then descendantTree(john,L) should succeed with
L =
[john,
[paul,
[henry, [helen]
],
[june]
],
[mary,
[adam]
]
]
being returned (indentations and line breaks have been added here for readabil- ity, but your program should not do this).
You may define some auxiliary relations if that helps in defining the ones above. Test your program thoroughly before submitting it. Document your code appropriately. Do not include any parent(X,Y) facts in your file.
- [20 points] Write and test a Prolog program pl that solves the following puzzle:
The police are trying to track down the gang of three kids who have been stealing pumpkins. So far, they have established the following facts: the kids’ first names are Angela, Mary, and David; one is 5, one is 7, and one is 8; one has the last name Diamond, and the one with the last name Grant is 3 years older than the one with the last name Leung. You can assume Angela and Mary are female and David is male.
Use the technique shown in the zebra example discussed in class (the code is available on the course web page) to find missing information on the gang: each child’s age, gender, first name and last name, consistent with the data above. (Encode the above data as is and do not add additional facts.)
Use your Prolog code to show whether or not the computed information uniquely identifies the culprits; submit these test results in the file q2tests.txt, together with the program file. Document your code appropriately.