Assignment 6 "Lite": All rex all the time!
Due Monday, February 28 by 11:59 PM

Due to the exam, this homework assignment is a bit lighter than a regular assignment. However, there are still some challenging problems here so please get started early!

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, turns 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).

Please place all of your functions in a single file called hw6.rex. Please use the standard commenting convention of placing your name, file name, and date at the top of the file. 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. [3 Points] Create a function called supereverse(L) which takes a list L of lists as input and returns a list whose elements are the reversals of the original lists. Your function should be just one line of rex code that uses the Built-in map function and whatever other rex built-in function(s) you wish. For example here is some sample input and output.

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

2. [2 Points] 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
       

3. [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.
   
   
4. [6 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
     

5. [7 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
     

6. [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
       

7. [17 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.)
   
   
8. [5 Points] Create a function called minimum(T) which takes a list representing a binary search tree as input and returns the smallest element in that tree. For example, here is some sample input and output:

     rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ]];
     1
   
     rex> minimum(mytree);
     3
     

9. [15 Points] Write a function delete(X, T) which takes a value X and a list T representing a binary search tree and returns a binary search tree with all of the elements of T except with X removed. You can assume that X is definitely in the tree T. You should use the algorithm described in class for removing an item from a binary search tree. You'll need to use the minimum function that you wrote in the previous problem. Remember that to delete an element from a binary tree is not difficult if the element has 0 or 1 children. If the element (call it X) to be deleted has 2 children, we find the next larger element in the tree (call it Y) (the minimum element in the right subtree), remove Y, and place Y where X used to be. Now, we must do this using recursion! (Take a look at the insert function that we wrote in class. The recursion in delete will use similar ideas!) For example here is some input and output:

     rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ];
     1
   
     rex > delete(10, mytree);
     [20, [3, [], []], [42, [], [60, [], []]]]
     

10. [15 Points] A multi-way tree is a tree in which each node can have any number of children. For example, consider a tree with a root node Ada. Ada has three children: Betty, Bob, and Boris. Betty has four children: Cary, Corwin, Csilla, and Cyrus. Bob has no children. Boris has one child named Duvan and Duvan has two children: Esmerelda and Egbert. We will represent this tree as follows:

    mytree = ["Ada",
                    ["Betty",
                            ["Cary"],
                            ["Corwin"],
                            ["Csilla"],
                            ["Cyrus"]
                    ],
                    ["Bob"],
                    ["Boris",
                            ["Duvan",
                                  ["Esmerelda"],
                                  ["Egbert"]
                            ]
                    ]
            ];
    

    Notice that unlike our representation of binary trees, in this problem we assume a tree representation in which a leaf node is a list with just one element (as opposed to one element with two null children). Your job is to write a function called leaves(L) which takes as input an arbitrary multi-way tree and returns a list of all leaves in the tree (nodes with no children). For example, for the tree defined above, sample input and output would look like this:

    rex > leaves(mytree);
    [Cary, Corwin, Csilla, Cyrus, Bob, Esmerelda, Egbert]