Assignment 4: Prolog - true! [100 points]
Due Tuesday October 7th by 11:59 PM

Submitting...    For this assignment, you'll submit the three files: lists.pl, logicpuzzle.pl, and Hw4pr3.java. In the descriptions of the problems below we've included some hints. We encourage you to try each problem (at least for a few minutes) before reading the hints. However, it isn't a bad sign if you need to use the hints! The goal for this assignment is that you get comfortable with some of the patterns we use to solve problems in Prolog, not that you already know them before beginning the homework! The extra-credit problem, if you'd like to try it, would be submitted in a file named twentyfour.pl. Starter versions of the files are available here::

• ex.pl
• lists.pl
• logicpuzzle.pl
• einstein.pl
• twentyfour.pl
• Hw4pr3.java
• Hw4pr3Test.java

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.

Finally, please be sure to name your files and functions as noted by the problems.... The grading procedure for this assignment is partially automated and files and functions whose spellings differ from those below will help the graders a lot!

For each of the prolog functions that you write in list.pl, you are expected to write additional test cases. We encourage you to write these test cases BEFORE you write your code as a way to familiarize yourself with the behavior of the rule. Writing good test cases in some cases will require creating a new BST or Graph.

Note on Prolog's output formatting

There are several settings that control how Prolog formats its output: the following describes a few of those settings you may want to change.

You may have noticed that when answer variables get bound to long lists, swipl shows the list with '...' after about 10 elements, which can be annoying. To see the entire list, simply type

  w

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

?- range(1, 50, X).

X = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 

X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
     12, 13, 14, 15, 16, 17, 18, 19, 20, 
     21, 22, 23, 24, 25, 26, 27, 28, 29, 
     30, 31, 32, 33, 34, 35, 36, 37, 38, 
     39, 40, 41, 42, 43, 44, 45, 46, 47, 
     48, 49, 50]

To change the limit on the number of elements once and for all, copy the following at the top of your source file (we have done this for the source files this week).

:- set_prolog_flag(toplevel_print_options, [quoted(true), 
     portray(true), attributes(portray), max_depth(999), priority(699)]).

Part 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. This link has a starting point with placeholders. As before, you'll need to change the extension from .txt to .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 ).

The Prolog predicates to write in lists.pl (Problem 1) :

• [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. (Your rules do not have to work in the case that the first argument is a variable and the second argument is literal data.)
  
  

  Hints The append predicate may 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. 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 when Prolog inserts nodes into a binary tree, too! Thus, your Prolog predicates will delegate the insertion until they "find" (through recursion) the correct leaf into which to insert the new element.

  Again, use this 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.

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

Part 2: Einstein's logic-constraint puzzles (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

Part 3:    Java!    (10 points)

This week in Java adventures: Arrays!
[10 points; pair or individual]

• This week continues with Java Arrays, which might feel similar to Python's lists, but are much lower-level: you're dealing directly with a sequence of memory locations. As a result, Java Arrays are both much faster and much less flexible. The "less flexible" facets may be the most striking as you get used to them... !
• If you have not used arrays in Java or a C-like language before, or even if you have, you'll likely want to review how they work by reading the first few paragraphs on the CodingBat array page - up to (but not including) "Array Code Patterns".
• This time, there is no "show solution" button, but you are welcome to work with a partner on this (each should do the problems physically, but the effort can be fully shared). Partnering can help especially in dealing with the arbitrariness of new syntax!
• Since you won't have immediate access to the solution, we wanted to give you better support for testing your code. To do this, we provide a sample test-call to each of the methods inside the main method (You can run the code in the main method by running the file Hw4pr3.java.)

  
  		public static void main(String[] args){
     		   // duplicate of testFirstLast6_0
  		   int x[] = { 1, 2, 6 };
  		   System.out.println("returns: " + Hw4pr3.firstLast6(x));
  			// etc.
  		}
  	

• We also provide code within each of the methods to print out the input array and any other numbers you'd like to print out. For example, all of the methods start some print statements like shown below.

  
  		public static boolean firstLast6(int[] nums) {
  			System.out.println("****** firstLast6 ******"); 		// debug help
  			System.out.println("input: " + Arrays.toString(nums)); 		// debug help
  			System.out.println("Some number: " + 0);			// debug help
  			return true;
  		}
  	

• Some of the functions also include additional helper code, for example for creating a new array of length three:

  
    	public static int[] makePi() {
  		System.out.println("****** makePi ******"); 	
  		System.out.println("Some number: " + 0); 		
  		int[] retVal  = new int[3];						// creates new array of length 3
  		return retVal; // replace
  	}
    

Extra credit: 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.