Assignment 10: Prolog for Fun and Profit:
The Game of 24, Spamventure, and Digital Logic!

Due Monday, April 5 before midnight.

Suggested Reading: This week we will be covering Chapter 13 of Professor Keller's book.
Reminder: The second exam will be in class on Thursday, April 8. It will cover material presented since the last exam and including material from class on Tuesday, April 6.

Part 1: The Game of 24! (40 Points)

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)
  

 | ?- 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, '/' is performed using // (which is why 1-line comments in Prolog are prefaced by % and not //).

Here is an eval predicate (for evaluating trees) that will be helpful in solving this problem. This code is also in a file called part1.pl in the /cs/cs60/assignments/assignment10 directory. You may copy that code and use it freely. 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).

Remember - use recursion and Prolog's built-in search to do the work for you!

    %% eval(Tree, Value) is true iff the value of the Tree is Value.
    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 solve in action:

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

  no.


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

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

Remember that each given number must be used once and only once and that each given operator can be used any number of times (including zero!). Please submit this part of the assignment in a file called part1.pl.

Part 2: Spamventure! (35 Points)

In this part of the assignment you will be writing an interactive adventure game in Prolog!

In class we saw a simple adventure game written in Prolog. This code is available for you to copy. You can find it in /cs/cs60/assignments/assignment10/part2.pl. You can use this code as a starting point for your own adventure game.

Your adventure game must have the following features:

