ASSIGNMENT 2. Due December 20.

Please submit the problems 1-5 in ONE Prolog file, where everything except the 
source code is put in the comments. The 6th problem should be submitted in a 
separate file (you can either draw it by hand and scan, or make drawing in some 
program).

--------------------------------------------------------------------------------
1. Write a predicate that starts interaction with the user, asking her
   to input a number, then another number, and then the operation (addition or
   multiplication). After that, the program performs the operation on the numbers
   and writes the result in a file. The process repeats until the user types
   'finish'. All the results should be written in one file. If the user makes a
   wrong input (it is not a number, or it is neither addition nor
   multiplication), the program should repeat the question, indicating that what    
   has been typed in is not a number, or is a wrong operation.

  IO predicates can be found in the Section 5 of the book. Check also the Prolog
  manual.
  
--------------------------------------------------------------------------------

2. Write a ternary predicate delete_all(item,list,result) that is true if result
   is obtained from 'list' by deleting all occurrences of 'item'. Use the cut to
   prevent backtracking. Sample run:

   ?-delete_all(a,[a,b,c,a,d,a],X).
   X=[b,c,d];
   false

   ?-delete_all(a,[b,c,d],X).
   X=[b,c,d];
   false

--------------------------------------------------------------------------------

3. Write a 4-ary predicate substitute_in_term(X, Y, T1, T2) that is true if the
   term T2 is the result of substituting the Prolog atom or number Y for all
   occurrences of the Prolog atom or number X in the term T1.
  
   Hint: You may want to use =.. (the built-in univ predicate).

   Sample runs:
   ?- substitute_in_term(a, 1, f(a,b,g(a,h(a))), X).
   X = f(1,b,g(1,h(1)))

   ?- substitute_in_term(a, 1, [a,b,c,a,d,a,e], X).
   X = [1,b,c,1,d,1,e]

   ?- substitute_in_term(a, 1, X, f(1,b,g(1,h(1)))).
   X = f(a,b,g(a,h(a)))

   ?- substitute_in_term(a, f(a), f(a,b,g(a,h(a))), X).
   false.
--------------------------------------------------------------------------------

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

--------------------------------------------------------------------------------

5. Write a Prolog program that solves the followng logic puzzle
   (from logic-puzzles.org).
  
 Figure out the earnings, first name, competition and the home town for each
 athlete using the clues given.
 Below are all categories and options used in this puzzle.

 Earnings: $54000, $128000, $137000, $200000 
 First Names: Abril, Esther, Hudson, Lindsay
 Competition: javelin, 400m relay, 100m hurdle, pole vault
 Towns: Worcester, Memphis, Birmingham, Gulfport


1. Of Hudson and the athlete who won the javelin competition, one earns $137,000
   per year and the other earns $54,000 per year.
2. Lindsay earns more than the athlete who won the 400m relay competition.
3. The person raised in Birmingham came away with the gold in the 100m hurdle
   competition.
4. Either the athlete who won the javelin competition or the athlete who won the
   pole vault competition is Esther.
5. The person raised in Gulfport is Lindsay.
6. The 4 people were the employee with the $200,000 salary, Abril, the person
   raised in Worcester, and the athlete who won the 100m hurdle competition.
7. The person raised in Memphis earns more than the athlete who won the javelin
   competition.
   
--------------------------------------------------------------------------------

6. 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. It is assumed that the following facts are currently 
in the database (in the top-down order): found(c), found(d), found(mark).  
--------------------------------------------------------------------------------