CSc 8710 Deductive Databases and Logic Programming
Fall 1998
Programming Assignment #1
September 14, 1998 (Monday)

1.

Write a Prolog Program for rotate_left(L,M), where M is a list obtained by rotating left by one position all the elements of list L. For example, the list [a,b,c] becomes [b,c,a].

2.

Write a Prolog Program for sum_last_three(L,N), where N is the sum of the last three numbers in a list L of numbers. If the list L has fewer than three numbers, then N is the sum of all the numbers in L.

3.

Write a Prolog program to flatten a list. For example, the following goal should succeed:

?- flatten([a,[b,c],[[d],[],e]], [a,b,c,d,e]).

4.

Write a Prolog program for double(List,ListList), where every element of List appears twice in ListList. For example, the following goal should succeed:

?- double([1,2,3],[1,1,2,2,3,3]).

5.

Write a Prolog program which defines a relation, count_atoms(L,N), which computes the number of atoms present in list L at all the levels. This is very similar to flatten. For example, the following should succeed:

6.

Write a Prolog program which defines the relation, nth_member(N,L,X), which is true if X is the Nth member of list L. For example, the following should succeed:

7.

Write a Prolog program which defines the relation frequencies(L,M), where L is any list with possibly duplicate elements and M is a list of pairs which contains the number of times each element appears in the list L. For example the following should succeed:

8.

The Towers of Hanoi is a game played with three poles, called left pole, center pole, and right pole, and a set of N discs, each with a different diameter. The discs fit onto the poles by means of a hole cut through the center of each disc. Initially, all the discs are placed on the left pole. The object of the game is to move all the discs to the right pole. The center pole may be used as a spare pole, a temporary resting place for the discs. Only the top disc on any pole can be moved and at no time can a larger disc be on top of a smaller disc. A simple recursive solution to this problem is to move (N-1) discs from left pole to center pole, then move the last disc to the right pole, and finally move the (N-1) discs from center pole to the right pole.

Implement the Towers of Hanoi problem in Prolog. You must use the I/O relations of Prolog to output the solution. You need to define a predicate hanoi(N) whose input N is the number of discs. Upon execution of the query hanoi(N) the solution must be printed on the screen. You will need the following I/O relations:

(a)

nl: This will print a new line on the screen.

(b)

write: This relation takes in a term as input and prints the term on the screen. Some examples: write(aaa) will print aaa and write('move disc from ') will print move disc from .

9.

Write a Prolog program to solve the following logic puzzle:

There are five houses in a row, each of a different color and inhabited by a man of a different nationality, with a different pet, drink and brand of cigarettes.

The following are the clues to the puzzle:

(a)

The Englishman lives in the red house.

(b)

The Spaniard owns the dog.

(c)

Coffee is drunk in the green house.

(d)

The Ukrainian drinks tea.

(e)

The green house is immediately to the right (your right) of the ivory house.

(f)

The Winston smoker owns snails.

(g)

Kools are smoked in the yellow house.

(h)

Milk is drunk in the middle house.

(i)

The Norwegian lives in the first house on the left.

(j)

The man who smokes Chesterfields lives in the house next to the man with the fox.

(k)

Kools are smoked in the house next to the house where the horse is kept.

(l)

The Lucky Strike smoker drinks orange juice.

(m)

The Japanese smokes Parliaments.

(n)

The Norwegian lives next to the blue house.

Who owns the Zebra? Who drinks water?
Define a relation zebra_puzzle(Zebra_Owner,Water_Drinker) which will return the solution to the puzzle.