Harvey Mudd College
Computer Science 60
Assignment 6, Due Monday, March 1, by midnight

"Tyrannis Rex"

This assignment is worth 100 points.

You are asked to construct several function definitions in rex and test them. You should submit your functions in a single file named hw6.rex. It is easiest to start from the file /cs/cs60/assignments/assignment6/hw6.rex, which has a few lines of rex code that will help with the later problems. (Otherwise, you'll have to add those lines yourself!)

Important psychological note With the exception of the last problem (#15, bestThree), each of these rex functions can be built in just a few (3-4) lines of code, and many in just 1 or 2. Because of this, the ratio of thinking to coding is much higher in rex than java! So, don't get worried when most of your time is spent in thought about the problems, rather than typing them in... . Also, be sure to test things thoroughly.

Reading

This assignment touches on the early parts of Prof. Keller's text up through Chapter 3, though the topics needed will also be covered in class. There are many more examples in the book than we can cover in class.

Submission

You should submit the file you create (named hw6.rex) by running (at the unix prompt)

  >  cs60submit hw6.rex

  >  cs60submitall

The problems

1. Construct a function named sum taking a list of numbers as an argument and returning the sum of the list of numbers, e.g.,

         rex >  sum([5, 8, 9]);
         22
   
         rex >  sum(range(1,10));
         55
         

   (Hint: Use reduce.)
   
   
2. Use sum to construct a function named average, which computes the (arithmetic) average of a nonempty list of numbers. That is,

         rex >  average([5, 8, 9]);
         7.33333
   
         rex >  average(range(1,10));
         5.5
         

   You will want to use the float function, along with the length of the list, in order to obtain floating point averages. Note that

         rex >  22/3;
         7
   
         rex >  22/float(3);
         7.33333
         

3. Create a function called power(x,y) that takes two nonnegative integers as input and outputs x raised to the y power. For our purposes, any nonnegative integer (even 0), raised to the zeroth power, is 1. Some examples of power would be

         rex >  power(3,4);
         81
   
         rex >  power(10,3);
         1000
   
         rex >  power(42,-42);
         1
         

4. The function power is, in essence, repeated self-multiplication, where the first argument to the function is the number to be multiplied and the second argument represents the number of times the first is to be multiplied by itself. Write a recursive function superpower whose relation to power is the same as power's relation to multiplication. Thus, superpower is repeated "self-powering," and we assume superpower(n,0) is 1 for any n.

   As an example, superpower(2,3) is "2 to the power of 2 to the power of 2" or
   
   which is 2 to the fourth power, or 16. Write the superpower function. Again, the two inputs will both be nonnegative integers.

         rex >  superpower(2,3);
         16
   
         rex >  superpower(3,3);
         7625597484987
         

   (Rex supports infinite-precision integer arithmetic -- for instance, you might want to check out superpower(2,5), but you might have to turn off any built-in memory limits. (Ask...) The result has 19,730 digits!)
   
   
5. Just as power creates large outputs from small inputs, logarithms do the reverse. In particular, one can imagine that log-base-2 simply counts the number of times its input can be divided by two until 1 is reached. For this problem, create a function log2(x) that takes a single positive integer as an argument. It should output the number of times that x can be divided by 2 until the resulting value is 1 (integer division always rounds down, which is what you'll want in this case). For the purposes of this problem, log2 of any negative input should return 0. Use recursion as in the power function. Be sure to remember the base case!

          rex >  log2(16);
          4
          
          rex >  log2(31);
          4
          
          rex >  log2(32);
          5
          
          rex >  log2(1);
          0
   
          rex >  log2(-42);
          0
          

6. Write a tail recursive version of the above log2 function, called log2_tr. Remember that tail-recursive functions do no computation after their recursive calls (though they likely need to do some computation beforehand!) In addition, they often use an additional argument (the accumulator).
   
   
7. The built-in function reverse takes any list as input and returns a new list with the same elements, only in reverse order. Thus, reverse([1, 2, 3]) is [3, 2, 1]. Write a function superreverse, which takes a list of lists as input and outputs a new list whose elements are reversals of the original lists. For example,

       rex >  superreverse([ [1,2,3], [4,5,6], [7,8,9] ])
       [ [3,2,1], [6,5,4], [9,8,7] ]
   
       rex >  superreverse([['o','l',['I']],['e','v'],[['e','x'],'r']]);
       [[[I], l, o], [v, e], [r, [e, x]]
       

8. Write a function duperreverse, which takes a list L whose elements might be numbers or lists or lists of lists, etc. This function returns a list which is the reversal of L. If L contains a list, it and any sublists get recursively reversed. Here is some example input and output:
   
   

       rex > duperreverse([1, [2, 3], [4, [5, 6, [7, 8], 9] ] ]);
       [[[9, [8, 7], 6, 5], 4], [3, 2], 1]
   
       rex > duperreverse([['o','l',['I']],['e','v'],[['e','x'],'r']]);
       [[r, [x, e]], [v, e], [[I], l, o]]
       

   You will want to use the predicate atomic to implement this function.
   
   
9. Write a function pair(X, L) that returns a list of all pairs (a pair is a list with exactly two elements) in which the first element is X and the second element is taken from L. For example here is some sample input and output:

     rex > pair(1, [2, 3, 4]);
     [[1, 2], [1, 3], [1, 4]]
     

   
   
   
10. Write a function all_pairs(L1, L2) that takes two lists as arguments and returns a list whose elements are all the pairs with the first element from L1 and the second element from L2. For example here is some sample input and output:

      rex > all_pairs([1, 2, 3], [4, 5]);
      [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]
      

    
    
    
11. Write a tail-recursive version of length(L) that returns the length of its input list, L. You should call your function length_tr (don't call it length, because that is built in to rex). You may want to remind yourself about tail recursion... (problem 6 provides a few hints).



12. Write a function intersect(L1,L2) that returns a sorted list of all of the elements that appear in both the input lists, L1 and L2. If an element appears n1 times in one of the inputs and n2 time in the other input, it should appear min(n1,n2) times in the output list. You may assume that L1 and L2 will be sorted, and for full credit your approach should use the efficient "merge" method discussed in class.

    Here are some example inputs and outputs:

      rex >  intersect([4,5,5,5,6,6],[4,4,4,5,5,7,7]);
      [4,5,5]
    
      rex >  intersect(sort(explode("english")),sort(explode("language")));
      [e,g,l,n]
      

    
    
    
13. (A problem demonstrating Rex's broad application base...) Create a function named bowl(L) that takes as input a list of pairs, where a pair is a list of two elements. Just for the sake of discussion, we will call each of the input list's pairs a frame. The score of a frame, in general, is just the sum of the two integers in the frame. However, there is an exception. If the two integers in a frame add up to 10, then the first integer in the next frame gets added into the former frame's score (a "spare"). If there is no next frame, this extra rule is ignored, and the score of the frame is the sum of its two integers.

    The result of bowl(L) should be the sum of all of the frames in L.

    The following examples should make this clear, and they are simpler than the wordy explanation above:

           rex >  bowl( [ [5, 5], [2, 7] ] );
           21
    
           rex >  bowl( [ [4, 6], [1, 0] ] );
           12
    
           rex >  bowl( [ [0, 1], [2, 9], [4, 6] ] );
           22
    
           rex >  bowl( [ ] );
           0
    
           rex >  bowl( [ [10, 0], [2, 8], [1, 2] ] );
           26
           

    Hint: Try using multiple rules and pattern matching to simplify your code.
    
    
14. 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 the number of letters available -- it plays a role in the optional extra credit.)

        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 adding 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 example hw6.rex file, available in /cs/cs60/assignments/assignment6. Make sure that the above line is in your hw6.rex file! That way, the variable scrabbleScores will be bound to the above list and you can use it as necessary.

    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 -- but see the extra credit for a more true-to-life scrabble-scoring function.

    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"); // in case you're thinking regicide by now... 
        [ 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...
        

    In fact, your thinking at this point may have veered more toward the topic of four-letter words. A list of all scrabble-acceptable ones appears in /cs/cs60/assignments/assignment6/fourLets.rex.
    
    

15. Because there are far fewer scrabble-acceptable three-letter words than four-letter words, this final problem will put the above wordScore function to use with three-letter words.
    
    If you have played scrabble and have luck similar to mine, you 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.

    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. Those are up to you... .

    By including the line

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

    in your hw6.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.
    

Extra Credit Opportunities

1. For totally optional bonus credit (of 10%), write an improved scrabble-scoring function, hardScrabble, which takes into account the fact that there are a limited number of tiles of each letter available in the game and that there are two blank tiles, worth no points, which act as wildcards. If the word can not be formed at all in the game of scrabble, the hardScrabble function should simply print "Impossible word!"

   For example, two differences between scrabbleScore and hardScrabble are

     rex >  scrabbleScore("fuzzy");
     29
   
     rex >  scrabbleScore("pizzazz");
     45
   
     rex >  hardScrabble("fuzzy");
     19
   
     rex >  hardScrabble("pizzazz");
     Impossible word!
     

   
   
   
2. For another totally optional bonus credit (of 10%), and in keeping with the closer-to-reality theme of the previous problem, write a function realbowl(L). realbowl takes the same kinds of inputs as superbowl, and does bascially the same thing as superbowl with a three exceptions:
   
   
   • The input, L, may contain frames of the form [10, 'x']. That is, if the first element of a frame 10, the second element may be the character 'x'.
     
     
   • If the sublist [10, 'x'] does appear, then the score of that frame is 10 plus the value of the next two integers in the subsequent frame or frames. If there is only one subsequent integer, then only it gets added in; if there are none, nothing gets added in.
     
     
   • Any frame past the tenth is used only to fulfill the "strike" and "spare" requirements, and not added in again to the final score . This adds a bit of complexity to your solution, as you need to count frames -- calling another function that has an additional argument used as a counter is one strategy for doing this. However, it's important if the code is to live up to its name.
   
   Any bowling game (or partial game) can be represented as a list of these kinds of sublists. Examples include

          rex >  realbowl([ [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'], 
                            [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'], [10, 'x'] 
                            ]);
          300
   
          rex >  realbowl([ [10, 'x'], [4, 6], [5, 0] ]);
          40
          

   Note that realbowl does handle inputs that aren't real bowling games, e.g., anything with [10, 0] in it.