Assignment 6: All rex all the time! [105 Points]
Due Thursday, March 2 by 11:59 PM

Due to the exam, you will have a little longer than usual to work on this assignment. However, please do get started early as there are still some rather challenging (but fun!) problems here!

Throughout this assignment, you may also use any rex built-in function that we've discussed in class. As it turns out, the following built-in functions suffice for this assignment: append, map, and max (which returns the larger of its two numerical inputs), first (takes as input a list and returns the first element in that list), and second (takes as input a list and returns the second element in that list).

Part 1: Funky Funkshens! [42 Points]

All of the functions in this part should be in a single file called part1.rex. 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. We are not enforcing any particular formating convention for your code, but do avoid writing long functions all on one line. That's ugly.

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.

1. [1 Point] Create a function named erdos which takes as input a single positive integer x (or whatever name you choose). (You don't need to check that it's a positive integer.) The output it computes is 3x + 1, in the case that x is odd, and x/2, in the case that x is even.
   Examples of correct behavior are:

       rex >  erdos(42);
       21
   
       rex >  erdos(109);
       328
       

2. [5 Points] Create a function named collapse(L) that takes a list L of positive integers as input and as output returns a list of the number of iterations required so that erdos(erdos(...(erdos(x))...)) equals 1, for each element x in the list L. (To be precise, collapse returns the smallest such number of iterations.) Thus, collapse([1]) is [0].) Keep in mind that collapse takes a single list as input.
   
   As a bit more explanation, consider collapse([3]). Looking at the previous examples from the iterate specification, we see that

     erdos(erdos(erdos(3))) = 16.
     

   Continuing in this way,

     erdos(erdos(erdos(erdos(erdos(erdos(erdos(3))))))) = 1
     

   with erdos iterated 7 times. Thus, collapse([3]) == [7]. Further examples of collapse in action include

     rex >  collapse([3, 10, 5, 16]);
     [7, 6, 5, 4]
   
     rex >  collapse([129, 55, 85]);
     [121, 112, 9]
     

   Will every positive integer collapse to 1? No one knows, though many mathematicians have worked on it. The great mathematician Paul Erdos (the most prolific mathematician of all time) actually felt that "mathematics is not yet ready for such problems." This problem is known as the Collatz problem or "3x+1" problem. If you're in the hallways of Pomona's math department, check out the poster there on this very famous problem and what's currently known about it! You might also wish to Check out this site for more information on the amazing Paul Erdos.
   
   
3. [5 Points] Write a function iterate(N, F, X), taking as input a non-negative integer N and a function F (which will always be a function of one integer argument), and an integer X. The function iterate then returns the result of repeatedly applying F on the input X a total of N times, i.e., F(F(F...(F(X)))) where the number of F's is equal to N. (This is called an iterated function system and is used, among other places, in generating fractal images.) If N is 0, iterate simply returns X. For example here is some input and output:

     //   Here I'm using the erdos function from the example above.
     //   since the first argument is 1, the desired result is erdos(3),
     //   and erdos(3) equals 10.
     
     rex > iterate(1, erdos, 3);
     10
   
     // Now I'm iterating twice and computing erdos(erdos(3)):
     
     rex > iterate(2, erdos, 3);
     5
   
     // And this is finding erdos(erdos(erdos(3)))
     
     rex > iterate(3, erdos, 3);
     16
   
     // Iterating the anonymous function below two times is equivalent to adding 2.
   
     rex > iterate(2, (x)=>x+1, 9);
     11
     

