CPSC : Exercise 3 (Prolog) Solution

For this exercise you are expected to develop the programs below. You are expected to hand in a documented Prolog file (using the template which will be provided) 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 so-lution 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.

The last exercises, particularly (7), (8), and (9), are more challenging! Do the other exercises first!

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 mysubstring(X,Y) which succeeds when X occurs as contiguous sub-list 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 mysublists(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. A contact tracer is trying to work out who could have infected who in an office, given the various times (in days ago) the people in that office had met with each other:

met(john,28,mary). met(john,3,mary). met(peter,21,john). met(mary,23,mark). met(anne,19,peter). met(anne,29,john). met(anne,24,mary)). met(mark,17,paul).

...

When someone is infected, at a particular time, they are infectious for the next seven days, anyone they met within that time can be infected starting at the time of their meeting. The contact tracer having carefully collected the meeting times wishes to know, given that person A was infected n days ago whether the cause of person B being infected at time m could have been traced to person A’s infection. To establish this the contact tracer needs to establish a list of possible infection times – an infection pathway – caused by the meetings:

[infect(paul,17),infect(mark,23) ,infect(mary,28),infect(john,31)]


Thus, John was infected 31 days ago and met with Mary 28 days ago, who met with Mark 23 days ago, who, in turn met with Paul 17 days ago which may explain why Paul was sick 11 days ago!

The sequence of infections clearly must have strictly more recent times and each infection must be within the infectious window (so the times must be less than seven days apart). The path must start at the known infection (John 31 days ago) and end at the goal person whose infection one wishes to explain (Paul being infected): the start of the goal person’s infection must be within seven days of his observed infection (Paul being sick 11days ago).

Use the depth-first search capability of Prolog to write a predicate:

2

contact(infect(StartPerson,StartTime)

,infect(GoalPerson,GoalTime)

,InfectionPathway)

To uncover possible infection pathways in that office from a given starting infection to a given observed infection.

    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 tipsy.

        (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