Assignment 4: Prolog - true! [100 points]
Due Monday, October 8 by 11:59 PM

Submitting...    For this assignment, you'll submit the two files: lists.pl and logicpuzzle.pl. As may have become second nature, this assignment has a few (now more intricate) Java problems too. The extra-credit problem, if you'd like to try it, would be submitted in a file named twentyfour.pl. Starter versions of all of these prolog files are within this zip file:

• hw4.zip, including lists.pl, logicpuzzle.pl, and twentyfour.pl

• lists.txt
• logicpuzzle.txt
• einstein.txt
• twentyfour.txt

Formatting and commenting...

Please use the standard commenting convention of your name, 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!

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 :

• removeOne(E, List, NewList) should be true if and only if E is an element of list List one or more times, and the list NewList should be identical to List except that the element E is removed once. Note that the element may appear more than once, and so it can be removed from different parts of the list List.

  Here are some example queries and their resulting Prolog interactions. Remember that some versions of Prolog use false and true instead of No and Yes. If your Prolog works like that, then you'll see the boolean names instead:

  removeOne( a, [a,b,c,a], R ).
  R = [b, c, a] ;
  R = [a, b, c] ;
  No
  
  
  removeOne( d, [a,b,c,a], R ).
  No
  
  
  removeOne( E, [a,b,c,a], R ).
  E = a,
  R = [b, c, a] ;
  E = b,
  R = [a, c, a] ;
  E = c,
  R = [a, b, a] ;
  E = a,
  R = [a, b, c] ;
  No
  
  
  % this summarizes the above more succinctly
  setof( [E,R], removeOne( E, [a,b,c,a], R ), Answer ).
  Answer = [[a,[a,b,c]],[a,[b,c,a]],[b,[a,c,a]],[c,[a,b,a]]]
  

  For full credit, your removeOne predicate must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You should assume that the middle argument is bound to a list value (i.e., the second input will not be a variable in our tests). Keep in mind the requirement that E be a member of List! That requirement is tested by the second example above.

  It's not required, but it's a good idea to use no more than two rules for the removeOne predicate!
  
  If you're writing more than two, take a step back and reconsider! In particular, remember that in Prolog, negation is expressed through the failure of a search for bindings. Thus, you don't want a base case involving the empty list as the second argument! If you don't have a rule with the empty list as the second argument, then the rules will simply fail when passed an empty list as a second argument (directly or through recursion) -- this is what you'll want!

  So, what rules should there be? For this one, you will want one base-case rule that handles the case when E and the first element of List are identical. Then, you'll want a recursive rule, using the rest of List. That's it!

  More hints:    If you're stuck on how to write removeOne, here are English descriptions of the two rules you'll want:

  1. Rule 1    This should be a base case that expresses the fact that when you remove an item from a list that has that item as its initial element, then the result is the rest of that list. (One rule: no need for the :- sign at all.)
  2. Rule 2    This should be a recursive rule that expresses the fact that when you remove an item from a list that has some initial element, then the result will have that same initial element, but a different "rest" And the "rest" of the result will be obtained by calling removeOne on the "rest" of the original list. (One rule with only one recursive clause after the :- sign.)




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

  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:

  1. a base case for when the count is zero
  2. a case where X is NOT the first element of L
  3. a case where X is the first element of L.




• 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]]]
  

  The find predicate requires only three rules. Here is a rough guide:

  1. 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.
  2. a recursive case when the Pattern has a first and a rest (and so does the Target), but when the Index is still 0.
  3. 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).
  
  
  
• 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]
  

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

  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.




• 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, [], []]]]]
  

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




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

  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!

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

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 introduces 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".
• With that background, write code for the following 10 functions, all of which appear in the Array-1 Java section of CodingBat.
• 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!
• Here are the 10 to write and share with dodds@cs.hmc.edu (so that we can grade them):
  • firstLast6
  • sameFirstLast
  • makePi
  • commonEnd
  • sum3
  • rotateLeft3
  • reverse3
  • maxEnd3
  • sum2
  • middleWay
• If you're frustrated by the lack of syntax highlighting in codingbat.com exercises, you might want to download a Java Integrated Development Environment (IDE). We recommend Dr. Java but any Java IDE will be fine.
• For-loops are a natural control construct for manipulating arrays. That will be next week's theme!

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.