Assignment 9: Fun (and Games) with Prolog!
Due Monday, March 28 by 11:59 PM

This assignment is all Prolog all the time! The assignment has five parts. The first three parts are based on material from Tuesday's lecture. The last two parts (Towers of Hanoi and parsing) will be explained in class on Thursday -- give or take a day.

Please be sure to name your "functions" exactly as we've specified in the assignment. This is important since some of your code will be tested by an automatic code tester which will look for precisely these function names. (Keep in mind, too, that they're not really functions, but prolog predicates. This assignment might refer to them as functions at times, however...)

Note also that Prolog has some built-in "functions". In particular, Prolog has a built-in length(L, N) which is true if and only if list L has length N. Prolog also has a built-in append(A, B, C) which is true if and only if the result of appending list B to the end of list A results in list C. You are welcome to use these built-ins. You may also want to define your own helper "functions" as needed or other predicates that we defined in class, e.g., perm (that generates permutations), and member.

Part 1: The Simpsons and Prolog (5 Points)

• grandparent(X, Y) is true if and only if X is a grandparent of Y.
  
  
• cousins(X, Y) is true if and only if X and Y are first cousins. Note that a person cannot be their own cousin. Also, do not consider brothers and sisters to be cousins for this problem.
  
  
• hasYS(X) is true if and only if X has a younger sister. (Consider "younger" to mean strictly younger in age.)
  
  

Part 2: Lists in Prolog (15 Points)

