Assignment 8: Programming with Logic [100 Points]
Due Monday, November 5 by 11:59 PM

Please use the standard commenting convention of your name, file name, and date in each file. In addition, please have at least a one-line comment for each function that you implement. Finally, please BE SURE TO NAME YOUR FILES AND FUNCTIONS EXACTLY AS WE'VE SPECIFIED. The grading procedure for this assignment is partially automated and files and functions whose spellings differ from those below will cause our scripts to "barf".

Part 1: Movies and Prolog (30 Points)

1. directedBandits(Director) iff Director is the director of the movie  ['Bandits', 2001].
2. directedByBay(Movie) iff Movie is directed by 'Michael Bay'.
3. actressAfter1970(Actress) iff Actress was born after 1970.
4. player(Name, BirthPlace, Birthyear) iff either actor(Name, BirthPlace, Birthyear) or actress(Name, BirthPlace, Birthyear).
5. bornInLondon(Player) iff Player was born in ['London', 'England'].
6. playerAndDirector(Player) iff Player is a player that directed some movie.
7. playedAndDirected(Player) iff Player is a player that directed a movie in which he or she played.
8. playedMultiple(Player) iff Player played in more than one movie.
9. playedInComedy(Player) iff Player played in a comedy.
10. playedNotDirected(Director) iff Director directed some movies, but played in at least one movie he/she did not direct.
    

Part 2: Lists in Prolog (40 Points)

• myReverse(X, Y) is true if and only if list Y is the reversal of list X. DO NOT USE THE BUILT-IN REVERSE PREDICATE.  Notice that you can use this rule to now actually compute the reversal R of a list by typing, for example, myReverse([1, 2, 3], R). Make sure this works.
  
  
• occurs(X, L, N) is true if and only if item X occurs in list L exactly N times. Here is an example:

   | ?- occurs(spam, [oh, spam, spam, we, love, spam], X).
  
   X = 3 ;
   no
   

  When writing this predicate, be careful that it "computes" exactly the correct number of occurences (an easy pitfall is to write a version of this function that returns all values of X less than or equal to the number of occurences). Also, your occurs predicate should be able to generate the terms that occur a particular number of times, e.g.,

   | ?- occurs(T, [oh, spam, spam, we, love, spam], 3).
  
   T = spam ;
   no
   

• One-dimensional pattern matching is an important task in many applications such as cryptography and DNA sequencing. We'll encode a pattern as a list of items and we'll search for a pattern in another list called the "target". The rule find(Pattern, Target, Index) takes two lists Pattern and Target and a non-negative integer Index as input. This rule is true if and only if Pattern occurs inside list Target beginning at position Index. For example, here is a Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], 0).
   yes
   

  Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list).

   [1, 2, 1, 2, 1]
   ^
   |
   The pattern [1, 2] appears beginning right here at location 0.
   I'm looking for a 1 followed immediately by a 2 and I find it
   beginning here!
   

  It also occurs again at position 2 of the target.

   [1, 2, 1, 2, 1]
   ^
   |
   The pattern [1, 2] appears beginning right here at location
   2.
   

  Thus, here's another Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], 2). 
   yes
   

  In fact, these are the only two occurences as indicated by the following Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], X). 
  
   X = 0 ;
   X = 2 ;
   no
   

  find(P,T,I) should also work when both P and I are unbound variables. Write the rules for find. 
   
• remove(F, List, NewList) is true if and only if F is an element, List is a list (that contains no repeated elements and contains F), and NewList is a list identical to List except that F is not in Newlist. For example,

  | ?- remove(1, [2, 1, 3], [2, 3]).
  yes
  
  | ?- remove(1, [2, 1, 3], X).
  X = [2,3] ;
  no
  
  | ?- remove(1, [2, 3, 4], X).
  no
  
  | ?- remove(X, [1, 2, 3], [2, 3]).
  X = 1 ;
  no
  
  | ?- remove(X, [1, 2, 3], Y).
  X = 1,
  Y = [2,3] ;
  
  X = 2,
  Y = [1,3] ;
  
  X = 3,
  Y = [1,2] ;
  
  no
  

  Your remove rule must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You don't need to worry about the case that the second argument is a variable.

  Submit all your list code in a file named part2.pl.

  Part 3: Prolog Pancakes! (30 Points)

  Place the code for this part of the assignment in a file called part3.pl .

  You've been hired by the International Cottage of Pancakes (ICOP) to develop some software for their pancake chefs. A chef is presented with a stack of pancakes, each of different size. This stack is represented by a list. For example, the list [20, 10, 30] means that pancake with diameter 20 units is on the griddle, the pancake with diameter 10 units is on top of that pancake, the pancake with diameter 30 units is on the very top of the stack. (ICOP reinforces their pancakes with special ingredients to ensure that pancakes can be stacked with small pancakes below big ones!).

  ICOP wishes to serve their pancake stacks in sorted order from smallest at the bottom to largest at the top (for dramatic effect).

  A pancake chef can insert a flipper in any position in the stack and then flip the pancakes above the flipper (thus reversing their order) onto the stack of pancakes below the flipper. For example, by placing the flipper at position 1 in the stack [20, 10, 30], we would insert the flipper immediately above pancake 1, that is above the pancake with diameter 20. When we now flip, the pancakes above the flipper get reversed, resulting in the list [20, 30, 10]. If we now stick the flipper at position 0 in the stack [20, 30, 10], that is under the bottommost pancake, we would now flip and get [10, 30, 20]. Now, we can stick the flipper at possition 1 again (immediately above the pancake with diameter 10) and the flip results in the stack [10, 20, 30]. This stack is sorted and the chef is happy!

  Your job is to write a rule called pancakes(Stack, Number, Moves) which takes as input a list of pancakes called "Stack", an integer number "Number" indicating the number of flips to be performed, and a list "Moves" which contains exactly "Number" moves. pancakes(Stack, Number, Moves) is true if and only if the list of "Moves" contains exactly "Number" moves and these result in going from "Stack" to a sorted stack of the pancakes.

  Using the example above, we could type

  | ?- pancakes([20, 10, 30], 3, [1, 0, 1]).
  

  and prolog would say "yes".

  Now, make sure that your pancakes rule works EVEN when the third argument, the list of Moves, is a variable. This will be the only argument that might ever be used as a variable and it allows the chef to determine a sequence of flips to sort the pancakes. For example,

  | ?- pancakes([20, 10, 30], 3, X).
  X = [0,1,0] ;
  X = [1,0,1] ;
  no
  

  Notice that prolog found TWO different ways to sort the pancakes in 3 moves. (Check to make sure that you agree that both solutions are valid!)

  Notice also that the "Stack" may be arbitrarily large, but will never contain two pancakes of the same size.

  Your job is to write "pancakes" in prolog! It may be helpful to use the built-in "length" and "append" rules. It may also be helpful to you to use the "reverse" rule from above, and the "sorted" rule from lecture.  Here is sorted (reverse is up to you):
  

  sorted([]).
  sorted([_]).
  sorted([X, Y | Rest]) :- X < Y, sorted([Y | Rest]).