Assignment 4: Prolog - true! [100 points]
Due Monday, February 24th by 11:59pm

Submitting...    For this assignment, you'll submit the two files: lists.pl and logicpuzzle.pl. Also, there are four Java problems to complete and indicate in the usual way.

The extra-credit problem, if you'd like to try it, would be submitted in a file named twentyfour.pl.

Example code and starter versions of the files are available here:

• ex.pl   Examples from class...
• lists.pl   Starter file for #1
• logicpuzzle.pl   Starter file for #2
• einstein.pl   Example logic puzzle from class...
• twentyfour.pl   Starter file for the extra-credit problem

Formatting and commenting and testing...

Please use the standard commenting convention of your login, file name, and date at the top of each file. In addition, be sure to include a comment for each predicate that you implement.

For each of the prolog functions that you write in list.pl, you should write at least one additional test case. We encourage you to write these test cases BEFORE you write your code, especially as a way to deepen your understanding of the behavior of the rule.

Problem 1: Lists in Prolog

[60 points, pair or individual]

Here, you will write a few Prolog predicates that express relationships about lists (and trees and graphs, expressed as lists). Please submit these rules in one file called lists.pl.

You may create and use any helper rules that you like. In particular, some of the rules that we saw in class may be helpful here! For example, we wrote the member predicate:

member( X, [X|_] ).
member( X, [_|R] ) :- member( X, R ).

range(L,H,[]) :- L >= H.
range(L,H,[L|R]) :- L < H, M is L+1, range(M,H,R).

Prolog predicates to write in lists.pl :

• [Part 1]   rev(X,Y)
  
  rev(X, Y) should be 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, rev([1, 2, 3], R). Make sure this works. However, your rules do not have to work in the case that the first argument is a variable and the second argument is simply data, i.e., literal data.
  
  

  Hints Remember the "most common" order for Prolog clauses: (1) base cases, (2) recursion, (3) other constraints (esp. negatives). This applies here! Specifically, here are the left-hand-sides of the two rules you'll need, to get you started: rev( [], [] ). % this base-case rule is complete. rev( [F|R], Rev ) :- % recurse and then add another constraint! Finally, the built-in append predicate will be useful!




• [Part 2]    count(X,L,N)
  
  count(X, L, N) should be true if and only if item X occurs in list L exactly N times. For full credit, your predicate should work when X and/or N are variables (or both). It does not need to work when L is a variable.
  
  Here are two examples:

      count(spam, [oh, spam, spam, we, love, spam], N).  % user query
      N = 3 ;    % prolog reply
      No         % no more possibilities
  

  and a case where both X and N are variable:

      count(X, [oh, spam, spam, we, love, spam], N).  % user query
      X = oh,
      N = 1 ;    % any more?
      X = spam,
      N = 3 ;    % any more?
      X = we,
      N = 1 ;    % any more?
      X = love,
      N = 1 ;    % any more?
      no         % no more possibilities
  

  It's OK to get one more result in the latter case, above, with

      N = 0      
  

  and either no X at all or an unnamed variable X. Whether or not you get this final possibility depends on where (if at all) your code forces things to be bound to a value. Any of these is ok.

  Hints When writing the count predicate, be careful that it "counts" exactly the correct number of occurences. One pitfall is to write a version of this function that returns all values of X less than or equal to the correct count. Also, remember the most common order for clauses: (1) bases cases, (2) recurse, (3) other constraints (negatives as late as possible). The count predicate requires no more than three rules. Try re-designing things if your code is going beyond that! Here is a guide to the three rules you'll want: a base case for when the count is zero a case where X is NOT the first element of L a case where X is the first element of L.

  
  
  
