Assignment 10: Prolog for Fun and Profit:
Spamventure, Logic Puzzles, and Digital Logic!

Due Monday, November 8 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, November 18. It will cover material presented since the last exam and including material from class on Tuesday, November 16.

Part 1: Spamventure! (40 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/part1.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 part1.pl and submit your cheat sheet in a file called README.txt.

Logic Puzzles in Prolog! (30 Points)

First, the true story! It's Thanksgiving Break and five students from the five colleges are heading home together on the train. Algird, Bruno, Collette, Dino, and Edwina are each from different Claremont Colleges. The 5 Claremont Colleges are: Pomona, Pitzer, HMC, CMC, and Scripps. Each student brings a different snack: Jots, Chocolate, Donuts, Pez, and Spam. They are all on the train together in seats 1 through 5. Here are the nine "hints" for the puzzle:

1. Dino and Bruno sat in the end seats (that is, seats 1 and 5, but which student sat in which of these seats is still unknown).
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 person 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.

Your task is to use Prolog to determine: which student is in each seat, what college does each student go to, and what did each student bring for a snack?

Your program should be in a file called part2.pl. When the user types solveit. the program should print out something like the following (the answer below is incorrect, but the format of the output is what you should use in your solution):

Seat 1:  collette goes to pitzer and brought donuts
Seat 2:  dino goes to pomona and brought jots
Seat 3:  edwina goes to scripps and brought chocolate
Seat 4:  algird goes to hmc and brought pez
Seat 5:  bruno goes to cmc and brought spam

You will find a file called part2.pl in the directory /cs/cs60/assignments/assignment10/ which has the rules of the puzzle as a comment. Do your coding in this file. This will help you see the rules of the puzzle as you're writing your code. Here are the requirements for your code:

• Keep your code as simple, clean, and elegant as possible.
• Encode the rules or "hints" of the puzzle but don't add any of your own shortcuts or insights into the solution.
• Each of the nine "hints" above should have its own simple inference rule.
• Have ample comments which explain what each inference rule is doing and what it corresponds to in the puzzle.
• One litmus test for the quality of your code is this: Is the code sufficiently clear that a person with knowledge of Prolog could easily translate the puzzle from your Prolog file back into English, without even looking at your comments?

Digital Logic in Prolog! (30 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 to do here. We want to write code that accurately reflects the details of our digital design so that we can later verify its correctness!

For example, using Prolog's matching abilities is not in the spirit of what we're trying to do here. Thus, code such as

mult([A, B, C], 0, [0, 0, 0]).
mult([A, B, C], 1, [A, B, C]).  

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