1. As in the code provided for you, the game should be invoked by typing start. This displays the complete instructions and the information on your current location. (See below for more on what kind of information is displayed for each location.)
   
   
2. Your game should have an objective (e.g. finding the spam, slaying the evil Spamerwonk, or some such other goal) which is stated when the game is started. The game should end when the objective has been met. (You can use the command halt. in your code to end the Prolog session.)
   
   
3. Expand the game "map" beyond the four locations in the existing file. You can build a totally new game map if you like. You should have at least 6 different locations.
   
   
4. Upon arriving at a new location, the game should give a brief description of that location (e.g. "You see a grove of Spam trees swaying gently in the wind."), a list of all of the objects at that location which can be picked up (e.g. "You see a spam", "You see a key"), and a list of new locations which can be reached (in one move) and their direction (e.g. "You see a cave to the north. You see a lake to the south.").
   
   
5. Implement a drop(X) rule analogous to the take(X) rule. If the user attempts to drop an object that she isn't holding, the program should say something like "You aren't holding that!"
   
   
6. The player may hold no more than two objects at a time. If the user attempts to take an object which would exceed this limit, she is told that this is not permitted.
   
   
7. Implement an inventory function which lists all of the objects currently held by the player. That is, when the player types inventory., she sees a list of all the items in her hand.
   
   
8. The current file has only two objects defined (spam and key). Add some more objects and make sure that each object is required for some task. (E.g. The key might be required to enter a locked door, etc.)
   
   
9. Add at least one additional feature of your own choosing. (E.g. You might introduce an animate creature in the game which is either an adversary or otherwise.)
   
   
10. Document all commands in the instructions function.
    
    
11. You need not go gonzo with this. It's easy to add tons of features but this isn't required. Up to 5 bonus points will be awarded for features beyond what is requested here.
    
    
12. Write a "cheat sheet" called README.txt which documents the sequence of moves required to win the game. The grutors will try out these instructions on your game (if they can't solve it by themselves!)

Your code will need to use dynamic assertion and retraction of facts as well as the Prolog fail mechanism described in class.

Please submit your code in a file called part2.pl and submit your cheat sheet in a file called README.txt.

Digital Logic in Prolog! (25 Points)

Digital circuit designers frequently need to represent their designs in a hardware description language and then test these designs for correctness using testing software. In industry, languages such as VHDL and Verilog are frequently used. However, we can do some of this in Prolog very easily!

We begin by specifying how AND, OR, and NOT gates work as shown below:

and(0, 0, 0).
and(0, 1, 0).
and(1, 0, 0).
and(1, 1, 1).

or(0, 0, 0).
or(0, 1, 1).
or(1, 0, 1).
or(1, 1, 1).

not(0, 1).
not(1, 0).

Think of the arguments here as "wires". Notice that for the AND gate, for example, the first two arguments are the input wires to the AND gate and the last argument is the output wire. So, the query and(1, 0, X) is asking Prolog "If I were to enter a 1 and 0 to the inputs of an AND gate, what would be the output?". Notice that NOT gates have just one input wire and one output wire.

Next, we can specify the workings of a full adder. Recall that a full adder takes three inputs, the bits X and Y to add up and a carry-in bit. The full adder computes the sum bit and a carry-out bit. The code below specifies the design of a full adder as we saw in class. The important thing to note here is that the first three arguments to fa represent the input wires and the last two arguments represent the output wires. The code for fa is strictly the digital logic for our circuit. We could have cheated and used more sophisticated Prolog code to do fa but this is NOT what we want. We want code that accurately reflects the details of our digital design so that we can later verify its correctness!

What is allowed to be in fa then? Only the use of digital devices that we have already built. So far, we only have AND, OR, and NOT gates. Notice that the program starts with its three input wires, but also specifies new wires such as NX, NY, M1, among others.

fa(X, Y, Cin, Sum, Cout) :-
    not(X, NX),
    not(Y, NY),
    not(Cin, NCin),
    and(NX, NY, R1),
    and(R1, Cin, M1),
    and(NX, Y, R2),
    and(R2, NCin, M2),
    and(X, NY, R3),
    and(R3, NCin, M3),
    and(X, Y, R4),
    and(R4, Cin, M4),
    or(M1, M2, R5),
    or(M3, M4, R6),
    or(R5, R6, Sum),  %% End of Sum 
               
    %% and now for Cout...
    and(X, Y, S1),
    and(X, Cin, S2),
    and(Y, Cin, S3),
    or(S1, S2, S4),
    or(S3, S4, Cout).

Once we have built a full adder, we can now build a 3-bit ripple-carry adder (a device to add two 3-bit numbers, as we saw in class) using a chain of full adders. Full adders are now part of our "digital library" and we can use them freely! Notice that the code below is the Prolog representation of the digital circuitry for a 3-bit ripple carry adder. Again, we could have cheated and used Prolog features (such as the "+" operator!) to add up the numbers, but this is NOT what we want if we are going to simulate circuits accurately!

%% Representation of a 3-bit ripple-carry adder.
ripple3([X2, X1, X0], [Y2, Y1, Y0], [Z3 ,Z2, Z1, Z0]) :-
    fa(X0, Y0, 0, Z0, Carry1),
    fa(X1, Y1, Carry1, Z1, Carry2),
    fa(X2, Y2, Carry2, Z2, Z3).

What is this code saying? It says "A ripple-carry adder takes two 3-bit numbers as input, call the wires for the first 3-bit number X2, X1, and X0 and the wires for the second 3-bit number Y2, Y1, and Y0. The output comes out on four wires called Z3, Z2, Z1, Z0. Inside the ripple-carry adder are three full adders. The first one takes the inputs on wires X0 and Y0, along with a hard-wired input of 0, and sends the outputs to wires Z0 and Carry1. Z0 is one of the output wires but Carry1 is a new wire that comes out of the full adder." The same kind of reasoning applies to the next two full adders.

Your task is to build a digital circuit for a 3-bit multiplier and represent it accurately in Prolog. Start, by working the digital design out on paper. Then, translate that diagram directly into Prolog using the conventions adopted here. In particular, your Prolog "circuit" should be called m3 and it should have the following signature:

m3([X2, X1, X0], [Y2, Y1, Y0], [Z5, Z4, Z3, Z2, Z1, Z0])

You will find the code for a 3-bit ripple-carry adder in the file /cs/cs60/assignments/assignment10/part3.pl. You may copy and use this code. In your implementation of m3, you will almost certainly want to build other circuits to add to your digital library - possibly even bigger ripple-carry adders.

Be careful to build your digital circuits from logic gates and other digital circuits. Do not use any other Prolog features (Prolog's addition, unification, or any other operators), as this defeats the circuit designers objectives. Test your code and submit it in a file called part3.pl.

Here is some example input and output:

| ?- m3([1, 1, 0], [0, 0, 0], X).  <-- What is 6 times 0?
X = [0,0,0,0,0,0]                  <-- It's 0.

| ?- m3([1, 1, 1], [1, 1, 1], X).  <-- What is 7 times 7?
X = [1,1,0,0,0,1]                  <-- It's 49 (32+16+1)

(Optional Bonus Problem!) The Four Fours Problem!

This bonus problem is open-ended and challenging. It is worth up to 20 points, depending on how far you get and the quality of your code.

The "Four Fours Problem" is related to the Game of 24 in Part 1. In this problem, we want to know how many consecutive non-negative integers (beginning with 0) can be constructed using arithmetic expressions involving exactly four 4's. We are allowed a number of different arithmetic operations (see below) and we wish to construct each integer using exactly four 4's. Some of the many possible examples for the first few non-negative 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))

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

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.

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 bonus.pl. You should name the main predicate as follows:

  fours(N,Tree)