• [Part 3]    find(P,T,I)
  
  

  One-dimensional pattern matching is an important task in many applications such as cryptography and DNA sequencing. For this problem we encode a 1d pattern as a list of items (named Pattern) and we'll search for that pattern within another list called the Target.

  Thus, for this problem write the rule find(Pattern, Target, Index) which takes two lists Pattern and Target and a non-negative integer Index as input. This find rule should be true if and only if Pattern occurs inside list Target beginning at position Index. The find predicate should not be true in the case that Pattern is the empty list -- so your base case will need to be bigger than the empty list!

  For example, here is a Prolog query and response:

      find([1, 2], [1, 2, 1, 2, 1], 0).   % user query
      Yes     % this might be true instead of Yes
  

  Here are two more examples:

      setof( N, find( [1,2], [1,2,1,2,1], N ), Answer ).
      Answer = [0, 2]
  

  and

      find([], [1, 2, 1, 2, 1], N).
      No.
  

  Remember that find should not succeed for the empty Pattern.

  For full credit, your find predicate should work when either or both of Pattern and Index are Variables. We will only test your code when Target is bound to a value (it's a non-variiable).

      find( Pattern, [a,c,a,c], N ).
      Pattern = [a],
      N = 0 ;
      Pattern = [a, c],
      N = 0 ;
      Pattern = [a, c, a],
      N = 0 ;
      Pattern = [a, c, a, c],
      N = 0 ;
      Pattern = [c],
      N = 1 ;
      Pattern = [c, a],
      N = 1 ;
      Pattern = [c, a, c],
      N = 1 ;
      Pattern = [a],
      N = 2 ;
      Pattern = [a, c],
      N = 2 ;
      Pattern = [c],
      N = 3 ;
      No
  

  You can coax setof to give you all of these at once, if you'd like:

      setof( [N,P], find( P, [a,c,a,c], N ), Answer ).
      Answer = [[0, [a]], [0, [a, c]], [0, [a, c, a]], [0, [a, c, a, c]], 
                [1, [c]], [1, [c, a]], [1, [c, a, c]], [2, [a]], 
                [2, [a, c]], [3, [c]]]
  

  Hints The find predicate requires only three rules. Here is a rough guide: a base case when the Pattern is a list of a single element and when that same element is the first element of a potentially longer Target list. In this case, Index should be 0. a recursive case when the Pattern has a first and a rest (and so does the Target), but when the Index is still 0. a recursive case when the Pattern is any list, the Target has a first and a rest, and the Index is a variable (and will end up being something greater than 0).

  
  
  
• [Part 4]    depth(E,Tree,N)
  
  depth(E, Tree, N) should be true if and only if E is an element of the binary search tree Tree at a depth of N. The root of the tree is defined to be at depth 0. The children of the root are all at depth 1, their children at depth 2, and so on.

  For full credit, your depth predicate should work in the case that either or both E and/or N are variables or bound values. You should assume that Tree is, in fact, a binary search tree -- your code should not try to check this. You'll be able to use the tree below by including in your code the tree1 predicate, as follows:

  tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
               [ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).
  

  Then you can use this to bind a variable to the above data before testing. The examples below illustrate this.

  Here are some example queries and their resulting Prolog interactions:

  tree1( T1 ), depth( 42, T1, N ).    % user query
  
  T1 = [42, [20, [10, [5, [], []], ... % prints the tree
  N = 0 ;      % user asks for more with the semicolon
  
  No           % no more depths for 42
  
  
  
  tree1( T1 ), setof( E, depth( E, T1, 3 ), Answer ).  % user query
  
  T1 = [42, [20, [10, [5, [], []], ... 
  Answer = [5, 18, 50, 2009]
  

  Warning    It's better not to use the "cons bar" (the vertical bar) anywhere in this depth predicate or the insert predicate below. Remember that the general form of a binary serach tree is three elements:

  [ Root, Left, Right ]
  

  which requires only commas, no "cons"es.

  Hints The depth predicate requires only three rules: a base case and two recursive cases. Remember that if you get "singleton" warnings, you may be using a variable only one time in a prolog statement. You can replace that variable with the "don't care" symbol, an underscore: _.




• [Part 5]    insert(E, Tree, NewTree)
  
  insert(E, Tree, NewTree) should be true if and only if NewTree is a binary search tree identical to Tree, except that the element E is now present in NewTree in an appropriate place. It is OK if E is already in Tree -- in that case, NewTree and Tree will be identical.

  For this predicate, the only input that needs to be handled as a variable (or value) is the last one, NewTree. You should assume that both E and Tree are already bound.

  Warning!!    When you insert nodes into a binary tree, they are ALWAYS inserted at a leaf! This is true whether it's Racket or it's Prolog... . Thus, your Prolog predicates will delegate the insertion until they "find" (through recursion) the correct leaf into which to insert the new element. Remember that you need to bind the result to the whole output tree, not only the subtree at which the insertion is happening.

  Again, use the tree1 predicate:

  tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
               [ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).
  

  Then you can use this to bind a variable to the above data before testing.

  Here are two example queries and their resulting Prolog interactions. The spacing has been adjusted to make it clear what's happening, but Prolog will simply print the full tree out. (See the note at the top of this assignment about telling Prolog to always print all of its data.)

  tree1( T1 ), insert( 43, T1, NewTree ).
  
  T1 =      [42, [20, [10, [5, [], []], [18, [], []]], []], 
                 [100, [67, [50, [], []], []], 
                       [150, [], [2009, [], []]]]],
  NewTree = [42, [20, [10, [5, [], []], [18, [], []]], []], 
                 [100, [67, [50, [43, [], []], []], []], 
                       [150, [], [2009, [], []]]]] 
  
  
  
  
  
  tree1( T1 ), insert( 41, T1, NewTree ).
  
  T1 =      [42, [20, [10, [5, [], []], [18, [], []]], []], 
                 [100, [67, [50, [], []], []], [150, [], [2009, [], []]]]],
  NewTree = [42, [20, [10, [5, [], []], [18, [], []]], [41, [], []]], 
                 [100, [67, [50, [], []], []], [150, [], [2009, [], []]]]]
  

Hints The insert predicate requires no more than four rules: two base cases (if E is there or not there) and two recursive cases. You might re-design things if your code is extending beyond that... .




• [Part 6]    path(A, B, Graph, Path)
  
  path(A, B, Graph, Path) should be true if A and B are both nodes in the graph Graph and if Path is a list of nodes that constitutes a path from A to B using edges from Graph. You should also assume that every node A is reachable from A itself using the single-node path [A] - this is a good base case!

  For full credit, your path predicate should work when A, B, and/or Path are variables. However, you may assume that Graph is a fully-instantiated list of edges -- not a variable.

  Here is an example graph1 predicate:

  graph1(  [ [a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z] ] ).
  

  You can use this to bind a variable to the above data before testing.

  Hint: Take a look at the Racket reach? algorithm from class and hw#3 - this is exactly the same algorithm (though it is very different syntax, to be sure!)
  
  Also, you will want to use this kind of pattern-matching for the graph in the use-it case: [[X,Y]|R]: this provides both endpoints of one edge - you'll need to use both!

  Here are two example queries and their resulting Prolog interactions.

  % small example ~ just finding P
  graph1(G1), path( a, z, G1, P ).  % user query
  
  G1 = [[a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z]],
  P = [a,b,w,x,z] ;
  % our implementation had lots of identical answers...
  

  Here is a means to get all distinct answers:

  ?- graph1(G1), setof( P, path( a, z, G1, P ), Answer).
  G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],  % first prints G1
  Answer = [[a,b,w,x,z],[a,b,z]]                     % prints all 2 answers
  

  It would certainly be possible to find the minimum path by taking the shortest-length element of Answer, above. Edge weights could be added, as well. You don't need to do any of this for the problem at hand, but it's worth mentioning that Prolog can certainly find minimum paths, just as Racket can.

  % HUGE example ~ A, B, and P are all unbound
  graph1(G1), path( A, B, G1, P ).  % user query
  
  G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
  A = B,
  P = [B] ;
  
  G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
  A = a,
  B = b,
  P = [a,b] ;
  
  G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
  A = a,
  B = c,
  P = [a,b,c] ;
  %% and far too many more to iterate through by hand...
  
  
  
  %% for full credit, your code should handle graphs with
  %% cycles in addition to acyclic graphs, e.g,
  graph1( G1 ), G2 = [ [z,a] | G1 ], setof( Path, path( a, z, G2, Path ),
  Answer ), member( [a,b,z], Answer ).
  

  The above test should return true (perhaps with some bindings...)

  It's possible to ensure that each edge is used only once, but not necessary for this problem. However, your code should finish -- that is, it shouldn't head infinitely around a cycle in the graph.

  Hints The path predicate requires no more than three rules (though it's OK to use slightly more). It can be done very naturally in only two! We'd recommend the use-it-or-lose-it approach that was introduced with Racket -- here, however, it will be much more concise! Again, check out Racket's reach? example from class and hw#3.




• [Extra credit - part 7]    delete(E,Tree,NewTree)
  
  For up to +5 points of (optional) extra-credit on this assignment, implement the delete predicate for binary search trees. You implemented this in homework #2 in Racket -- here, the algorithm is the same, only expressed in Prolog:
  • If E isn't in Tree, then NewTree is identical to Tree
  • If E isn't at the root of Tree, then delete from the appropriaet subtree -- but return the full structure (with only the one node deleted).
  • If E is at the root of Tree, then you'll need to handle three cases:
    • if both children trees are empty, the result is a fully empty tree
    • if only one child is nonempty, the result is that child
    • if both children are nonempty, the result promotes the minimum element of the right-hand subtree to be the new root and removes it from the right-hand subtreee. You'll need to include a helper predicte to do this!
  
  Include five test cases (with your own tree or one of ours) that show that these different possibilities for the problem are working.

Problem 2: Einstein's logic-constraint puzzle (30 Points)

Note on spelling: Be careful with the various names in this problem -- you'll want to keep the spelling consistent. In particular, be sure collette is with two l's and two t's. (We've tried to be consistent ourselves; if you see any problems, let us know!)

For this problem, your task is to write a set of prolog rules that will solve the following logic puzzle (in the spirit of Einstein's Zebra Puzzle):

/*
 * algird, bruno, collette, dino, and edwina are each from different
 * one of five colleges: pomona, pitzer, hmc, cmc, and scripps.
 *
 * Each one brings a different snack:  jots, chocolate, donuts, pez, and spam.
 * They are all on the train together in seats 1 through 5.
 *
 * We want to know which student is in each seat, what college does each
 * student attend, what did each student bring for a snack?
 * Determine whether there is a solution, and if so, whether it is unique.
 *
 * 1.  bruno and dino sat in the end seats.
 * 2.  algird sat next to the student from hmc.
 * 3.  collette sat next to friends with chocolate and donuts.
 * 4.  The hmc student brought spam as a snack and sat in the middle seat.
 * 5.  chocolate was immediately to the left of pez.
 * 6.  bruno, dino, and algird do not go to Scripps.
 * 7.  The pomona student sat between the persons with jots and spam.
 * 8.  dino did not sit next to the person with donuts.
 * 9.  The cmc student did not sit next to edwina.
 *
 * Note that negation constraints don't generate values -- they can
 * only check for consistency of already-instantiated values. Thus,
 * they must be tested _after_ variables are instantiated with values.
 *
 * Here is the solution (which is helpful to have for debugging!)
 *
 * Seats =
   [[bruno,cmc,jots],          % Seat 1
    [algird,pomona,donuts],    % Seat 2
    [collette,hmc,spam],       % Seat 3
    [edwina,scripps,chocolate],% Seat 4
    [dino,pitzer,pez]]         % Seat 5
 *
 */

Be sure to format your output in an easy-to-read manner.

In particular, you need to have a solve predicate that generates and prints the solution to the five-colleges logic puzzle neatly -- modeled from the solve predicate in the einstein.pl example.

That solve predicate first generates the solution to the puzzle, and then it prints the results in a reasonable fashion:

solve :-
  einstein( [ H1, H2, H3, H4, H5 ] ),
  write( ' first house: '), write(H1), nl,
  write( 'second house: '), write(H2), nl,
  write( ' third house: '), write(H3), nl,
  write( 'fourth house: '), write(H4), nl,
  write( ' fifth house: '), write(H5), nl.

This zero-argument predicate solve is called without parentheses at all, and it produces results as follows:

?- solve.

 first house: [norwegian, cat, dunhill, water, yellow]
second house: [dane, horse, marlboro, tea, blue]
 third house: [brit, bird, pallmall, milk, red]
fourth house: [german, zebra, rothmans, coffee, green]
 fifth house: [swede, dog, winfield, beer, white]

Yes

Hints:    the "end seats" constraint is a good opportunity to use the or operator (the semicolon, ;). Specifically, you'll likely want something similar to this:

( Seats = [something] ; Seats = [somethingelse] ), ... other clauses ..., 

Submitting...    Be sure to submit the two files: lists.pl and logicpuzzle.pl to the usual place on the submission site

Problem 3:    Java! (10 points)

We have five additional Java problems this week, worth a total of 10 points. This week, the problems don't have solutions... We encourage you to pair up with someone to work on these, again emphasizing Java loops, lists (arrays), and strings:

• Java for loops and while loops
• Java arrays and loops

• doubleChar
• countCode
• bobThere
• repeatEnd
• sameStarChar

I've been stringing Java along...

Submission!

Be sure to submit your sentence in the usual way, under hw4pr3.txt; see below if you're in the mood for EXTRA Prolog, as well... .

[Extra]    The Game of 24! (up to +11 points)

This totally optional 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 - such that the solution combines the numbers in the list [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, integer division 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. Note that eval can handle numbers and it can handle trees that are bound to some value (using the nonvar predicate) Thus, the eval predicate can not generate trees. Allowing eval to generate trees can lead to infinite recursion, as it looks in the (unbounded) space of trees for operations possibly leading to R.

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

Here are some other examples of solve in action. Warning: You may especially want to check the second of these. In particular, a common partially working solution to this problem handles the first example below, but not the second example. Note how the list of values is being split into sublists in the second case. Be careful to only allow non-empty splits; otherwise, you'll end up with an infinite recursion!

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

  Tree = [*,1,[*,2,[*,3,4]]]    % other solutions are certainly possible!



  solve(['+','-','*','/'], [2,8,22,424], 42, Tree).  % only one solution possible!

  Tree = [-,[/,424,8],[/,22,2]]



  solve(['+'], [1, 1, 1, 1], 24, Tree).   % no solution

  No.



  solve(['+'], [24], 24, Tree).    % base case

  Tree = 24
 

For +5 points, your solve predicate should work as above, generating trees (with a value provided for Result). For the final +6 points, your predicate should also be able to generate the Result value (as well as the tree):

?- solve(['+', '*', '-'], [1, 10,100, 1000], N, Tree).

N = 1111,
Tree = [+,1,[+,10,[+,100,1000]]] ;

N = 1110,
Tree = [*,1,[+,10,[+,100,1000]]] ;

N = -1109,
Tree = [-,1,[+,10,[+,100,1000]]] ;

N = 11001,
Tree = [+,1,[*,10,[+,100,1000]]]   % and many, many more...

Please submit this extra-credit part of the assignment in a file called twentyfour.pl.