CS 60, Assignment 7

Computer Science 60
Principles of Computer Science
Spring 2006

Assignment 7: More rex, Infinite Lists, and Prolog warmup! [100 Points]
Due Thursday, March 9 by 11:59 PM

Please note the special time and due date for this assignment. No CS 60 dollars may be used on this assignment.

(Note: There will be no assignment given out over Spring Break. When you return from Spring Break on Monday, March 20, the next assignment (Assignment 8) will be posted and it will be due on Monday, March 27).

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: Preventing SpamWars [30 points]

Put all of your code for this part in a file called part1.rex There is already some code in this file at: /cs/cs60/assignment7/part1.rex.

The mayors of a number of neighboring cities have been noticing some conflicts brewing between their cities over the rumor of an upcoming Spam shortage. Cities with small Spam reserves have been making plans to raid the stores of those with larger reserves, should it come to that.

The mayors, wishing to avoid all conflicts over canned meat products, have decided that if two cities are about to go to war, the mayors will cut off all access from one city to another by destroying all roads that would allow travel between the two towns (perhaps by way of other towns). They want to do the minimal damage to their infrastructure, so they have contacted Napquest, the company from the bonus problem in Assignment 6, to help them determine the minimum number of roads that must be destroyed in order to fully separate the two cities. Napquest has hired you to help with this problem.

In this problem, a map is a list of two things: a list of cities and a list of roads. The list of cities is a simple list of city names (they might be numbers or strings). The list of roads is a list of pairs, where each pair is a list of the form [City1, City2]. City1 and City2 are just names of cities that must appear in the city list (again, they might be numbers or strings). The roads are undirected, that is, a road from City1 to City2 will also allow travel from City2 to City1. Order does not matter. (Note that we include a full list of cities in our map representation, rather than including just the edges, because we want to be able to represent a city in the map even if there are no roads connected to it.)

Your job is write a program called minRoadCut which takes as input three things: The names of two cities on the brink of war and an entire map. The function returns the value of the smallest number of roads that must be destroyed to successfully separate the two cities. Remember that roads are undirected and that it is not sufficient simply to cut the road between City1 and City2 (if one exists in the first place) because there might be another way to get there going through City3, for example.

The solution to this problem is not long, but this problem will take significant planning, so make sure you sit down and map out an algorithm before you start coding! This planning is extremely important to avoid confusion and frustration. Weirdo analysis is a good way to approach this problem, but you will need to deal with a number of subproblems (e.g., determining when you are done).

As one subpiece we recommend writing a modified version of reachable that works on our new graph (i.e. map) structure. reachable should take as input two cities and a map and return true if there is a way to get from City1 to City2 on the map, and false otherwise.

To help you with this task, we have provided a "reachableDir" function that works for directed graphs (that may contain cycles) using the representation from Part 1 of Assignment 6 (i.e. a graph is a list of pairs representing edges in the graph). reachableDir takes two cities and a directed graph and returns true if there is a way to get from City1 to City2. Essentially reachableDir is the solution to "reachable" from Assignment 6, but our version can definitely handle cycles in the graph (yours was not required to). Note that this function almost solves our problem and could be very useful if only our roads were directed rather than undirected....

The program need not be fast, but it must compute the right answer. For full credit, keep your code very short.

Finally, remember to test your code carefully on a number of sample graphs (maps) that you create.

Part 2: Infinite Lists [30 Points]

This part of the assignment should be submitted in a file called part2.rex.

In class we wrote a function called from(N) which takes a number N as input and generates the infinite list of integers greater than or equal to N. The function was written as:

  from(N) => [N |$ from(N+1)];

Another useful function is get(N,L) which takes a non-negative integer N and an arbitrary infinite list L as input and returns the Nth element in the list (where the first element is assumed to have index 0). This function can be written as:

  get(N, [F | R]) => N == 0 ? F : get(N-1, R);

