Harvey Mudd College
Computer Science 60
Assignment 1, Due Friday, Feb. 1, by midnight

"Tyrannis Rex"

This assignment is worth 50 points.

You are asked to construct several function definitions in rex and test them. You should submit your functions in a single file named hw1.rex. Your code needs to have an initial comment with the assignment number, your name, and the date. Also, each function should be clearly commented and should be neatly formatted.

The example file fac.rex in the directory /cs/cs60/as/a1 demonstrates appropriate commenting styles, with comments on the commenting! You can examine that file with emacs with the command command 

 emacs /cs/cs60/as/a1/fac.rex &

Reading

This assignment touches on parts of the text up through Chapter 3, though the topics needed will also be covered in class. You should, however, begin reading the book, as there are many more examples and thorough explanations of rex's features and the information structures used here. You may want to try writing some simpler functions on your own as well to get the hang of rex.

Practice Problems

If you would like to try some additional practice problems either before or after working on this assignment, there are several (with answers) in the file /cs/cs60/as/a1/practice.probs

Testing your answers

There are lots of tests available to make sure that your code is working (and, for example, that you have not made a small change to one of the functions' names, which will cause the grading programs to ignore them). In the directory /cs/cs60/as/a1/ there are lots of test files, named Test0.in through Test26.in. These files will be used in the grading of your HW, so each one your code passes will guarantee it one HW point. A test is passed when lots of OKs show up. If you see the word bad, your code has failed that test.

To use the tests, you should "redirect" them into rex after loading in your file. That is, type 

   rex hw1.rex < /cs/cs60/as/a1/Test0.in
This checks all of the tests in the file Test0.in. There are about two tests for each of the thirteen problems in the assignment (#14 and #15 are extra credit). I would recommend testing as you go, i.e., after finishing each problem. To look at the test file, you can use emacs or (quicker) just type 
   cat /cs/cs60/as/a1/Test0.in
cat is a program that simply prints a file to the screen.

Shortcuts: It would be painful to type the above line in again and again to test your code! Remember that the up arrow returns to a previous command. You can simply use the up arrow, then edit the number to be one greater, and hit return... .

Submission

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

% cs60submit hw1.rex
You will need to do this on turing from the directory in which you have your hw1.rex file.

Grading

The graders will test your functions on these and other examples. When the problem states that a function's argument has a given form, you may assume that the test cases will not take any other forms; that is, you do not need to put in error-checking for erroneous argument types. Remember that style and commenting will be worth 20% of the score. Guidelines are here. An well annotated example is in /cs/cs60/as/a1/fac.rex. Here is a brief reminder of one possible format: 

// Assignment: CS 60 assignment 1
// Author:     Zachary Dodds
// Date:       1/19/02

// NOTE TO GRADERS: I haven't slept in 128 hours!

// Problem -1:  fac returns the factorial of its input
//     inputs:  n, a nonegative integer
//
// this example uses recursion and rewrite rules to compute factorial

fac(0) => 1;
fac(n) => n * fac(n-1);

The problems

Write each of the following functions in your hw1.rex file. Feel free to use built-in rex functions (atomic, first, float, length, map, range, reduce, rest, reverse, and second, along with the arithmetic and logical operators will suffice, but you may use others). These and other built-in functions are available from the rex reference card. The only built-in functions you may not use are log, the built-in logarithm function, pow, the built-in power function, or ack, a built-in "superpower" function -- these would make problems 4-7 too easy! (You may want to check your own functions with these built-in versions, which is certainly OK.)

  1. Create a function named add42List which takes a list of numbers as input and returns a list in which each entry of the original list has been increased by 42. Example input and output are 
          rex >  add42List([1, -7, -42, 8]);
      [43, 35, 0, 50]
    (Hint: Define add42 and use map.)

  2. 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.)

  3. 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
  4. 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. For an example of recursion in rex, take a look at the file fac.rex in /cs/cs60/as/a1. (Your power function should use recursion -- keep in mind that the power function is really just repeated multiplication.) Some examples of power would be 
          rex >  power(3,4);
      81

      rex >  power(10,3);
      1000
  5. 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. For 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. 
          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!)

  6. Just as power creates large outputs from small inputs, logarithms do the reverse. 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). 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
  7. Create a function superlog(b,x) that takes two positive integers as arguments (with b >= 2) and outputs the log-base-b of x (in the same way that the log2 function computes the log-base-2 of its argument). 
           rex >  superlog(5,25);
       2
       
       rex >  superlog(7,343);
       3
    Note that superlog does not have the same relationship with log2 that superpower has with power.

  8. 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]]
  9. 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]
    You will want to use the predicate atomic to implement this function.

  10. (A problem demonstrating Rex's broad application base...) Create a function named bowl that takes as input either one or two lists. You should assume that each of those input lists contains exactly two integers. For example, valid calls to bowl would be 
           rex >  bowl( [5, 5], [2, 7] );

       rex >  bowl( [3, 9] );

    Just for the sake of discussion, we will call each of bowl's imput list(s) a frame. The score of a frame, in general, is just the sum of the two integers in the frame. Your function bowl should return the score of the first input frame. (If there is only one input frame, just return its score.) There is a special case to consider, however:

    If the two integers in a frame add up to 10, then the first integer in the next frame gets added into its score. If there is no next frame, you ignore this rule.

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

           rex >  bowl( [5, 5], [2, 7] );
       12

       rex >  bowl( [4, 6], [1, 0] );
       11

       rex >  bowl( [4, 6] );
       10

       rex >  bowl( [4, 5] );
       9

       rex >  bowl( [5, 3], [1, 0] );
       8

       rex >  bowl( [0, 7] );
       7
    Notice that the first result above is 12 because the first frame's integers add to 10 and the following integer (from the next frame) is 2. Hint: Try using multiple rules and pattern matching to simplify your code.

  11. Write a new function that expands on the previous problem: superbowl(L). superbowl takes as input a list L that contains any number of elements, but all of those elements are, themselves, lists of two integers, i.e. frames (as in the previous problem). superbowl returns the sum of the scores of all of the frames in the input. The same scoring rules apply as in the previous problem.

    If the input is the empty list, superbowl should return 0. Thus, correct runs include 

           rex >  superbowl([ ]);
       0

       rex >  superbowl([ [2, 8] ]);
       10

       rex >  superbowl([ [10, 0], [2, 7] ]);
       21

       rex >  superbowl([ [10, 0], [2, 7], [1, 2] ]);
       24

       rex >  superbowl([ [10, 0], [2, 8], [1, 2] ]);
       26
    Notice that the last result is 26 because of the following:
    1. The score of the first frame [10, 0] is 12, since its integers add to 10 and the following integer is 2.
    2. The score of the second frame [2, 8] is 11, since its integers add to 10 and the following integer is 1.
    3. The score of the last frame [1, 2] is 3.
    4. All those scores add to 26.

    (You might point out that superbowl isn't as useful as it might be. One of the extra credit problems asks you to fix this.)

    Hint: don't use reduce! Use pattern matching, recursion, and, if you'd like, bowl.

  12. 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.) 
        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/as/a1/scrabbleScores.rex . You can include it (and thus use scrabbleScores) by adding the line 
        sys(in,"/cs/cs60/as/a1/scrabbleScores.rex");
    in your file (or, in theory, at the rex prompt). Make sure that the above line is in your hw1.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,L), which takes a word w (a string) and a list L (which has a structure like scrabbleScores, above) as inputs. wordScore should return the word's score: 

        rex >  wordScore("quiz",scrabbleScores);
    22

    rex >  wordScore("twelve",scrabbleScores);
    12
    We will only test your wordScore function with the scrabbleScores list, above, but you could imagine other word-scoring schemes (the next assignment will look at some of these).

    Hints: The built-in functions assoc and explode will be useful for this problem. assoc will be covered in some detail in class -- in short, assoc(f,L) returns the first member of L whose first element is f. (All members of L must be lists.)

    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/as/a1/fourLets.rex.

  13. 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 (named ospd3) in /cs/cs60/as/a1/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,L,wordlist) should accept any seven-letter string (of lowercase letters) as the rack, a list of letter scores L (we will use only scrabbleScores), and any list of strings as wordlist and then return the highest-score achievable with that rack, along with the word achieving that score. There may be several correct answers, in which case bestThree should return one of them. Make sure the output is a list of the maximum score followed by a word (from wordlist) achieving that score.

    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/as/a1/threeLets.rex");
    in your hw1.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",scrabbleScores,ospd3);
    [10, axe]

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

    rex >  bestThree("eiilrrx",scrabbleScores,ospd3);
    [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.
  14. 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",scrabbleScores);
  29

  rex >  scrabbleScore("pizzazz",scrabbleScores);
  45

  rex >  hardScrabble("fuzzy",scrabbleScores);
  19

  rex >  hardScrabble("pizzazz",scrabbleScores);
  Impossible word!
    (Note that a wordlist is not used here to determine if the input word is actually in the dictionary.)

  15. 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:


    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.