Assignment 7 "Ultralite"
Due Friday, October 15 by 5 PM (No CS 60 dollar extenstions)

Please note the due date and time of this assignment. No CS 60 dollar extensions may be used on this assignment.

This assignment has two parts: One part is on Scrabble scoring and you know everything you need to do this part of the assignment. The second part is on infinite lists and this material will be covered in class on Tuesday, October 12.

You may use any rex built-in function that you wish. Please place all of your functions in a single file called hw7.rex. Please use the standard commenting convention of placing your name, file name, and date at the top of the file. For each of the problems below, include a comment (Java comment syntax works in rex) indicating which problem this is (such as "this is the code for the blah blah blah problem"). Please make sure that your solutions appear in the order that we have given the problems. Use white space (spaces, new lines, tabbing) to make your code readable.

Finally, please BE SURE TO NAME YOUR FUNCTIONS EXACTLY THE SAME AS WE'VE SPECIFIED BELOW. The grading procedure for this assignment is partially automated and functions whose spellings differ at all from those below will not be seen by the automatic testing programs.

Part 1: Scrabble Scoring [10 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/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 hw7.rex file, available in /cs/cs60/assignments/assignment7.

   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?
       

   The following is a fun but optional bonus problem. The rest of the assignment comes after this bonus problem.
   
2. [Optional 10 Point Bonus Problem!] In this problem 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.

   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 hw7.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. My solution requires about 5 seconds; yours may be faster or slower depending on your approach.
   

Part 2: Infinite Lists [20 Points]

  from(N) => [N |$ from(N+1)];

  get(N, [F | R]) => N == 1 ? F : get(N-1, R);

  find_index(X, [Y | L]) => X == Y ? 1 : 1 + find_index(X, L);

Now you could use these functions as follows:

rex > get(5, from(10));
14

rex > find_index(5, from(4));
2

1. First, the totally gratuitous story. Professor I. Lai of the Pasadena Institute of Technology (P.I.T.) wants to write a function that takes as input two infinite lists L1 and L2 and returns an infinite list that contains all of the elements in L1 and all of the elements in L2, where the order of the elements in this new list is not important. Professor Lai's implementation works like this:

         lai(L1, L2) => [F1 | R1] = L1, [F1 |$ lai(R1, L2)];
       

   You can try this function out in rex. For example, try lai(from(100), from(0)). What you'll discover is that the numbers from the second infinite list [0, 1, 2, ...] never ever get put on this list. That is, no matter how long you wait, you will never see 0, for example, in this infinite list. So, if you try to run

         find_index(0, lai(from(100), from(0)));
       

   you'll end up running forever! Professor Z. Ip of the Massachusetts Institutue of Typing has proposed another approach to merging infinite lists L1 and L2 which he calls "zipping". Zipping takes the first element of L1, then the first element of L2 then it goes back and takes the next element from L1 followed by the next element of L2, etc. For example, here's what would happen if we zipped from(100) with from(0):

         rex > zip(from(100), from(0));
         [100, 0, 101, 1, 102, 2, 103, 3, 104, 4, 105, 5, 106, 6, 107, 7,
       108, 
         8, 109, 9, 110, 10, 111, 11, 112, 
   
         more? (return to continue, q to quit, a to abort, g to go
         non-stop, b to break) 
       

   Your first task (and it's very short) is to implement the zip function. Use delayed evaluation, of course! Specifically, your delayed evaluation implementation of zip should put some finite number of elements on the output list (it can be more than one) and then should delay the evaluation of the rest of the list.
   
   
2. Your next task is a bit more challenging. Now you are going to implement a pairs function for infinite lists. That is, given two infinite lists L1 and L2, pairs(L1, L2) returns an infinite list of all pairs (a pair is list with two elements) in which the first element comes from L1 and the second one comes from L2. Professor Lai's implementation, called lai_pairs has the following behavior:

       rex > lai_pairs(from(0), from(0));
       [ [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], 
       [0, 6], [0, 7], [0, 8], [0, 9], [0, 10], [0, 11], 
       [0, 12], [0, 13], [0, 14], [0, 15], [0, 16], 
       [0, 17], [0, 18], [0, 19], [0, 20], [0, 21], 
       [0, 22], [0, 23], [0, 24],
   
       more? (return to continue, q to quit, a to abort, g to go
       non-stop, b to break) 
   

   Professor Di Agnol observes that this is very bad. The pair [1, 0], for example, will never ever appear on this list, no matter how long we wait! Her idea is to write a function called pairs(L1, L2) which will build all pairs from L1 and L2 in such a way that eventually any pair that you're looking for will appear on this list. Her clever insight is that the output could look like this:

       rex > pairs(from(0), from(0));
       [[0, 0], [0, 1], [1, 0], [0, 2], [1, 1], [2, 0], 
       [0, 3], [1, 2], [2, 1], [3, 0], 
       [0, 4], [1, 3], [2, 2], [3, 1], [4, 0], 
       [0, 5], [1, 4], [2, 3], [3, 2], [4, 1], [5, 0], 
       [0, 6], [1, 5], [2, 4], [3, 3], 
   
       more? (return to continue, q to quit, a to abort, g to go
       non-stop, b to break) 
       

   Take a close look at the pattern of the output. Notice that the first pair contains the 0th element of the first list and the 0th element of the second list. The next two pairs are those in which sums of the indices are exactly 1 (that is, the pair comprising the 0th element in the first list and the 1st element of the second list and then the pair comprising the 1st element of the first list and the 0th element of the second list). The next few pairs are those in which the sums of the indices are exactly 2, etc. In this way, if we are waiting for any given element to show up on the list, it will appear eventually. Your task is to write this pairs function using delayed evaluation. You may need to write several helper functions to do this. However, among the pair function and any of its helper functions, there should be a total of only one delayed evaluation (that is, the "$" sign should appear just once in total.). Again, your function should output some finite number of pairs and should then delay the evaluation of the rest of the list.