CPSC : Exercise 3 (Prolog) Solution

For this exercise you are expected to develop at least 8 of the programs below. The tutorials will work through (some of) the solutions. You are expected to hand in a documented Prolog file containing your solutions ... I encourage you to discuss these programs with your classmates: the aim is to complete these exercises (somehow!) so that you get used to thinking in Prolog (which is very different from Haskell). You should comment your code indicating, in particular, from where you got the solution if it is not your own. Recall that it is important that you understand the solutions as this comprehension will be tested in the tutorial/lab written test.

Please name your predicates according to what is prescribed below.

    1. Write a predicate:

        (a) myappend(X,Y,Z) which succeeds precisely when Z is the two list X and Y appended together.

        (b) myreverse(X,Y) which succeeds precisely when Y is the list X reversed.

        (c) myflatten(X,Y) which succeeds precisely when Y is the list X flattened.

        (d) mymember(X,Y) which succeeds precisely when X is in the list Y.

        (e) Write a predicate myremove(X,Y,Z) which succeeds precisely when Z is the list Y with exactly one occurrence of X removed from Z.

    2. Write a predicate mymember2(X,Y) which succeeds precisely when there are two occur-rences of X in the list Y.

    3. Defined predicate substring(X,Y) which succeeds when X occurs as contiguous sublist of Y. Thus, [3,4,5] is a substring of [1,2,3,4,5,6] but [1,3,5] is not.

    4. Write a predicate sublists(X,S) which given a list in X provides the set of all sublists in S (here the sublist need not be contiguous). Can this predicate be reversed?

    5. Write a predicate mypermutation(X,Y) which succeeds when Y is a permutation of X as a list.

    6. Create a (small) database of your family with son and daughter relations such as:




1

daughter(’Mary Goddard’,’John Smith’,’Judi Goddard Smith’).

son(Mary Goddard’,’John Smith’,’Michael Smith’).

...

Then write predicates to encode the following relations:

grandfather(X,Y).

grandmother(X,Y).

brother(X,Y).

sister(X,Y).

sibling(X,Y).

cousin(X,Y).

...

    7. Given a relation specified by edges. For example

edge(a,b). edge(a,c). edge(a,d). edge(e,a). edge(c,a).

....

Write a predicate path(X,Y) which determines whether there is a (directed) path between any two nodes.

Can you modify the above path finding predicate to find the shortest path, shortpath(X,Y,L) (where L is the distance) between any two nodes?

    8. Write a Prolog program to solve the following logic puzzle. There are five houses in a row, each of which are a different color and are owned by men of different nationalities, who own different pets, prefer different drinks, and play a different sport.

        (a) The Irishman lives in the first house on the left.

        (b) The man who plays baseball lives in the house next to the man who keeps a tiger.

        (c) The occupant of the house, next to the house where the owner rides a horse, plays soccer.

        (d) The squash player drinks gin.

        (e) The Frenchman plays rugger.

        (f) The Irishman lives next to the blue house.

        (g) The Englishman lives in the red house.

        (h) The Spaniard is often seen taking his dog for a walk.

        (i) Beer is brewed (and drunk in large quantities) in the green house.

        (j) The Scotsman drinks whiskey and is often tipsey.

2

    (k) The green house is immediately to the right of the white house.

    (l) The tennis player owns snakes.

    (m) Soccer is played in the yellow house.

    (n) A lot of wine get consumed in the middle house.

Who owns the hamster? Who drinks orange juice?

    9. Solve the Josephus problem.

Josephus, a Jewish historian living in the 1st century was in the siege of Yodfat. He found himself with an accomplice as one of n soldiers trapped in a cave by the Romans. The soldiers after some discussion chose suicide over capture and settled on a serial method of committing suicide by drawing lots. They stood in a circle and counted down clockwise from a given number N (and a starting position): the man who uttered 0 then killed himself and the circle as a result shrank and the whole procedure was repeated starting at the man who stood (clockwise) next to the spot just vacated.

Josephus states that by luck – or possibly by the hand of God – he and his accomplice remained until the end. Then, when only he and his accomplice were left alive, they decided the whole suicide pack business was a bit crazy, and that they had a much better idea: they would surrender to the Romans!

The problem is where in a circle of n men given a countdown from N should Josephus and his accomplice place themselves?


































3