Harvey Mudd College
Computer Science 42
Assignment 11, Due Tuesday, November 29, by 11:59pm

IMPORTANT: YOU MAY NOT WORK ON THIS
ASSIGNMENT IN THE MIDDLE OF THANKSGIVING BREAK.

SPECIFICALLY, DO NOT WORK ON THIS
BETWEEN 11:59pm WEDNESDAY, NOVEMBER 23
AND 12noon SUNDAY, NOVEMBER 27.

Fun (and Games) with Prolog!

Typically puzzles ask the user to satisfy a set of constraints -- and this is precisely what prolog was designed to do. In this assignment you will be using prolog to solve several different types of puzzles. The work involved is primarily in representing the puzzles and their rules. In order to help the graders, please check that you name your prolog rules (predicates) as they're specified in the assignment.

Feel free to use Prolog's built-in predicates in solving these puzzles. In particular, Prolog has a built-in length(L, N) which is true if and only if list L has length N. member( X, L ) is predefined in SWI Prolog. You may use your removeOne from the previous hw (or use this one):

removeOne(X,[X|R],R).
removeOne(X,[F|R],[F|S]) :- removeOne(X,R,S).
Also, Prolog also has a built-in append(A, B, C) which is true if and only if the result of appending list B to the end of list A results in list C. You may also want to define your own helper rules as needed.

Submission    Please submit your problems in separate files named

Here are the starter files for most of these parts:

Reminder: Printing all the elements of the resulting lists...

By default Prolog will use ellipses (...) to represent items in a list nested more than 10 deep. For example,

?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]
To change this behavior, you can do one of the following two things. First, use write: 
?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16], write(L).
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

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

Yes
Note that write shows the full value -- and then goes on to report the bound variables exactly as before. Alternatively, you can turn off the "max_depth" feature with the following: 
set_prolog_flag( toplevel_print_options, 
    [quoted(true), portray(true), attributes(portray), max_depth(0)] ).
leading to a change in how bound values are printed out: 
?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] .

Part 1: Einstein's logic-constraint puzzles (20 Points, individual) logicpuzzle.pl

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): 
/*
 * 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, snickers, 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 snickers and donuts.
 * 4.  The hmc student brought spam as a snack and sat in the middle seat.
 * 5.  snickers 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.
*/

Be sure to format your output in an easy-to-read manner. In addition, make sure that you leave a comment for the graders so that they know how to generate and print the solution to the puzzle. As an example, consider the solve predicate in the einstein.pl example (which you should probably read!). It first generates the solution to the Zebra puzzle, and then it prints the five houses 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 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

Please submit this part of the assignment in a file called logicpuzzle.pl.


Part 2: The Game of 24! (20 Points, individual) twentyfour.pl

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

     solve(Ops, Values, Result, Tree)