4. [6 Points] This problem will borrow heavily from the last one! Write a function iterate(N, F), taking as input a non-negative integer N and a function F (which will always be a function of one integer argument). The function iterate then returns a function of one input that is equivalent to calling F on that input N times, i.e., F(F(F...(F(X)))) where the number of F's is equal to N. The only difference from the previous problem is that iterate, when it has two arguments, will return a function, instead of a resulting value. Note that rex, like Java, considers functions with the same name but different numbers of arguments to be completely different functions. This is called overloading.

     // Here I'm using the erdos function from the example above.
     //   since the first argument is 1, the desired result is erdos(3),
     //   and erdos(3) equals 10.
     
     rex > iterate(1, erdos)(3);
     10
   
     // Now I'm iterating twice and computing erdos(erdos(3)):
     
     rex > iterate(2, erdos)(3);
     5
   
     // And this is finding erdos(erdos(erdos(3)))
     
     rex > e3 = iterate(3, erdos);
     1
   
     rex > e3(3);
     16
   
     // Iterating the anonymous function below two times is equivalent to adding 2.
   
     rex > iterate(2, (x)=>x+1)(9);
     11
     

5. [2 Points] Consider a function f which takes as input a real number and outputs a real number. Let's define the h-approximate derivative of f to be (f(x+h)-f(x))/h. Write a rex function derivative which takes as input a real-valued function f of one variable and a number h and outputs another real valued function: The h-approximate derivative of f. For example,

       rex > f(x) = x * x * x;
       1
   
       rex > g = derivative(f, 0.1);
   
       rex > g(10);
       303.01
       

6. [3 Points] Now generalize the derivative function to a function called d which takes as input a real-valued function of one variable, a value for h, and a value n. Now, d(f, n, h) returns the h-approximate nth derivative of f. For example,

       rex> f(x) => x * x * x;
       1
   
       rex> h = d(f, 2, 0.1);
       1
   
       rex> h(10);
       60.6
       

7. [5 Points] Write a function envelope(F,G) that takes two functions as input. Each function is a function of one number. (That is, F and G each take one number as input.) envelope returns a function which takes as input one number, call it X, and returns the larger of F(X) and G(X). To be precise, here greater means further toward positive infinity (not "greater in magnitude," which would work differently for negative numbers). Also, it should return F(X) if they're equal, since in that case F(X) == G(X). Careful here - envelope returns a function and not a number. For example here is some sample input and output:

       // To demonstrate, I'll first define two functions called foo and goo.
       rex > foo(X) => 2*X + 1;
       foo
   
       rex > goo(X) => 3*X - 2;
       goo
   
       // Now, envelope(foo, goo) returns a function and here we let moo
       // represent that function.
   
       rex > moo = envelope(foo, goo);
       1
   
       // Now, let's evaluate the function moo with input of 5.
   
       rex > moo(5);
       13
       

8. [15 Points] Recall that a predicate is simply a function whose output is 0 or 1, that is, false or true. A directed graph is defined to be a map made of one-way "roads" between cities. This is represented as a list in which each element is a list of two elements. For example, the graph [ [1, 2], [1, 3], [2, 3] ] represents a map in which there is a road from city 1 to city 2, a road from city 1 to city 3, and a road from city 2 to city 3. Notice that this map is ACYCLIC in the sense that there is no cycle in the map. That is, there is no way to go from a city back to itself, unless you never leave the city in the first place!

   Write a predicate reachable(a,b,G) that answers the question of whether or not you can get from city "a" to city "b" in the directed graph G. Specifically, the first two inputs to reachable are nodes in the graph G, and the graph itself is the third input. reachable returns 0 if there is no path from a to b, and it returns 1 if there is a path (possibly through other nodes) from a to b.

   NOTE Your predicate will only be given ACYCLIC graphs as input. Thus, you don't have to worry about "running around in circles" searching for whether there is a path from a to b, because there will be no cycles in the graph. Also, remember the graphs are directed. For example,

       rex >  reachable("A", "F", [ ["A","D"], ["B","D"], ["C","D"], ["A","E"], 
   	                ["D","E"], ["E","F"] ]);
       1
       
       rex >  reachable("C", "A", [ ["A","B"], ["B","C"] ]);
       0
       
       rex >  reachable("D", "D", [ ["A","B"], ["B","C"] ]);
       1
       

   As the last example illustrates, your function should acknowledge that any node can be reached from itself. What's more the node does not even need to be in the graph! (This is because the graph does not have to be connected -- an unlisted node is one with neither outgoing nor incoming edges.)
   
   