Notice that this function definition assumes that N is not larger than the length of the list. (This is OK here because the lists we'll be dealing with are, well, um, infinitely long!) Finally, one last function which you'll use is find_index(X,L). This function takes an element X and an arbitrary list L and returns the index of the first occurrence of X in list L. This function can be written as:

  find_index(X, [Y | L]) => X == Y ? 0 : 1 + find_index(X, L);

Notice that this implementation also implicitly assumes that the list is infinitely long. (Otherwise, we would need a base case!)

Now you could use these functions as follows:

rex > get(2, from(10));
12

rex > find_index(5, from(4));
1

You're welcome to use these functions in your code if you like.

First, the totally gratuitous story. Professor I. Lai of the Pasadena Institute of Technology (P.I.T.) wants to write a function that takes as input two infinite lists L1 and L2 and returns an infinite list that contains all of the elements in L1 and all of the elements in L2, where the order of the elements in this new list is not important. Professor Lai's implementation works like this:
```
      lai(L1, L2) => [F1 | R1] = L1, [F1 |$ lai(R1, L2)];
    
```
You can try this function out in rex. For example, try lai(from(100), from(0)). What you'll discover is that the numbers from the second infinite list [0, 1, 2, ...] never ever get put on this list. That is, no matter how long you wait, you will never see 0, for example, in this infinite list. So, if you try to run
```
      find_index(0, lai(from(100), from(0)));
    
```
you'll end up running forever! Professor Z. Ip of the Massachusetts Institutue of Typing has proposed another approach to merging infinite lists L1 and L2 which he calls "zipping". Zipping takes the first element of L1, then the first element of L2 then it goes back and takes the next element from L1 followed by the next element of L2, etc. For example, here's what would happen if we zipped from(100) with from(0):
```
      rex > zip(from(100), from(0));
      [100, 0, 101, 1, 102, 2, 103, 3, 104, 4, 105, 5, 106, 6, 107, 7,
    108, 
      8, 109, 9, 110, 10, 111, 11, 112, 

      more? (return to continue, q to quit, a to abort, g to go
      non-stop, b to break) 
    
```
Your first task (and it's very short) is to implement the zip function. Use delayed evaluation, of course! Specifically, your delayed evaluation implementation of zip should put some finite number of elements on the output list (it can be more than one) and then should delay the evaluation of the rest of the list.
Your next task is a bit more challenging. Now you are going to implement a pairs function for infinite lists. That is, given two infinite lists L1 and L2, pairs(L1, L2) returns an infinite list of all pairs (a pair is list with two elements) in which the first element comes from L1 and the second one comes from L2. Professor Lai's implementation, called lai_pairs has the following behavior:
```
    rex > lai_pairs(from(0), from(0));
    [ [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], 
    [0, 6], [0, 7], [0, 8], [0, 9], [0, 10], [0, 11], 
    [0, 12], [0, 13], [0, 14], [0, 15], [0, 16], 
    [0, 17], [0, 18], [0, 19], [0, 20], [0, 21], 
    [0, 22], [0, 23], [0, 24],

    more? (return to continue, q to quit, a to abort, g to go
    non-stop, b to break) 
```
Professor Di Agnol observes that this is very bad. The pair [1, 0], for example, will never ever appear on this list, no matter how long we wait! Her idea is to write a function called pairs(L1, L2) which will build all pairs from L1 and L2 in such a way that eventually any pair that you're looking for will appear on this list. Her clever insight is that the output could look like this:
```
    rex > pairs(from(0), from(0));
    [[0, 0], [0, 1], [1, 0], [0, 2], [1, 1], [2, 0], 
    [0, 3], [1, 2], [2, 1], [3, 0], 
    [0, 4], [1, 3], [2, 2], [3, 1], [4, 0], 
    [0, 5], [1, 4], [2, 3], [3, 2], [4, 1], [5, 0], 
    [0, 6], [1, 5], [2, 4], [3, 3], 

    more? (return to continue, q to quit, a to abort, g to go
    non-stop, b to break) 
    
```
Take a close look at the pattern of the output. Notice that the first pair contains the 0th element of the first list and the 0th element of the second list. The next two pairs are those in which sums of the indices are exactly 1 (that is, the pair comprising the 0th element in the first list and the 1st element of the second list and then the pair comprising the 1st element of the first list and the 0th element of the second list). The next few pairs are those in which the sums of the indices are exactly 2, etc. In this way, if we are waiting for any given element to show up on the list, it will appear eventually. Your task is to write this pairs function using delayed evaluation. You may need to write several helper functions to do this. Again, your function should output some finite number of pairs and should then delay the evaluation of the rest of the list.

Part 3: Playing with Prolog! (15 Points)

In the directory /cs/cs60/assignments/assignment7 you will find a file called part3.pl. This file contains an expanded database of the Simpsons family. You should make a copy of this file and add the following rules to this file. You may also add any additional helper rules that you wish, including anything that we looked at in class. However, please don't change the facts about parenthood/relationships among the Simpsons!

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

Recall that "," is the symbol for AND, ";" is the SYMBOL for OR, and "\+" is the symbol for NOT. Please look at the class notes for other Prolog syntax. Your file should be called part3.pl and submit it using cs60submit.

Part 4: Lists in Prolog (25 Points)

Here, you will write three Prolog rules for lists. Please submit these rules in one file called part4.pl using cs60submit. 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 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 part4.pl.

Last modified March 2006 by Christine Alvarado