ASSIGNMENT 2. Due December 19.
=============================

Total points: 40

==============================================================
1. 4 points.

  Write a binary predicate count_occurrences(input, result) that is
  true if 'result' is a list of two-element lists [el, number_of_occurrences_in_input],
  where 'el' is an element of the list 'input', and 'number_of_occurrences_in_input'
  is an integer specifying how many times 'el' occurs in 'input'.

  For each element 'el' in 'input' there should be a corresponding pair
  [el, number_of_occurrences_in_input] in 'result'.


  Sample run:

?- count_occurrences([a,b,c,a,b,c,d], X).
X = [[d, 1], [c, 2], [b, 2], [a, 2]].

?- count_occurrences([], X).
X = [].
  
===============================================================

2. 4 points.

   Write a predicate count_and_print_occurrences that starts a dialog
   with the user, asking her/him to provide a list. Then it calls the
   count_occurrences predicate to calculate the occurrences of elements
   in the provided list, prints the result on the screen and repeats
   the process asking again to provide a list. The user can stop
   interaction by typing 'stop'. If a non-list term is provided, the
   program should repeat the request.

  A sample run:

?- count_and_print_occurrences.
Enter a list, or type stop to stop:
|: [a,a,b,c,c,c].
The element c occurs in the input list 3 times.
The element b occurs in the input list once.
The element a occurs in the input list twice.
No other element occurs in the input list.

Enter a list, or type stop to stop:
|: [a,a,b,b,b,b,c,c,c].
The element c occurs in the input list 3 times.
The element b occurs in the input list 4 times.
The element a occurs in the input list twice.
No other element occurs in the input list.

Enter a list, or type stop to stop:
|: [a,b,c,a,b,c,a,a,b].
The element b occurs in the input list 3 times.
The element a occurs in the input list 4 times.
The element c occurs in the input list twice.
No other element occurs in the input list.

Enter a list, or type stop to stop:
|: [a,b,f(a),b].
The element b occurs in the input list twice.
The element f(a) occurs in the input list once.
The element a occurs in the input list once.
No other element occurs in the input list.

Enter a list, or type stop to stop:
|: f(a).
Enter a list, or type stop to stop:
|: stop.
true.

=================================================================

3. 3 points.
  
  Write a predicate merge(L1,L2,L) which is satisfied by the ordered
  (with respect to the standard order) lists of terms L1, L2, and L
  so that L is the result of merging L1 and L2.

  Sample runs:

?- merge([1,2,5], [2,4,6,8], L).
L = [1, 2, 2, 4, 5, 6, 8] ;
false.

?- merge([1,2,5,6,7,8], [2,4,6,8], L).
L = [1, 2, 2, 4, 5, 6, 6, 7, 8, 8] ;
false.

?- merge([1,3,5,7,9,c,d], [a,b,c], L).
L = [1, 3, 5, 7, 9, a, b, c, c, d] ;
false.

?- merge([1,2,3,f(a),f(b)], [a,b,c], L).
L = [1, 2, 3, a, b, c, f(a), f(b)] ;
false.

?- merge([1,2,3,b,c,d], [a,b,c], L).
L = [1, 2, 3, a, b, b, c, c, d] ;
false.

?- merge([], [], L).
L = [].

?- merge([], [a,b,c], L).
L = [a, b, c].

?- merge([], [a,b,c], [a,b,c]).
true.

?- merge([a,a], [a,b,c], [a,b,c]).
false.


==========================================================

4. 3 points.
  
   Write a program to compute the list of all triples [X,Y,Z]
   where
     - X, Y,, and Z are different integers between 0 and 9
       (both included), and
     - (10*X+Y)/(10*Y+Z) equals X/Z.

?- good_triples(L).
L = [[1, 6, 4], [1, 9, 5], [2, 6, 5], [4, 9, 8]].  

=========================================================

5. 5 points.

   Consider the program for findall:

