Harvey Mudd College
Computer Science 60
Assignment 1, Due Thursday Jan. 27, 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 clearly commented. The five criteria the graders will be looking for with respect to formatting, comments, etc. are listed here. Be sure to have your name in a comment at the top of the file. The example file factorial.rex in the directory /cs/cs60/as/a1 demonstrates appropriate commenting styles, with comments on the commenting!

Reading

This assignment touches on parts of the text through Chapter 3, though the topics actually needed will be considered 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.

Submission

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

% cs60submit hw1.rex
You will be asked to input the assignment number, which is 1. Don't forget it's due Thursday at midnight... .

Getting Started

Type rex at the prompt to enter the rex interpreter. Note If the program rex is not found, the full pathname is /cs/cs60/bin/rex. You will want to add the directory /cs/cs60/bin to your path in your .cshrc file. Ask me or another student about doing this. You can exit rex at any time by pressing CTRL-D (control key and D). Play around with rex and get the feel of how it works. For documentation on rex, see the rex reference guides available from here. As practice, write a function called add42 which takes a number as input and returns a new number which is 42 greater than the input. For example, 
rex >  add42(-7);
35

rex >  add42(190);
232
If the user provides an input which is not a number, that's not your problem!

Once you've got the add42 function working, exit rex and type that function definition in a file called hw1.rex. You should have a cs60 directory in your home directory. Go into that directory with 
> cd cs60
When you list (ls) the files you should see 15 directories named a01 to a15. I'd encourage you to create your hw1.rex in the a01 directory. You can cd to it and then open up emacs, for example.

Now you can start rex back up (from the same directory ~/cs60/a01 in which your file is located) and, at the rex prompt, type *i hw1.rex. This will load in the file (the "*i" stands for "include") and you can now use the functions that were defined in that file. As it loads, you will see the results from each statement in the file. In particular, if you have test statements, you will see whether the tests are passed or failed. (See below.) Alternatively, you can type rex hw1.rex at the unix prompt and it will start rex up with the functions defined in the file hw1.rex. Example files are available in the directory /cs/cs60/as/a1. Feel free to load these files and try the example functions there. For example, typing at the unix prompt 

> rex /cs/cs60/as/a1/factorial.rex
will make the fac function available. (Try it!)
There is a function named test which allows for easy testing of your functions from within a file. test takes two arguments: the first is a function application and the second is the result of that function application. If, in fact, the first argument evaluates to the second, then the message ok will be printed; otherwise, the message bad will be printed. Thus, if your add42 function is working, you can try 
rex >  test(add42(-7),35);
ok: add42(-7) ==> 35

rex >  test(add42(190),231);
bad: add42(190) returned 232, should be 231
(It shouldn't be 231, but that's the answer we told it to expect in the test function.) In general, it is usually much easier to use emacs (or your favorite text editor) to create and modify files of rex statements and then "include" them as described above. There are files in the directory /cs/cs60/as/a1/ named Test#.rex, which have test statements with which you can try your functions for each of the assignment's problems. For example, after typing your add42 function into a file named hw1.rex, you can try the following (at the unix prompt, not the rex prompt): 
>  rex hw1.rex < /cs/cs60/as/a1/Test0.in
You should see that your function succeeded at all of the tests: 
hw1.rex loaded
1 rex > ok: add42(-7) ==> 35


2 rex > ok: add42(0) ==> 42


3 rex > ok: add42(101) ==> 143


4 rex > ok: add42(190) ==> 232


5 rex > ok: add42(12345678900) ==> 12345678942


6 rex >
One thing that will make typing at the prompt more like editing a file in emacs is the *r command, which toggles emacs-like line input (the arrow keys will work). However, I'd suggest doing all of your editing into a file with emacs and then loading the results into rex either with *i or by typing 
> rex (your filename)
at the unix prompt. This will load all of your functions in the specified file.

Lots more information on using rex is available at the rex summary page.

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.

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 is pow, the built-in power function (or ack, for that matter) -- it would make problems 4-5 too easy! Also, don't use log. (You might want to check your own functions with these built-in versions, however).

  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: 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 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) which takes two nonnegative integers as input and outputs X raised to the Y power. For an example of arithmetic in rex, take a look at the file factorial.rex in /cs/cs60/as/a1. Use recursion. 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
    (You might want to check out superpower(2,5), but you may have to turn off any built-in memory limits!).)

  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 (integer division always rounds down, which is what you'll want in this case) until the resulting value is 1. 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(X,Y) that takes two positive integers as arguments (X >= 2) and outputs the log-base-X of Y (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. 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.) 
        letterScores =
    [
    ['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/letterScores.rex . You can include it (and thus use letterScores) by adding the line 
        sys(in,"/cs/cs60/as/a1/letterScores.rex");
    at the rex prompt or (preferably) in your hw1.rex file.

    Write a function scrabbleScore, which takes a word (as a string) and the above letterScores list as inputs and outputs the score for that word. Thus, 

        rex >  scrabbleScore("twelve",letterScores);
    12

    rex >  scrabbleScore("quiz",letterScores);
    22
    The built-in function explode will be useful for this problem: it 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.

    On the other hand, 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, in case you're interested in the highest-scoring such word... . (This is absolutely not required, however.)

  11. Because there are far fewer scrabble-acceptable three-letter words than four-letter words, putting the above scrabbleScore function to use will be limited to the former, smaller possibilities.

    If you have played scrabble and have luck similar to mine, you have found yourself often staring at a rack of letters like "aaeiijx". Now, with a complete set of allowable three-letter words in /cs/cs60/as/a1/threeLets.rex, your goal is to write a function which finds the highest-scoring three-letter word from such a rack. By including the line 
        sys(in,"/cs/cs60/as/a1/threeLets.rex");
    either typed at the prompt or placed 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.)

    The function bestThree(string,list) should accept any seven-letter string as a rack of letters and return a list of the highest-scoring (or one of the highest-scoring) legal three-letter word that rack can create, along with the score. (There may be several correct answers.) In the process of writing bestThree you will want to write several helper functions along the way. Those are up to you... . Some input/output examples: 
        rex >  bestThree("aaeiijx",ospd3);
    [10, axe]

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

    rex >  bestThree("eiilrrx",ospd3);
    [10, rex]
  12. For totally optional bonus credit (of 20%), 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",letterScores);
  29

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

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

  rex >  hardScrabble("pizzazz",letterScores);
  Impossible word!