CSC3030 Programming Paradigms Practical Exercises (30%) 1995. You must write MuProlog programs to solve the problems below. The single source file containing your solution to exercise 1, 2 or 3, must be submitted electronically using the Unix `submit' command (not email) before the appropriate deadline. You must make each submission exactly as required so that it can undergo standard tests. You can make repeated submissions but only the last one is kept. Submit will not accept solutions after the deadline. If there is any system fault with the submit command near to a deadline then give a paper copy of your solution to me (or hand it in to the Dept. office) before the deadline (!) and also mail it electronically - I will check that the copies are identical. The objective is for you to become familiar with the features of MuProlog and to get an idea of the Prolog style of programming. Prolog is very different from languages like C and Pascal. I do not necessarily expect you to become an expert in Prolog but you should make a serious attempt to get into the Prolog way of thinking and should not just recode C into Prolog. Try to avoid the use of non-logical features such as assert, retract, cut etc. Warning: there may be subtle differences if you use some other "brand" of Prolog, eg. on a home computer. It is your responsibility to correct for these. All assessment will be in terms of MuProlog. ------------------------------------------------------------------------------- Ex1: by end of week 3: 5.00pm Friday 17 March 1995 *************************** Use the example file `windsor.pro' as the database of facts for this exercise. (windsor.pro may grow as more data is found.) Create a MuProlog program in a single file called `relations.pro'. Your program must define the following predicates before(D1, D2) /* true iff date D1=date(...) is before date D2 */ parent(C, P) /* true iff P is a parent of C */ grandparent(C, G) /* true iff G is a grandparent of C */ sibling(S1, S2) /* true iff S1 and S2 are siblings */ aunt(N, A) /* true iff A is an aunt of N (see the notes) */ uncle(N, U) /* true iff U is an uncle of N (see the notes) */ cousin(C1, C2) /* true iff C1 and C2 are (1st) cousins */ married(W, M, D) /* true iff W and M married as of date D */ and heir(X, Y, D) /* true iff Y is the heir of X as of date D */ The predicates should be defined in exactly these forms as they will undergo standard tests. They should work with ground and unground parameters. Do not include the facts from `windsor.pro' in your file `relations.pro'. Your predicates should work with other databases of facts. The notes on toy-Prolog will give you some ideas. The program will be run by (i) consulting `windsor.pro' (possibly modified!) (ii) consulting `relations.pro' (yours, it should consult no files itself!) (iii) evaluating certain queries. Submit your file `relations.pro' using the `submit' program. Do not submit any other files. You can resubmit `relations.pro' up to the deadline but only the last version submitted will be kept. *** NB. I have changed married() to wed() in windsor.pro *** *** to avoid a name-clash with the assignment [6/3/95] *** ------------------------------------------------------------------------------- Ex2: by end of week 6: 5.00pm Friday 7 April 1995 **************************** The stable-marriage problem: There are n men and n women. Each woman wants to marry a man and each man wants to marry a woman. Each woman lists the men in her order of preference, from first to last. Each man lists the women in his order of preference, from first to last. A set of marriages is `stable' if it does not contain any examples of marriages (m1,w1) and (m2,w2) where m1 prefers w2 to w1 and w2 prefers m1 to m2 (or m1 and w2 would "run off" together). Write a MuProlog program `marriage.pro' to find a set of stable marriages of all the men and women. It must take data from a file `prefer' of the form: n -- number, line 1 m11 m12 ... m1n -- woman 1's preferences, first to last m21 m22 ... m2n ... mn1 mn2 ... mnn -- woman n's preferences w11 w12 ... w1n -- man 1's preferences 1st to last ... wn1 wn2 ... wnn -- man n's preferences, line 2*n+1 eg. 3 1 2 3 1 3 2 2 3 1 3 2 1 2 1 3 1 3 2 A single space will separate preferences. Do not submit `prefer'; it will be provided. When your program is `consulted' it should solve the problem specified in the file `prefer' and print one solution in the form: (m1,w1) (m2,w2) .... (mn,wn) Notes: `Stable' does not necessarily mean happy! There are always `male optimal' and `female optimal' solutions which may or may not be different; it pays to take the initiative. The problem is equivalent to the University Admissions problem and to many other matching problems. Submit your file `marriage.pro' using the `submit' program. ------------------------------------------------------------------------------- Ex3: by end of week 9: 5.00pm Friday 5 May 1995 ****************************** Write a MuProlog program to solve cryptic arithmetic puzzles of the form `word1+word2+...=word'. eg. SEVEN+THREE+TWO=TWELVE Each letter represents a different digit. Leading letters cannot be zero. The puzzles obey the normal laws of decimal arithmetic. Find out what digit each letter represents (there can be multiple solutions). Try to write an efficient program. Do not enumerate all 10! permutations; it is a big number. Your program must be submitted in a single file called `cryptic.pro'. When consulted, it must take data from a file (provided) called `puzzle' which will contain one or more puzzles, one to a line, without spaces. It should print all solutions to the puzzle(s) with the letters replaced by the correct digits. Submit your file `cryptic.pro' using the `submit' program. ------------------------------------------------------------------------------- Marking: All solutions will be marked at demonstrations lasting 20 to 30 minutes at times to be arranged starting week 10: *** Monday 8 May 1995 *** onwards. You will be marked on your understanding of both Prolog and your solutions to the exercises. You will be asked about alternative solutions to the exercises and also about *** different problems altogether *** (eg. sorting, traversals, combinatorics, ...). Be sure to review all exercises and your solutions before the demonstration! ------------------------------------------------------------------------------- L. Allison, Dept. Computer Science, Monash University, 1995