CS 60, Assignment 9

Computer Science 60
Principles of Computer Science
Spring 2004

Assignment 9: Fun (and Games) with Prolog!
Due Monday, March 29 before midnight.

This assignment is all Prolog all the time! Please be sure to name your Prolog rules 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 names.

Recall that to start Prolog you simply type "prolog" on turing. All Prolog files should end with the suffix .pl. To load in a file such as myfile.pl you should type the following at the prolog prompt:

?- [myfile].

Note that the .pl suffix is not included here and the period is important. Prolog expects everything to end with a period. Type halt to end Prolog.

Recall that "," is the symbol for AND, ";" is the SYMBOL for OR, and "\+" is the symbol for NOT. Please review the class notes for other Prolog syntax, including the difference between "==", "=", and "is" and also the difference between the "not equals" operators "\==" and "=\=".

Note also that Prolog has some built-in rules. 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 rules as needed.

Part 1: The Simpsons Meet Prolog (15 Points)

In the directory /cs/cs60/assignments/assignment9 you will find a file called part1.pl. Copy this file into your own directory. This file contains an expanded database of the Simpsons family with many facts. Begin by taking a close look at the kinds of facts provided in that file.

You should add the rules below to this file. You may add any additional helper rules that you wish, including anything that we looked at in class.

grandparent(X, Y) is true if and only if X is a grandparent of Y.
granddaughter(X, Y) is true if X is a granddaughter 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. Brothers and sisters are also generally not cousins!
hasMGD(X) (pronounced "has many granddaughters") if and only if X has more than one granddaughter.
hasYS(X) (pronounced "has younger sibling") if and only if X has a younger sibling.

Your file should be called part1.pl and submit it using cs60submit.

Part 2: Lists in Prolog (15 Points)

Now, you will write two Prolog rules for lists. Please submit these rules rules in one file called part2.pl using cs60submit. Again, you may use any helper rules that you like. In particular, some of the rules that we saw in class may be useful to you here. You may implement and use any of them.

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 of a list by typing, for example, reverse([1, 2, 3], X). 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 function, be careful that it "computes" exactly the correct number of occurrences (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 occurrences).

Part 3: Pattern Matching in Prolog! (10 Points)

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 0 as indicated by the following Prolog query and response:

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

      X = 0 ;
      X = 2 ;
      no

Write the rules for find. It might be handy to write some helper "functions" to make find easier. Submit your code in a file named part3.pl.

Part 4: Towers of Hanoi (30 Points)

In this part of the assignment, you will write a Prolog program to solve the Towers of Hanoi puzzle. Please submit your solution in a file called part4.pl. You should carefully review the "fox, hare, and lettuce" solution that we wrote in class before embarking on this program. You can find a copy of that puzzle in /cs/cs60/assignments/assignment9/part4/fox.pl. The big ideas in the fox puzzle and the hanoi puzzle are very similar. Fortunately though, the Hanoi program is considerably shorter! (You should expect your program to be about 20 lines of Prolog code, not including comments and spacing between rules.)

Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer correct solutions to the puzzle. Here are the details:

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 "fox, hare, and lettuce" 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 is to exit Prolog, reenter it, and start again.

Part 5: Grammars in Prolog (30 Points)

In Assignment 8 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 (and copy) the files g0.pl,g1.pl, g2.pl, g3.pl, and g4.pl supplied for you in /cs/cs60/assignments/assignment9/part4/. Each of these files specifies a different grammar. A grammar is specified by declaring the variables, terminals, and rules.

For example, consider the grammar for valid additions of 0's and 1's. (This is the grammar specified in the file g0.pl.)

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

We also specify which symbols are terminals as shown below.

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

Finally, the grammar rules are stated as ordered pairs, where the first element is the left-hand-side of a rule and the second argument is the LIST of elements appearing on the right-hand-side of that rule. For the grammar above, these rules are stated as shown below.

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 plan to call parse with the sentential form comprising just the start variable and the list of symbols being just the list of symbols to parse. For example, here is some sample input and output:

| ?- [part5].                       <--- HERE WE ARE LOADING IN OUR PROGRAM
yes 

| ?- [g0].                          <--- HERE WE ARE LOADING IN A GRAMMAR
yes

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

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

We've seen several puzzles and the solutions for these puzzles written in Prolog. For up to 15 bonus points (depending on the complexity), write a Prolog program to solve your favorite puzzle. Here are the requirements:

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!

In addition to submitting your bonus, please send e-mail to Ran and Zach letting them know that you have submitted the bonus problem (so that they can play with it themselves!).

Last modified March 2004 by Ran Libeskind-Hadas

Computer Science 60 Principles of Computer Science Spring 2004

Assignment 9: Fun (and Games) with Prolog! Due Monday, March 29 before midnight.