CPSC 453, Spring 2003
Second Assignment
These Prolog programming exercises are due in class next Wednesday, January 29. You can copy the file /home/cs225/prolog/family.pl and add your solutions to all these exercises to that file. Turn in a printout of the file and make sure that it is available in your account for me to test. You should not attempt to do the Exercise 4 until after Friday's class.
Exercise 1: Add definitions for the following relationships to those already defined in the program that we looked at in class, /home/cs225/prolog/family.pl:
- married(X,Y). Let's be tradtionalist and say that X and Y are married if they are parents of the same child. (Childless couples would have to be entered explicitely into the database of facts).
- uncle(X,Y). Meaning that X is an uncle of Y. Don't forget that your aunt's husband is also your uncle.
- aunt(X,Y).
- stepchild(X,Y). Meaning that X is Y's stepchild, that is X is a child of someone who is married to Y but is not Y's child.
Exercise 2: (Number 4 on page 676 of the text.) Design a Prolog program unique(Bag,Set) that takes a Bag (that is, a list that might contain duplicate elements) and returns a Set (that is, a list with no duplicates).
Exercise 3: (From number 5 on page 676 of the text.) Write a Prolog program to count all the atoms contained, either directly or indirectly, in a list. That is, write deepCount(List,Num), where List is a list which can contain sub-lists which themselves can contain sublists, and so on. deepCount should set Count to be the total number of atoms in the list at all levels. For example,
deepCount([a,[b,c],b,[[a,b],d]],N)would set N equal to 7. Assume that the lists contain only atoms and other lists. You can test whether a variable X is bound to an atom by using the predicate atom(X).
Exercise 4: (From number 7 on page 676 of the text. This is a standard problem, except that it's usually assumed that the cannibals will eat the missionaries if they are in the majority, and the problem is to avoid this. This is a more politically correct version, I guess.) Three missionaries and three cannibals come to the bank of a river they wish to cross. There is a boat that will hold only two people. Everyone is capable of rowing the boat. If there are ever more missionaries than cannibals on one side of the river, then the cannibals will get converted. The problem is to find a sequence of moves that will get everyone across the river with no conversions. Write a Prolog program that will do this. You will have to design a representation of the possible problem states and a way of specifying the legal moves. Your program should find and print a list of moves that solves the problem.