Assignment 7: More java and more rex [100 Points]
Due Wednesday, October 25 by 11:59 PM

Part 1: Spam[pede/sweeper] version 2.0! [40 points]

In this part of the assignment you will improve the design and the functionality of your spamsweeper or spampede program. You should work with the code that will benefit the most from a redesign (i.e. the assignment in which your score was lower or that you feel went worse for you). For this program (either spamsweeper or spampede) your tasks are the following:

1. In a file called part1.txt, write a few sentences about why you chose the program you did (i.e. why did you feel it had more room for improvement than the other). Your reasoning does not have to be detailed, but should refer to some aspect of good coding style (e.g., my functions were too long, I used too many magic numbers, my lack of incremental design made my code very un-modular, etc.)
2. Improve your design. Almost all code has room for improvement in its design, even if the grutors did not take off points. Identify a number of ways that your design could be improved and make those changes to your code. Detail and justify your changes in the part1.txt file. The exact number of changes will depend on your original design, but I am looking for somewhere around 2-3. However, note that the quality of your improvements and your justification is more important than the quantity.
   
   Note: Some of you submitted very nice designs the first time around that need only very minor improvements. If you are having trouble seeing any substantive redesign that would improve your code, you may instead submit a justification of 2-3 aspects of your original design (e.g., what was good about the way you broke up your functions, the variables you introduced, etc)?
3. Improve your functionality: Fix any problems with the functionality of your program that you or the grutors encountered. Document those changes in your part1.txt file. If you did not have any errors in functionality, add one significant bonus feature to the play of your game.

This assignment is intentionally (slightly) vague to help get you thinking about the issues in real-world software design. Keep in mind the following elements of good programming as you do this part of the assignment:

• Magic numbers (don't use them)
• Modular design (i.e. code doesn't have a lot of interwoven dependencies)
• Getters and setters
• Good variable and function names
• Small methods
• Public vs. private
• Good comments
• Abstraction and code reuse
• Code distribution between classes
• Spacing and code readability

For this part, you should submit your part1.txt file as well as all of the files needed to play your Spamsweeper or Spampede game.

Part 2: Preventing SpamWars [30 points]

For this problem and the next, please use the standard commenting convention of your name, file name, and date in each file. In addition, please have at least a one-line comment for each function that you implement. Finally, please BE SURE TO NAME YOUR FILES AND FUNCTIONS EXACTLY AS WE'VE SPECIFIED. The grading procedure for this assignment is partially automated and files and functions whose spellings differ from those below will cause our scripts to "barf".

Put all of your code for this part in a file called part2.rex There is already some code in this file at: /cs/cs60/assignment7/part2.rex.

The mayors of a number of neighboring cities have been noticing some conflicts brewing between their cities over the rumor of an upcoming Spam shortage. Cities with small Spam reserves have been making plans to raid the stores of those with larger reserves, should it come to that.

The mayors, wishing to avoid all conflicts over canned meat products, have decided that if two cities are about to go to war, the mayors will cut off all access from one city to another by destroying all roads that would allow travel between the two towns (perhaps by way of other towns). They want to do the minimal damage to their infrastructure, so they have contacted Napquest, the company from the bonus problem in Assignment 6, to help them determine the minimum number of roads that must be destroyed in order to fully separate the two cities. Napquest has hired you to help with this problem.

In this problem, a map is a list of two things: a list of cities and a list of roads. The list of cities is a simple list of city names (they might be numbers or strings). The list of roads is a list of pairs, where each pair is a list of the form [City1, City2]. City1 and City2 are just names of cities that must appear in the city list (again, they might be numbers or strings). The roads are undirected, that is, a road from City1 to City2 will also allow travel from City2 to City1. Order does not matter. (Note that we include a full list of cities in our map representation, rather than including just the edges, because we want to be able to represent a city in the map even if there are no roads connected to it.)

Your job is write a program called minRoadCut which takes as input three things: The names of two cities on the brink of war and an entire map. The function returns the value of the smallest number of roads that must be destroyed to successfully separate the two cities. Remember that roads are undirected and that it is not sufficient simply to cut the road between City1 and City2 (if one exists in the first place) because there might be another way to get there going through City3, for example.

The solution to this problem is not long, but this problem will take significant planning, so make sure you sit down and map out an algorithm before you start coding! This planning is extremely important to avoid confusion and frustration. Weirdo analysis is a good way to approach this problem, but you will need to deal with a number of subproblems (e.g., determining when you are done).

As one subpiece we recommend writing a modified version of reachable that works on our new graph (i.e. map) structure. reachable should take as input two cities and a map and return true if there is a way to get from City1 to City2 on the map, and false otherwise.

To help you with this task, we have provided a "reachableDir" function that works for directed graphs (that may contain cycles) using the representation from Part 1 of Assignment 6 (i.e. a graph is a list of pairs representing edges in the graph). reachableDir takes two cities and a directed graph and returns true if there is a way to get from City1 to City2. Essentially reachableDir is the solution to "reachable" from Assignment 6, but our version can definitely handle cycles in the graph (yours was not required to). Note that this function almost solves our problem and could be very useful if only our roads were directed rather than undirected....

The program need not be fast, but it must compute the right answer. For full credit, keep your code very short.

Finally, remember to test your code carefully on a number of sample graphs (maps) that you create.

Part 3: Scrabble Scoring [30 Points]

1. 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/assignment6/scrabbleScores.rex. You can include it (and thus use scrabbleScores) by including the line

       sys(in,"/cs/cs60/assignments/assignment6/scrabbleScores.rex");
       

   in your file (or, in theory, at the rex prompt). This line is already in the template part3.rex file, available in /cs/cs60/assignments/assignment7.

   In the file part3.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 as 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?
       

2. 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/assignment6/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 part3.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/assignment6/threeLets.rex");
       

   in your part3.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 part3.rex.