ASSIGNMENT 2. Due December 18.
----------------------------


1. Write a predicate substitute(X,Y,Xs,Ys) that is true if the list Ys is the result of
substituting Y for all occurrences of X in the list Xs.

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

2. Write a predicate without_doubles_1(Xs, Ys) that is true if Ys is
the list of the elements appearing in Xs without duplication. The
elements in Ys are in the same order as in Xs with the last
duplicate values being kept.

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

No

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

3. Write a predicate without_doubles_2(Xs, Ys) that is true if Ys is
the list of the elements appearing in Xs without duplication. The
elements in Ys are in the reversed order of Xs with the first
duplicate values being kept.

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

No

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

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.
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)];

no

Write two versions of the reordering program: with and without difference
lists.

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

5. 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 cut to prevent backtracking.
Sample run:

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

X=[b,c,d];

No


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

X=[b,c,d];

No

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

6. Write a ternary predicate delete_nth that deletes every N'th element from a list. 
Sample runs:

?- delete_nth([a,b,c,d,e,f],2,L).

L = [a, c, e] ;

No
?- delete_nth([a,b,c,d,e,f],1,L).

L = [] ;

No
?- delete_nth([a,b,c,d,e,f],0,L).

No
?- delete_nth([a,b,c,d,e,f],10,L).

L = [a, b, c, d, e, f] ;

No

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

7. 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 Prolog manual.

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

8. Write a predicate merge(L1,L2,L) which is satisfied by the ordered lists of
integers L1, L2, and L so that L is the result of merging L1 and L2.

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


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

9. Write the following as a set of Prolog predicates:

Eat at the restaurant if it looks nice but if it stinks don't eat there

using:
(a) cut and fail combination
(b) the '\+'  predicate.

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

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