findall(X, G, _) :-
    asserta(found(mark)),
    call(G),
    asserta(found(X)),
    fail.

findall(_, _, L) :-
    collect_found([], M),
    !,
    L=M.

collect_found(S, L) :-
    getnext(X),
    !,
    collect_found([X|S], L).
collect_found(L, L).

getnext(X) :-
    retract(found(X)),
    !,
    X \== mark.

Let collect_found([a,b], L) be the goal. Draw the complete derivation tree
for this goal as discussed in the lecture, indicating the parts of the tree
cut by the cut predicate.

===================================================================

6. 4 points.

   Given a list of elements colored red, white, and blue, reorder
   the list so that all the red elements appear first, then all the
   white elements, followed by the blue elements. The reordering should
   preserve the original relative order of elements of the same color.

   Use difference lists.
  
Sample run:

?- reorder([red(1), white(2), blue(3), red(4), white(5)], Reordered).

Reordered = [red(1), red(4), white(2), white(5), blue(3)];
false

==================================================================

7. 4 points
  
  Write a program that removes duplicate elements from a list.
  Write two versions of the corresponding predicate,
  without_doubles_1(L1, L2) and without_doubles_2(L1, L2),
  where in both of them L2 the list of the elements appearing
  in L1 without duplication, and
    - in without_doubles_1(L1, L2), the elements of L2 are
      in the same order as in L1 with the last duplicate values
      being kept.
    - in without_doubles_2(L1, L2), the elements in L2 are in
      the reversed order of Xs with the first duplicate values
      being kept.


Sample runs:

?- without_doubles_1([1,2,3,4,5,6,4,4],X).
X = [1, 2, 3, 5, 6, 4];
false

?- without_doubles_2([1,2,3,4,5,6,4,4],X).
X = [6, 5, 4, 3, 2, 1];
false

==========================================================

8. 5 points
  
   Write a Prolog program that solves the followng logic puzzle (from logic-puzzles.org).
  
   Figure out the first name, wine, entree, and price for each person using the clues given.
   Below are all categories and options used in this puzzle.

   First names: Lynda, Nick, Robin, Virginia
   Wines: bordeaux, chianti, merlot, shiraz
   Entrees: beef stir-fry, citrus chicken, filet mignon, red snapper
   Prices: $24.99, $25.99, $26.99, $27.99

   Clues:

    1. The diner who ordered the red snapper didn't have the bordeaux.
    2. Lynda paid less than the one who had the bordeaux.
    3. Neither the one who had the bordeaux nor the one who had the chianti was the person who paid $26.99.
    4. The diner who ordered the beef stir-fry had the chianti.
    5. The diner who ordered the citrus chicken paid 1 dollar less than the one who had the chianti.
    6. The diner who ordered the filet mignon paid less than the one who had the shiraz.
    7. Virginia was either the diner who ordered the beef stir-fry or the diner who ordered the red snapper.
    8. The one who had the merlot paid 1 dollar less than Robin.

======================================================

9. 6 points.

  Implement the predicate occurs(Var, Term) that succeeds if
  the Prolog variable Var occurs in the Prolog term Term, and
  fails otherwise.

Sample runs:
  ?- occurs(X, f(X)).
  true.

  ?- occurs(X, f(Y)).
  false.

  ?- occurs(X, f(a,g(b,h(X,c),d))).
  true.

  ?- occurs(X, X).
  true.

  ?- occurs(x, f(x)).
  false.

  ?- occurs(x, x).
  false.

  ?- occurs(x, f(X)).
  false.

===========================================================

10. 2 points.  
  
    Write a predicate twice_as_long(L1,L2) that succeeds if
    the list L2 is twice as long as the list L1.

    Do NOT compute the lengths of the lists.

Sample run:

?- twice_as_long([],[]).
true.

?- twice_as_long([a],[1,2]).
true.

?- twice_as_long([a,b],X).
X = [_G328, _G331, _G334, _G337] ;
false