CS60 Assignment 9

Harvey Mudd College
Computer Science 60
Assignment 9, Due Friday, April 12, by midnight

Prolog Puzzles

This assignment introduces some of the more impressive capabilities of prolog (and asks you to convince prolog to exhibit them). Problems 1-4 and the extra credit are prolog "programs" (really predicates). They should be submitted all together in a file named puzzles.pl . There is a (small) file named /cs/cs60/as/a9/puzzles.pl with a few predicates to start you out.

The second part (Problem 5) can be typed and submitted as an ascii file named proof.txt or handwritten and submitted under the door of Olin 1265 by midnight on Sunday night (4/14).

Problem 1 (5 points): remove

Write a prolog clause (or a number of clauses) that implement remove, where remove(E, LBefore, LAfter) indicates that LAfter is the same as list LBefore, except that the first occurrence (if there is one) of element E is removed from LAfter. If E is not in LBefore, then LAfter is identical to LBefore.

For example, possible runs of remove might include

?- remove(1, [2, 1, 3, 1], [2, 3, 1]).

yes


?- remove(X, [2, 1, 3, 1], [2, 1, 1]).

X = 3 ;
no


?- remove(1, [1, 2, 3, 1, 2], X).

X = [2,3,1,2] ;
no


?- remove(1, X, [2, 3, 4]).

X = [1,2,3,4] ;
X = [2,1,3,4] ;
X = [2,3,1,4] ;
X = [2,3,4] ;
X = [2,3,4,1] ;
no

You may want to use the member predicate we discussed in class and provided in /cs/cs60/as/a9/puzzles.pl as an example. Note that depending on your exact implementation of remove, the order in which the answers appear (in the examples above) may be different. This is certainly OK.

Problem 2 (5 points): find

Pattern matching is an important task in many applications such as cryptography and DNA sequencing. This problem asks you to find a sublist wherever it might appear within a larger list. Write the predicate find(Pattern, Target, Index) that takes two lists Pattern and Target and a non-negative integer Index as input. This predicate is true if and only if Pattern occurs inside list Target beginning at position Index. Note that there may be more than one Index at which the pattern is located.

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

Write the rules for the predicate find. You may want to write some helper predicates to make find easier. Here are a couple of other example runs from find:

      | ?- find( P, [1,2,3,4], 1 ).

      P = [] ;
      P = [2] ;
      P = [2,3] ;
      P = [2,3,4] ;
      no


      | ?- find( P, [a,b], X ).

      P = [],
      X = 0 ;
      
      P = [a],
      X = 0 ;
      
      P = [a,b],
      X = 0 ;
      
      P = [],
      X = 1 ;
      
      P = [b],
      X = 1 ;
      
      P = [],
      X = 2 ;
      
      no

find will not be able to answer queries like

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

because prolog has no idea what to put after the 1 and 2 into the list L. (It will give some internal variable name and then, perhaps, head off into an infinite loop looking for more things to include.)

Problem 3 (10 points): a real puzzle!

In this problem you will be solving (or writing prolog predicates to solve) the generalized Missionaries and Cannibals problem. You may want to use the example puzzles -- particularly the towers of Hanoi problem -- done in class as a guide.

In this problem, there are some number of missionaries and cannibals on the banks of a river and only one boat available. The goal is to achieve some desired configuration of missionaries and cannibals on the two sides of the river, but you are subject to two constraints. First, the number of cannibals can never be greater than the number of missionaries on either side of the river. If, however, there are no missionaries at all on one riverbank, then there may be any number of cannibals there. The second constraint is that there is only one boat available. Thus, it has to go back and forth across the river. The boat must have at least one person to navigate it (either a missionary or a cannibal) and can fit at most two people (any combination of missionaries and cannibals).

The problem is to write a prolog predicate solveMC that will enable queries to solve arbitrary missionaries and cannibals problems. Write solveMC with the following arguments:

solveMC( MoveList, StateList, StartState, EndState ) :- ...

