Problem Solving using Functions

Harvey Mudd College
Computer Science 60
Assignment 1, Due Thursday Sep. 9, by midnight

"Tyrannis Rex"

This assignment is 50 points of your overall grade. Each problem is worth 8 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. You don't have to write a book on each one, but at least describe the function and, if more than one or two lines, your approach. In addition, be sure to have your name at the top of the file. The example file factorial.rex in the directory /cs/cs60/assignments/a1 demonstrate appropriate commenting styles.

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.

Getting Started

Type rex at the prompt to enter the rex interpreter. 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.) You can exit rex at any time by pressing CTRL-D (control key and D). (By doing this, you will lose all of the functions that you defined while you were in the interpreter.) Play around with rex and get the feel of how it works. For documentation on rex, see the rex reference guides available here. 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 -- if so, please create your hw1.rex there. Now you can start rex back up (from the same directory in which that 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/assignments/a1. Feel free to load these files and try the example functions there.

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),232);
ok: add42(190) ==> 232

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/assignments/a1/
which have test statements with which you can try your functions for each of the assignment's problems. For example, after loading or typing your add42 function, you can try

rex >  *i /cs/cs60/assignments/a1/p0test.rex

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

You may want to copy the test files to your directory or file to save on typing the path name.

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). 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. Each problem will receive credit according to the following guidelines:

50% for a basically working program.
25% for sufficiently documenting each function
25% for a particularly good approach, concise style, and for robustness

More details on these criteria are available here. Unless your code is extraordinarily inefficient or does not use recursion (when specified), no points will be taken off for the third criterion in this assignment.

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 function you may not use is pow, the built-in power function (or ack, for that matter) -- it would make problem 2 too easy! (You might want to check your own power function with it, however).

- 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]
      
```
  (Use map.)
- 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
      
```
  (Use reduce.)
- 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
      
```
Create a function called power(X,Y) which takes two 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/assignments/a1. Use recursion. Some examples of power would be
```
      rex >  power(3,4);
      81

      rex >  power(10,3);
      1000
      
```
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 not superpower(2,6).)
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]]
    
```
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.
( Part 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 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 formatted for direct copying to a rex-readable 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/assignments/a1/fourLets.rex, in case you're interested in the highest-scoring such word... . (This is absolutely not required, however.)

(Part 2) 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/assignments/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/assignments/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 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]
    
```
For totally optional bonus credit, 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. For example, one implementation might act as follows:
```
  rex >  scrabbleScore("fuzzy");
  29

  rex >  scrabbleScore("pizzazz");
  45

  rex >  hardScrabble("fuzzy");
  19

  rex >  hardScrabble("pizzazz");
  Impossible word!
  
```

Harvey Mudd College Computer Science 60 Assignment 1, Due Thursday Sep. 9, by midnight

"Tyrannis Rex"

Getting Started

The problems

Harvey Mudd College
Computer Science 60
Assignment 1, Due Thursday Sep. 9, by midnight