CS 60, Assignment 7

Computer Science 60
Principles of Computer Science
Spring 2005

Assignment 7: Fun and Games with Rex!
Due Monday, March 7 by 11:59 PM

This is a fun and challenging assignment. Please start early! There will be one more short assignment due right before spring break. There will be no homework assigned over spring break.

Try to keep your code as elegant and simple as possible. About 20% of the score on this assignment will be based on simplicity and elegance of code. For example, don't write 20 lines of code when 10 will do. Use rex's powerful built-in functions such as map, keep, drop, or reduce in lieu of writing extra helper functions when possible.

This assignment has four parts. You will be submitting four rex files called part0.rex, part1.rex, part2.rex, and part3.rex.

Part 0: 2-Dimensional Arrays! [10 Points]

This zeroeth part of the assignment is about implementing 2-dimensional arrays in rex. (It's called "Part 0" because arrays begin indexing at 0!) In the file /cs/cs60/assignments/assignment7/part0.rex you will find the code for one-dimensional arrays that we implemented together in class. Your task is to write a getter and setter for two-dimensional arrays. Write the following functions and submit them in a file called part0.rex:

get(A, i, j) returns the value stored in "row" i and "column" j of 2-dimensional array A. If nothing has been inserted into A, you should treat it as an infinitely large array of 0's. You will find it useful to represent array A as a list of lists. Each list in A corresponds to a row of elements in the array. Thus, each list (or "row") is actually a 1-dimensional array. It will be useful to use the code for 1-dimensional arrays that we developed in class. See examples in the next problem description.
set(A, i, j, X) constructs a new list which represents a 2-dimensional array identical to A except that the element at "row" i and "column" j of the array is now set to have value X. Again, it will be useful to use the code for setting elements in a 1-dimensional array as described in class. Here are some examples of get and set in action:
```
  rex > myarray = [];
  1

  rex > get(myarray, 3, 4);
  0

  rex > myarray = set(myarray, 3, 4, 42);
  1

  rex > myarray;
  [[], [], [], [0, 0, 0, 0, 42]]

  rex > get(myarray, 3, 4);
  42

  rex > get(myarray, 3, 3);
  0
  
```

Part 1: Scrabble Scoring [25 Points]

In the game of scrabble, each word played receives a score which is the sum of the values of its letters. The following table contains a list of lists of the form
[ letter, letter's value, number of letters available ].
For example, the letter 'b' is worth three points and there are two of them available in the game. (For this problem, you can ignore that third entry - number of letters available - we're not using that data here.)
```
    scrabbleScores =
    [
    ['a',1,9],
    ['b',3,2],
    ['c',3,2],
    ['d',2,4],
    ['e',1,12],
    ['f',4,2],
    ['g',2,3],
    ['h',4,2],
    ['i',1,9],
    ['j',8,1],
    ['k',5,1],
    ['l',1,4],
    ['m',3,2],
    ['n',1,6],
    ['o',1,8],
    ['p',3,2],
    ['q',10,1],
    ['r',1,6],
    ['s',1,4],
    ['t',1,6],
    ['u',1,4],
    ['v',4,2],
    ['w',4,2],
    ['x',8,1],
    ['y',4,2],
    ['z',10,1]
    ];
    
```
This list is available in the file /cs/cs60/assignments/assignment7/scrabbleScores.rex. You can include it (and thus use scrabbleScores) by including the line
```
    sys(in,"/cs/cs60/assignments/assignment7/scrabbleScores.rex");
    
```
in your file (or, in theory, at the rex prompt). This line is already in the template part1.rex file, available in /cs/cs60/assignments/assignment7.

In the file part1.rex write a function wordScore(w), which takes a word w (in the form of a string) and returns the word's scrabble score:
```
    rex >  wordScore("quiz");
    22

    rex >  wordScore("twelve");
    12

    rex >  wordScore("fuzz");
    25
    
```
Notice that the number of letters available does not play a role here.

Hints: The built-in functions assoc and explode will be useful for this problem. See the scrabbleScores.rex file for an explanation of assoc. Here's a quick description of explode:

explode takes a string as input and outputs the same string and a list of characters, e.g.,
```
    rex >  explode("rex"); // The idea of exploding rex is sometimes tempting!
    [ r, e, x ]
    
```
where those three characters are literal characters and not variables. Note that when outputting characters, rex does not print the single quote that is necessary for inputting characters. Thus, if you ever want to transform a list of characters into a string, you need to type
```
    rex >  implode([ 's', 't', 'a', 'r' ]);
    star                                    // actually a black hole?
    
```
Next, you will put the above wordScore function to use with three-letter words!

If you have played Scrabble, you may have found yourself often staring at a rack of letters like "aaeiijx". There is a complete list of allowed three-letter words (the list is named ospd3) in /cs/cs60/assignments/assignment7/threeLets.rex. This problem puts rex to work to find the highest-scoring word from this list that can be formed using letters from a particular rack.

Also in the file part1.rex write a function named bestThree that finds the highest-scoring three-letter word from a rack of letters. bestThree(rack) should accept any seven-letter string (of lowercase letters) as the rack and then return the highest-score achievable with that rack, along with the word achieving that score in a two-element list. There may be several correct answers, in which case bestThree may return any one of them.

In the process of writing bestThree you will want to write several helper functions along the way.

By including the line
```
    sys(in,"/cs/cs60/assignments/assignment7/threeLets.rex");
    
```
in your part1.rex file, the variable ospd3 will be bound to a list of all legal three-letter words. (The name ospd3 stands for the Official Scrabble Player's Dictionary's three-letter words.) Be sure to do this.

Some input/output examples:
```
    rex >  bestThree("aaeiijx");
    [10, axe]

    rex >  bestThree("abcdabc");
    [7, cab]

    rex >  bestThree("eiilrrx");
    [10, rex]
    
```
One caution: because bestThree is somewhat compute-intensive, there may be a bit of a wait for it to return an answer. Our solution requires about 5 seconds; yours may be faster or slower depending on your approach. Remember to submit all the code for this part of the assignment in a file called part1.rex.

Part 2: Twenty Questions (35 Points)

In this part of the assignment you will be implementing twenty questions in rex. Please put this code in a file called part2.rex.

Here's an example of how the game will look when you run it:

  rex > play();
  Is it bigger than a breadbox? yes
  Is it an elephant? no
  I'm clueless!  What were you thinking of? a computer scientist
  Please give me a question that distinguishes between an elephant and
  a computer scientist.
  Does it have a long trunk
  And what would the answer be for a computer scientist? no
  Would you like to play again? yes
  Is it bigger than a breadbox? yes
  Does it have a long trunk? no
  Is it a computer scientist? yes
  Would you like to play again? no
  Thanks for playing!

We have provided files called part2.rex (there's not much there, but this is where you will be doing your coding) and io.rex in the directory /cs/cs60/assignments/assignment7. You should read through these files, especially io.rex carefully! It defines all of the input/output functions that you will need and even defines the initial game tree and a few other things! ALL of your code for this problem will be in the file part2.rex. This file already includes io.rex which has the provided input-output functions. You should not modify io.rex.

After you have examined io.rex to see what it provides, take a look iodemo.rex in that same directory. This file demonstrates how the io.rex file gets used. Please read this file carefully as well.

Here's how your program should behave:

The game is launched by invoking play() which is defined in io.rex.
When the user is asked a question, the answer should be assumed to be either yes or no. You don't need to worry about other possible inputs.
When the user defines a new animal, he or she will provide the accompanying pronoun. (As in an aardvark or a zebra).
When the user is asked to enter a question to distinguish between two animals, the user does not provide the punctuation. (The question mark will be taken care of automatically by the "ask" function that we've provided.)
The user must be invited to play again, as long as he or she likes.

Here are the things that you'll need to know in order to implement this game in rex:

rex functions are perfectly happy to deal with strings. You might wish to take a few minutes to read over the documentation on strings in rex in the on-line rex documentation.
String comparison works in the "right" way. For example, it's valid to have the statement X == "yes" ? do_something() : do_something_else().

Think about this program very carefully before writing it. Take a look at how we wrote insert and how you wrote the delete function for binary search trees. Both are good reminders of how to operate on trees. In particular, note that rex functions produce new output. This means that a result of playing one round of 20 Questions is that a new tree is constructed. It may be exactly the same as the original tree (if the user guessed an animal that the program knew) or it might differ from the original tree very slightly (by having one new question and one new animal). An important observation here is that a consequence of playing one round of the game is that a new tree is constructed. This new tree is the tree that we use if the player chooses to play another round of the game.

For full credit, keep your program as simple and elegant as possible. The file, part2.rex can be done in roughly 12 lines of rex code. (A bit more or less is OK too, but if you are writing 30 lines of code, this is an indicator that you are doing too much work and your code is unnecessarily complicated.)

Part 3: Recursive Descent Parsing (30 Points)

In this part of the assignment you will be writing a recursive descent parser and an evaluator for arithmetic expressions with addition, multiplication, exponentiation, negation, and parenthesization. In particular, we will use the unambiguous context-free grammar that we saw in class:

S -> P + S | P
P -> E * P | E
E -> U ^ E | U
U -> ( S ) | - V | V
V -> '0' | ... | '9'

Your task is to write a recursive descent parser for this grammar. One of the functions in your file should be called parse. This function takes a string to parse and returns a list of two things:

A parse tree, a tree of operations and variables that reflects the computational structure of the input expression as we demonstrated in class.
A residue list, a list of characters (tokens) that have not yet been parsed.

Note that the first element in each case will be a parse tree, and the second element will be the residue list. If the parsing was successful, the residue will be the empty list.

From our experience, a good way to approach this problem is to first build a parser for a simplified version of this grammar. For example, you might begin with the grammar:

S -> P + S | P
P -> E * P | E
E -> V
V -> '0' | ... | '9'

Once you get the parser working for this grammar, you can extend it to the full grammar for this problem.

Here's an example of how your parse function will behave once you have implemented the full grammar. Notice that in the first two examples, the residue is empty because parsing was successful. The third example did not succeed in parsing because the input was malformed.

rex > parse("1+2^3");
[[+, 1, [^, 2, 3]], []]

rex > parse("(1+2)^3+-4");
[[+, [^, [+, 1, 2], 3], [-, 4]], []]

rex > parse("1+2*+3");
[[+, 1, [*, 2, Error]], [BADTOKEN, 3]]

Take a look at (and feel free to use any part of) the file part3.rex which is in the directory /cs/cs60/assignments/assignment7. It shows a recursive descent parser for expressions using only addition. Note the use of explode to tokenize the original string, i.e., to break it into individual meaningful units, which in this case are single characters. Note that your input string should have no whitespace, since whitespace will be converted into additional "space" characters by explode.

Once you have successfully written your recursive descent parser, implement an Evaluate function and whatever other helper functions you need. Evaluate takes as input an arithmetic expression (with addition and multiplication and one digit numbers) and returns its arithmetic value. For example, here is how your Evaluate function should behave.

rex > Evaluate("1+2^4");
17

rex > Evaluate("1*2+3");
5

3 rex > Evaluate("1+");
Bad Input

Notice that this function should return the string "Bad Input" if the expression is malformed. The Evaluate function will need to call the parser and some helper functions. You may wish to use the rex built-in function make_number which takes a character as input returns a number corresponding to that character. For example,

rex > make_number('4');
4

rex > 1 + make_number('2');
3

Remember to place all of your code for this part of the assignment in a file called part3.rex.