Part 2: Twenty Questions [33 Points]

Here's an example of how the game will look when you run it:

  rex > play();
  Is it bigger than a breadbox? yes
  Is it an elephant? no
  I'm clueless!  What were you thinking of? a computer scientist
  Please give me a question that distinguishes between an elephant and
  a computer scientist.
  Does it have a long trunk
  And what would the answer be for a computer scientist? no
  Would you like to play again? yes
  Is it bigger than a breadbox? yes
  Does it have a long trunk? no
  Is it a computer scientist? yes
  Would you like to play again? no
  Thanks for playing!

After you have examined io.rex to see what it provides, take a look iodemo.rex in that same directory. This file demonstrates how the io.rex file gets used. Please read this file carefully as well.

Here's how your program should behave:

• The game is launched by invoking play() which is defined in io.rex.
• When the user is asked a question, the answer should be assumed to be either yes or no. You don't need to worry about other possible inputs.
• When the user defines a new animal, he or she will provide the accompanying pronoun. (As in an aardvark or a zebra).
• When the user is asked to enter a question to distinguish between two animals, the user does not provide the punctuation. (The question mark will be taken care of automatically by the "ask" function that we've provided.)
• The user must be invited to play again, as long as he or she likes.

• rex functions are perfectly happy to deal with strings. You might wish to take a few minutes to read over the documentation on strings in rex in the on-line rex documentation.
• String comparison works in the "right" way. For example, it's valid to have the statement X == "yes" ? do_something() : do_something_else().

For full credit, keep your program as simple and elegant as possible. The file, part2.rex can be done in roughly 12 lines of rex code. (A bit more or less is OK too, but if you are writing 30 lines of code, this is an indicator that you are doing too much work and your code is unnecessarily complicated.)

Part 3: Scrabble Scoring [30 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/assignment6/scrabbleScores.rex. You can include it (and thus use scrabbleScores) by including 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 template part3.rex file, available in /cs/cs60/assignments/assignment6.

   In the file part3.rex 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 as 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?
       

2. Next, 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/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.

   Also in the file part3.rex 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/assignment6/threeLets.rex");
       

   in your part3.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. Our solution requires about 5 seconds; yours may be faster or slower depending on your approach. Remember to submit all the code for this part of the assignment in a file called part3.rex.
   

OPTIONAL BONUS: Shortest Paths [6 Bonus Points]

Finally, here is a fun but optional bonus problem which extends the reachable problem in Part 1.

You have been hired by Napquest, a company specializing in finding shortest paths between given cities. (It's called Napquest, because their algorithms tend to be inefficient, causing the users to nap while they wait for the answer!)

A map is a list of "triplets", where each triplet is a list of the form [City1, City2, Distance]. City1 and City2 are just names of cities (e.g. they might be numbers or strings) and Distance is a positive real number indicating the length of the one-way road from City1 to City2. For example, here is a valid map: [ ["Claremont", "Spamville", 1], ["Spamville", "Claremont", 2], ["Spamville", "Foobarsburg", 2], ["Foobarsburg", "Claremont", 4] ]. Notice that the map may contain cycles and that there may be funny things like a one-way road from Claremont to Spamville which is shorter than the one-way road from Spamville to Claremont.

Your job is write a program called shortest which takes as input three things: The name of the start city, the name of the end city, and an entire map. The function returns a single positive real number, namely the length of the shortest path from the start city to the end city. If there is no path from the start city to the end city, the shortest path length should be Infinity (a value built-in to rex).

The program need not be fast, but it must compute the right answer. For full credit, keep your code very short. If your code is more than 8 lines long, it's too long!

If you choose to do this problem, submit it in a file called bonus.rex. No fancy algorithms are required here. You've seen everything you need in class to do this problem.

Finally, remember to test your code carefully on a number of sample graphs that you create.