will solve for an arithmetic tree named Tree using operators Ops among the integers in Values to give the final value Result. For example, 
 | ?- solve(['+', '*', '-'], [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, the actual division operation using the // operator, e.g., "HalfN is N // 2".

Here is an eval predicate for evaluating trees of opreations. It will be helpful in solving this problem. You may copy this code and use it freely. However, it requires the first argument (the tree being evaluated) to already have a fixed value before eval is called. (That's what nonvar is checking.) Thus, you cannot simply say "eval(T, 24)." and generate suitable trees; there are infinitely many possible trees, and so this might easily lead to infinite recursion.

    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.
You may also use any of Prolog's built-in rules and any helper rules that you like (including those that we wrote in class).

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. Notice how the list of values is being split into sublists in the second case: 

  ?-  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
Notice that a plain integer is the simplest possible solution tree (not [24]), and there are many more answers to the first example above.

Warning!    Be careful for a situation that can lead to infinite recursion: if you split a list into two parts and one of those two parts is the same length as the original list, then a recursive call will not get closer to a base case (and is likely to continue forever!)

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

Part 3: Towers of Hanoi (20 Points, pair or individual) hanoi.pl

In this part of the assignment, you will write a Prolog program to solve the Towers of Hanoi puzzle. Please submit your solution in a file called part3.pl. You should carefully review the "alien, spampede, and spam" solution that we examined in class before embarking on this program. The big ideas in the two programs are very similar. Fortunately though, this Hanoi program is considerably shorter. (This program can be less than about 20 lines of Prolog code, not including comments and spacing between rules.) You might start from the "alien, spampede, and spam" code and altering it to create your hanoi-solving program.

Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer correct solutions to the puzzle. Here are the details:

Please submit this part of the assignment in a file called hanoi.pl.

Part 4: Generating Language (40 Points, pair or individual) parser.pl

You may submit either or both of these two problems for +10 and +10 points, respectively. The first one you should submit in a file named parser.pl.

Generating language (token lists)

In Assignment 4 you wrote a recursive-descent parser in Racket for Unilang; recall that recursive descent parsers have one handwritten function for each variable in the grammar. In this assignment you will write a general "parse engine" in Prolog which will allow you to parse a string, given a description of the grammar! Better yet, your parser will also allow you to generate language.  (Amazing, but true!)

To make life simpler, our goal is not to construct a parse tree, but we DO want to know if there EXISTS a parse tree for a given string using the given grammar. For example, IF we had a grammar for the English language, we would be able to ask our parser if a particular sentence was valid in English, and get a yes or no answer. The neat thing is that we won't hard-code the grammar into our parser; we'll just tell it what a grammar is and what string we're interested in and ask: "Hey Prolog, can this string be parsed by the given grammar?"

Take a look at the files g0.pl,g1.pl, g2.pl, g3.pl and g4.pl supplied to you from the top-level assignment page. Each of these files specifies a different grammar. A grammar is specified by declaring the variables, terminals, and rules.

For example, consider the grammar for valid additions of 0's and 1's. (This is the grammar specified in the file g0.pl.)

s -> v + s | v
v -> 0 | 1
Here, s and v are the variables and 0 and 1 are the terminals. Notice that no upper-case letters are used. This is important, as Prolog uses upper-case letters to represent its own variables.

You can see how this grammar is specified in file g0.pl Our convention is as follows: Variables are stated as facts. These facts simply state the names of the variables. In this example, the facts state that s and v are variables as shown below.

variable(s).
variable(v).
We also specify which symbols are terminals as shown below. 
terminal(0).
terminal(1).
terminal(+).

The grammar rules are stated as ordered pairs, where the first element is the left-hand-side of a rule and the second argument is the LIST of elements appearing on the right-hand-side of that rule. For the grammar above, these rules are stated as shown below.

rule(s, [v, +, s]).
rule(s, [v]).
rule(v, [0]).
rule(v, [1]).

Finally, we will have one rule saying which variable is our "start symbol" (where the parse should begin).

startsymbol(s).
  1. First, write a predicate terminals(L) that checks whether L is a list of nonterminals. To make things more interesting, you should structure your definition so that the query 
      ?- terminals(L)
    produces all finite lists of terminals in order from shortest to largest. There will be infinitely many (so don't try to use setof to collect them all), but you should be able to get more for as long as you are willing to hit the semicolon key. For example, after g0 is loaded, you might see: 
      ?- terminals(L).
   L = [] ;
   L = [0] ;
   L = [1] ;
   L = [+] ;
   L = [0, 0] ;
   L = [1, 0] ;
   L = [+, 0] ;
   ...etc...

    Hint 1: if Prolog satisfies the query p(X), q(Y) and you ask for a different solution by hitting semicolon, Prolog will try all the different ways to solve q(Y) before it goes back and tries to find a different solution for p(X).

    Hint 2: if your code isn't doing what you expect, enter trace. and re-run the query. You can single-step (“creep”) through the search process by hitting enter after each step. When you're done, you can hit a to abort single-stepping. To turn off tracing, nodebug.

  2. Next, we'll write the heart of our general-purpose parsing function. The predicate match(S,L) should be true when the sentential form S can produce the list of terminals L according to the grammar rules. A sentential form is a list containing variables and/or terminals. It can produce the list of terminals L if by replacing variables with one or more terminals, according to the grammar rule for each variable. For example, again assuming grammar g0: 
      ?- match([v, +, s], [0, +, 1]).
  true .

  ?- match([0, +, s], [0, +, 1]).
  true .

  ?- match([+, s], [+, 1]).
  true .

  ?- match([s], [1]).
  true .

  ?- match([v], [1]).
  true .

  ?- match([1], [1]).
  true .

  ?- match([], []).
  true .
    You can assume that neither input to match contains undetermined Prolog variables; we only care about yes and no answers. Your code should follow a “leftmost” strategy: look at the first item in the sentential form, and either replace it (if it's a variable), or compare it against the first item in the token list (if it's a nonterminal). Thus, the query match([v, +, s], [0, +, 1]) should be making recursive calls along the lines of the above sequence (plus other recursive calls that may lead to dead ends)
  3. Finally, write a predicate parse(L) that succeeds if and only if L is a sequence of terminals that can be produced by the grammar, beginning with the start symbol of the grammar. Your parse predicate should report success or failure when L is an explicit list, depending on whether it can be produced by the grammar. It should also work when L is a variable, in which case it should produce all sequences of terminals derivable from the grammar, or at least as many sequences as you care to see by hitting the semicolon key. Make sure that it really does guarantee that every valid sequence will eventually be produced. For example, if your code, given grammar g0, produced only sums of zeros ([0], [0, +, 0], [0,+,0,+,0], etc.) it is not fully correct. Explain in a comment near the parse function how you know that every valid sequence will eventually be produced.

    For example, here are some sample inputs and outputs: 

    ?- [parser].           % <--- HERE WE ARE LOADING IN OUR parse PROGRAM
% parser compiled 0.00 sec, 344 bytes
true.

?- [g0].               % <--- HERE WE ARE LOADING IN A GRAMMAR
% g0 compiled 0.00 sec, 352 bytes
true.

?- parse([1, +, 0, +, 1]).
true .

?- parse([1, +]).
false.

?- parse([1, 0, +]).
false.

?- parse(L).
L = [0] ;
L = [1] ;
L = [0, +, 0] ;
...etc...

Your code will assume that there are facts already defined for the grammar using the names variable, terminal, rule, and startsymbol as illustrated above. Keep your code simple and elegant and be sure to test it thoroughly on the supplied grammars before submitting it. Each function can be done using just a few (< 10) new lines of Prolog code - if you are writing much more than that you are doing too much work!

Note: your code should work for all the grammars we provided. It does not need to work for all grammars. (See CS 81 and CS 131 for discussion of more efficient and general parsing algorithms.)

Optional Bonus Problem: Choose-your-own-puzzle

We've seen several puzzles and the solutions for these puzzles written in Prolog. For up to +15 bonus points (depending on the complexity), write a Prolog program to solve your favorite puzzle. Here are the requirements: