ASSIGNMENT 3. Due January 12.
----------------------------

1. 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 'not' predicate.

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

2.  Consider the following program that defines the predicate 'insert'.
The predicate is satisfied if its third argument is a sorted list obtained
from its second argument, also a sorted list, by inserting in it the first
argument:

  insert(X,[H|T],[H|T1]) :- X>H, !, insert(X,T,T1).
  insert(X,L,[X|L]).

   1. Provide an appropriate query to show that this program is incorrect
      with respect to the given specification.
   2. Change the program so that it works correctly

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

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

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

4. 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,a,a,b,c],X).

X = [[c, 1], [b, 2], [a, 3]] ;

No

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

5. Write a predicate count_and_print_occurrences that first asks the user
to provide a list, then asks where to print the output (on the screen or
in a file), counts occurrences in the list using the program developed
in the exercise 4 above, and prints the output either on the screen or in a
file specified by the user as follows: If, for instance, the count_occurrences
program computes the answer [[c, 1], [b, 2], [a, 3]], then
count_and_print_occurrences should print the following:

c occurs in the input once.
b occurs in the input twice.
a occurs in the input 3 times.
No other element occurs in the input.

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


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. Is the predicate p defined below tail recursive? Justify your answer.

p([H|T]):-q,p(T).
p([]).
q.

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

8. Implement the unification algorithm discussed on the lecture.

You can not use the predicate unify_with_occurs_check and
Prolog flag setting for occur_check in this exercise.

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

9. Write three binary predicates pre_order, in_order, and post_order that for a given
   binary tree return a list that corresponds respectively preorder, inorder, and
   postorder traversal of the tree.

   To traverse a non-empty binary tree in preorder, perform the following operations:

   1. Visit the root.
   2. Traverse the left subtree in preorder.
   3. Traverse the right subtree in preorder.

   To traverse a non-empty binary tree in inorder, perform the following operations:

   1. Traverse the left subtree in inorder.
   2. Visit the root.
   3. Traverse the right subtree in inorder.

   To traverse a non-empty binary tree in postorder, perform the following operations:

   1. Traverse the left subtree in postorder.
   2. Traverse the right subtree in postorder.
   3. Visit the root.

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

10. Solve the following puzzle (from Edi Weitz).

Three mice are living next to each other in three holes in the wall. Each mouse
has a favorite cheese flavor and a favorite TV show. Here are the hints:

1. Mice: Mickey, Mighty and Minny.
2. Cheese: Gouda, Emmentaler, Brie.
3. Shows: Emergency Room, Seinfeld, Simpsons.
4. Mickey Mouse loves Gouda.
5. Mighty Mouse's favorite TV show is Emergency Room.
6. The mouse that lives in the left hole never misses an episode of Seinfeld.
7. Mickey Mouse and Mighty Mouse have one mouse hole between them.
8. The Simpsons fan does not live on the left of the Brie lover.

For each mouse find the hole where it leaves, a favorite cheese and a favorite show.