the first argument MoveList is the list of legal moves that will get the missionaries and cannibals from their initial configuration (StartState) to their final configuration (EndState). The second argument StateList is a list of all of the configurations that have been seen "so far." The states in this list must be avoided (to avoid loops).

The StartState and EndState are lists of exactly five elements:

  [ #M's-left,  #C's-left,  #M's-right,  #C's-right , boatLocation ]

which you may want to pattern-match as

  [ ML, CL, MR, CR, left ]    or    [ ML, CL, MR, CR, right ]

In fact, since you have both "before" and "after" lists, you might want to pattern match with something like

  [ MLb, CLb, MRb, CRb, left ]      and     [ MLa, CLa, MRa, CRa, right ]

to indicate Missionaries vs. Cannibals, Left vs. Right, and before vs. after. The position of the boat will change depending on what particular move is being made (see the list of 10 possible moves below.) Because of this representation, the StartState at the very beginning of the 3-missionaries, 3-cannibals puzzle is

  [ 3, 3, 0, 0, left ]

the corresponding EndState is

  [ 0, 0, 3, 3, right ] .

Other tips

You will want to use the member predicate (gone over in class and in /cs/cs60/as/a10/puzzles.pl). You will also want to write your own "helper" predicates -- for example, a predicate named valid that checks that each river bank (left and right) is valid under the problem's constraints. Another helpful predicate might be move that describes each of the legal moves. There are 10 legal moves, listed below.

Please use these names (to make checking your work easier):

mToL      - one missionary from right to left
cToL      - one cannibal from right to left
mmToL     - two missionaries from right to left
ccToL     - two cannibals from right to left
cmToL     - one missionary and one cannibal from right to left

mToR      - one missionary from left to right
cToR      - one cannibal from left to right
mmToR     - two missionaries from left to right
ccToR     - two cannibals from left to right
cmToR     - one missionary and one cannibal from left to right

Example runs

Here are some example runs of the solveMC predicate -- keep in mind that, depending on the order of things in your implementation, your solutions may come in different order and they may be repeated several times. This is absolutely OK.

/* Here is the original 3-missionaries, 3-cannibals problem */



?- solveMC( MoveList, [], [ 3, 3, 0, 0, left ], [ 0, 0, 3, 3, right ] ).

MoveList = [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR]; 

<plus others, and you may have a different initial solution>






/* Just getting one missionary and one cannibal across */



?- solveMC( MoveList, [], [ 1, 1, 0, 0, left ], [ 0, 0, 1, 1, right ] ).

MoveList = [cmToR] ;
<plus repeats, though there are no other solutions>
<that do not repeat states.>








/* There is no way to get 4 missionaries and 4 cannibals across. */

?- solveMC( MoveList, [], [ 4, 4, 0, 0, left ], [ 0, 0, 4, 4, right ] ).

no

You can also use setof to get all distinct solutions.


/* I got twelve distinct solutions to the original */

a(S) :- setof(Moves, solveMC(Moves, [], [ 3, 3, 0, 0, left ], [ 0, 0, 3, 3, right ] ), S).  

?- a(S).

S =
[[ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
 [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR,cToL,cToR],
 [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR,cmToL,cmToR],
 [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR],
 [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR,cToL,cToR],
 [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR,ccToL,ccToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR,cToL,cToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR,cmToL,cmToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR,cToL,cToR],
 [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR,ccToL,ccToR]] ;

no

/* 
 * if you check for repeated states in different places, you may get 
 * additional or fewer solutions, so don't worry about the exact number,
 * though there should always be at least four:
 *
 *  [[ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
 *   [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR],
 *   [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
 *   [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR]] ;
 */

Note that all of these solutions explicitly disallow repeated states. Otherwise whenever there was one solution, there would be infinitely many, because a cannibal could cross the river any number of times after the initial solution was found.

Problem 4 (10 points): The game of 24!

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 solve24 such that

     solve24(Ops, Values, Result, Tree)

will solve for a syntax-tree named Tree using operators Ops on the set (the "cards") Values to give the final value Result. For example,


 | ?- solve24(['+', '*', '-'], [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. Remember -- use recursion and prolog's built-in search to do the work for you!

    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 solve24 in action:

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

  no.


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

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

and there are many more answers to this latter example.

Problem 5 (10 points): proving a program correct!

The solution to this problem should be typed into a plain text file and submitted as proof.txt. Alternatively, the solution can be written out and handed under the door of Olin 1265 by midnight Sunday night.

Given the following program, create appropriate loop invariants (statements that are true each time the program reaches the point labeled /* HERE */ in the code). You should have 4 invariants -- one for each of x, y, z, and i. The x, y, and z invariants should be equations for each in terms of i. The i invariant should be an inequality in terms of N.

Once you have your four loop invariants, prove them true by induction. Then, use the loop invariants to show that that the following function returns the cube of its argument, assuming that the input argument is non-negative. (Don't worry about proving that the function terminates for nonnegative inputs; we'll take that for granted. In general, however, proving that a program terminates is important and not always straightforward...)

Thus, you will need to prove two things: (1) that each loop invariant you've created holds true before every loop test and (2) that for the precondition N >= 0, the postcondition x = N*N*N holds (as long as N hasn't changed, which it won't).


/* assume the input, N, is nonegative */

static long cube(int N)
{
  int i, x, y, z;
  x = 0;
  y = 1;
  z = 6;

  for( i = 0; /* HERE */ i < N; i++ )
  {
    x = x + y;
    y = y + z;
    z = z + 6;
  }

  return x;
}

Testing

Be sure to test your prolog code with the above examples, as well as others that you create.

Reading

Prolog, Predicate logic, and proving programs correct are all covered in Chapter 10 of the book.

Submission

The puzzles.pl and proof.txt files with your prolog solutions and correctness proof should be submitted in the usual way, i.e., with

% cs60submit puzzles.pl
% cs60submit proof.txt

We will also look for a fours.pl problem, in case you tried the extra credit.

Extra Credit

For optional bonus credit (up to 20%), write a prolog predicate (you will need helper predicates to do this) that "solves" the four fours problem. You may want to base your solution on the "24" problem, above, though any approach is OK. This is a very open-ended extra credit -- all solutions are necessarily partial solutions. You should consider solving the problem from 0 to 100 an absolute success.

The four fours problem is the following challenge: for each nonnegative integer, write that integer as an arithmetic combination of exactly four fours. Some of the many possible examples for the first few (nonnegative) integers are these:

0 =  4 + 4 - 4 -4

1 =  44 / 44

2 =  (4/4) + (4/4)
  
3 =  4 - (4/4) - sqrt(4)
  
4 =  .4 * (4 + 4 + sqrt(4))

etcetera.

Martin Gardener (a long-time columnist for Scientific American) claimed that solving it for the integer 113 was impossible, though it's not proven one way or the other! If you do try it, submit your prolog code in a separate file named fours.pl. You should name the main predicate as follows:

  fours(N,Tree)

where N is the number which we would like to express as a combination of four fours, and Tree is a representation of the operations that are part of that combination.

The permitted operations are

concatenation (hence forty four is possible with 2 fours)
decimal point (.4 and 4.4 are allowed)
powers (4 to the 4th power uses two fours to create 256)
infinite repetition of a digit following a decimal point. This is usually denoted as a bar on top of the digit:
```
        _
       .4
       
```
This number is four ninths, so that you could write eight as
```
                  _ 
       8 =  sqrt(.4) * (4 + 4 + 4)
       
```
although there are more concise ways to write eight with 4's.
factorial (4!)
square root
ordinary use of parentheses
the four arithmetic operations (+ - * /), although division is not allowed unless it is exact (no rounding or truncating!)

As odd as it may seem, this problem has received a lot of attention in the formal (and not so formal) mathematical literature. Feel free to develop your own representations for sequences of operators and for the predicates you use. (Additional information on prolog is available from this site.)

Harvey Mudd College Computer Science 60 Assignment 9, Due Friday, April 12, by midnight