• reverse(X, Y) is true if and only if list Y is the reversal of list X. Notice that you can use this rule to now actually compute the reversal R of a list by typing, for example, reverse([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. Submit your code in a file named part2.pl.

Part 3: The Game of 24! (30 Points)

This problem asks you to use Prolog to provide a solver for a generalized version of the game "Twenty-Four". In the original game, players view a card with four numbers on it and try to make an arithmetic combination of the numbers using the operators +, -, *, / so that the result is 24 (parentheses are allowed but are implicit). Each number must be used exactly once. Each operator can be used any number of times.

In our generalization of the game, the fixed number 24 is replaced with a variable, the set of operators is specified in a list, and the list of numbers can have any length, not just 4. (By definition, no result can be made if the list is empty.)

Define a 4-ary predicate solve such that

     solve(Ops, Values, Result, Tree)
  

 | ?- solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree).

 Tree = [*,[+,[-,3,2],5],4] 
 

This means that we have found a solution Tree using operators +, *, and - on that will combine with set of numbers [2, 3, 4, 5] to yield 24. You may assume that the set of operators will always be a subset of ['+', '*', '-', '/'] and that '/' denotes integer division. In prolog, '/' is performed using // (which is why 1-line comments in prolog are prefaced by % and not //).

Here is an eval predicate (for evaluating trees of opreations) that will be helpful in solving this problem. You may copy this code and use it freely. It is also available for you to copy from /cs/cs60/assignments/assignment9/part3.pl. You may also use any of Prolog's built-in rules and any helper rules that you like (including those that we wrote in class).

    eval(R, R) :- number(R).
    eval(['+', A, B], R) :- eval(A, AR), eval(B, BR), R is AR + BR.
    eval(['*', A, B], R) :- eval(A, AR), eval(B, BR), R is AR * BR.
    eval(['-', A, B], R) :- eval(A, AR), eval(B, BR), R is AR - BR.
    eval(['/', A, B], R) :- eval(A, AR), eval(B, BR), BR\==0, R is AR // BR.
 

Here are some other examples of solve in action:

  ?-  solve(['+'], [1, 1, 1, 1], 24, Tree).

  no.


  ?-  solve(['+'], [24], 24, Tree).

  Tree = 24


  ?-  solve(['+', '*', '-'], [1, 2, 3, 4], 24, Tree),

  Tree = [*,1,[*,2,[*,3,4]]]
 

Please submit this part of the assignment in a file called part3.pl.

Part 4: Towers of Hanoi (30 Points)

• The disks will be represented by positive integers. There will always be only three pegs but there may be any number of disks. The program must be able to handle an arbitrary number of disks.
  
  
• A configuration of the puzzle will be represented by a list of three lists. The first list contains the disks (from smallest to largest) on peg 1, the second list contains the disks (from smallest to largest) on peg 2, and the third list contains the disks (from smallest to largest) on peg 3. For example, the list

      [ [1, 2], [3, 4], [] ]
    

  represents disk 1 on top of disk 2 on peg 1, disk 3 on top of disk 4 on peg 2, and nothing on peg 3.
  
  
• The initial configuration contains all disks on peg 1. For the case of four disks, for example, the initial configuration would be

      [ [1, 2, 3, 4], [], [] ]
    

• The final configuration contains all disks on peg 3. For the case of four disks, for example, the final configuration would be

      [ [], [], [1, 2, 3, 4] ]
    

• The number "12" represents moving the top disk on peg 1 to peg 2. Similarly, the number "13" represents moving the top disk on peg 1 to peg 3. The other possible moves are "21", "23", "31", and "32". You should write a set of Prolog rules called valid which take as input a configuration, the move number, and a new configuration. The rule evaluates to true if and only if it is a valid move to go from the first configuration to the new configuration via that move. For example, consider the following input and output assuming just three disks are being used:

      | ?- valid([ [1, 2, 3], [], [] ], 12, [ [2, 3], [1], [] ]).
      yes
    

  This is valid because we went from the first configuration to the second configuration via move "12". Here's another example:

      | ?- valid([ [1, 2], [], [3] ], 12, [ [2], [], [1, 3] ]).
      no
    

  In this case, it's possible to move from the first configuration to the second configuration, but not by move "12". Here's yet another example:

      | ?- valid([ [1 , 2], [], [3] ], 31, [ [3, 1, 2], [], [] ]).
      no
    

  Although we did move a disk from peg 3 to peg 1 here, this move was invalid because disk 3 cannot be placed on top of disk 1.
  
  
• Once you've written the six valid move rules, you're almost done! (Write these rules and test them before going on!) Now, you'll write a rule called hanoi which takes as input a configuration and a list of moves. hanoi says "yes" if and only if starting at that configuration and making the sequence of moves described in the list results in getting to the final configuration. Here's an example using three disks:

       | ?- hanoi([ [1], [2], [3] ], [23, 13]).
       yes
    

  The answer here is "yes" because move "23" followed by "13" leaves us in the final configuration. Once this function is written, you can do the following:

      | ?- hanoi( [ [1, 2, 3], [], [] ], Solution).
      Solution = [12,13,21,13,12,31,12,31,21,23,12,13,21,13] 
    

  (Your Prolog program may find a different solution. The solution found depends on the order in which the rules were defined. As long as your Prolog program finds a correct solution, that's fine!)
  
  
• A few notes on this program:
  
  
  • You'll need to use dynamic and assert in much the same way that we did in the "alien, spampede, spam" problem that we saw in class.
    
    
  • If you run your hanoi search twice, it might succeed the first time and fail the second time! Why? Recall that as we discussed in class, the asserted facts are still present the second time (that is, the configurations are still marked as visited!). The easiest way to get around this (without leaving Prolog) is to retract all of the dynamic assertions:

            | ?- retractall(marked(_)).
            yes
          

    Then, you should be able to run it again... .

Part 5: Grammars in Prolog (20 Points)

In Assignment 7 you wrote a recursive descent parser in rex for a grammar for arithmetic expressions involving addition, multiplication, and exponentiation. In this assignment you will write a general "parse engine" in Prolog which will allow you to determine if a given string can be parsed by virtually ANY grammar that you give it! Amazing, but true!

Here, we won't ask for a parse tree, but we DO want to know if a particular input can be derived by a given grammar. In other words, we just want to know if there EXISTS a parse tree for a given string using the given grammar. For example, IF we had a grammar for the English language, we would be able to ask our parser if a particular sentence was valid in English. The neat thing is that we won't tell Prolog how to parse, we'll just tell it what a grammar is and what string we're interested in and ask: "Yo Prolog, can this string be parsed by the given grammar?"

Take a look at the files g0.pl,g1.pl, g2.pl, g3.pl and g4.pl supplied to you in /cs/cs60/assignments/assignment9/part5/. Each of these files specifies a different grammar. A grammar is specified by declaring the variables, terminals, and rules.

s -> v + s | v
v -> 0 | 1 

Here, s and v are the variables and 0 and 1 are the terminals. Notice that no upper-case letters are used. This is important, since Prolog uses upper-case letters to represent its own variables.

You can see how this grammar is specified in file gr0.pl Our convention is as follows: Variables are stated as facts. These facts simply state the names of the variables. In this example, the facts state that s and v are variables as shown below.

variable(s).
variable(v).

terminal(0).
terminal(1).
terminal(+).

rule(s, [v, +, s]).
rule(s, [v]).
rule(v, [0]).
rule(v, [1]).

Your task is to write a general-purpose parser. This file will contain the rules for a "function" called parse. As described in class, parse takes as input a sentential form and a list of symbols to parse and says "yes" if and only if the sentential form derives the list of symbols using a leftmost derivation for the grammar.

In particular, we will only test your parse predicate with two fully-instantiated lists: the first will be the list of the grammar's start variable (not a Prolog variable) and the second will be a list of symbols to be parsed by that grammar (also not a Prolog variable).

For example, here are some sample inputs and outputs:

| ?- reconsult('part5.pl').         <--- HERE WE ARE LOADING IN OUR parse PROGRAM
yes 

| ?- reconsult('g0.pl').            <--- HERE WE ARE LOADING IN A GRAMMAR
yes

| ?- parse([s], [1, +, 0, +, 1]).   <--- note that everything is instantiated...
yes

| ?- parse([s], [1, +]).
no

| ?- parse([s], [1, 0, +]).
no

You should write the parse inference rules in a file called part5.pl and submit that file. Keep in mind that although we will only call parse with a one-element list (of the start symbol) as a first argument, you may want to write the predicate more generally than this to help with recursion... .

Your code will assume that there are facts already defined for the grammar using the names variable, terminal, and rule as illustrated above. Keep your code simple and elegant and be sure to test it thoroughly on the supplied grammars before submitting it. This can be done using fewer than 10 new lines of Prolog code - if you are writing much more than that you are doing too much work!

Optional Bonus Problem

• Name your file bonus.pl.
• Write very clear documentation at the top of your file explaining what the game is, it's rules, and how to run your program.
• In the spirit of Prolog, your solution should specify the rules and constraints of the game and not the explicit algorithm for solving it!