CSc 8710
Fall 2003
HW 2 (Due: Thursday, 18 September)
----------------------------------

(1) Write a predicate sum_pairs(L1,L2) which is true if and only if, 
    for each item in L2 in position i (except for the last position) 
    of L2 equals the sum of items in position i and i+1 in L1. The 
    last element in L1 and L2 must be the same. This also implies 
    that the two lists are of the same length.

    Sample runs:

  |?- sum_pairs([1,2,1],[3,3,1]).
  yes
  |?- sum_pairs([1,4,6,4,1],X).
  X = [5,10,10,5,1]
  yes

(2) Pascal's triangle is:

    row 0:         1
    row 1:       1   1
    row 2:     1   2   1
    row 3:   1   3   3   1
    row 4: 1   4   6   4   1
    ...
    ...
    Informally, each number is the sum of the two numbers above it. The 
    following is a way to index the numbers:

    Row i: P(i,0) P(i,1) P(i,2)....P(i,i) 
    The individual values are defined recursively as follows:

    P(i,0) = 1
    P(i,i) = 1
    P(i,j) = P(i-1,j-1) + P(i-1,j)

    Write a predicate pascal(X,L) that is true if and only of L is row X
    in the Pascal's triangle. Sample runs:

    |?- pascal(3,[1,3,3,1]).
    yes
    |?- pascal(4,[1,4,6,4,1]).
    yes
    |?- pascal(0,[1]).
    yes


(3) Write the predicate 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. Sample run:

    |?- frequencies([a,b,a,e,e,f,d,b,a,b],X).
    X = [[a,3],[b,3],[d,1],[e,2],[f,1]]
    yes

(4) Write a predicate magicTriangle(L,M) which generates a solution to the
    magic triangle problem: Given 6 integers, place each of them at a vertex
    or in the middle of a side such that the sum of the 3 numbers on each side
    is the same. List L contains the 6 input integers and M should contain
    the same 6 integers in order (starting from top vertex going clockwise
    (assuming the triangle is sitting horizontally with two vertices on a 
     horizontal line and the third vertex above). Sample run:

   ?- magic([20,18,10,8,-4,-2],M).
   M = [20, 8, -2, 18, 10, -4] 
   Yes