15110 Fall 2012 [Touretzky/Kaynar]

Programming Assignment 5 - due Wednesday, October 3

Overview

For this assignment, you will create a Ruby source file containing a Ruby function(s) implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function they help. You should store a source file(s) for each problem in a folder named pa5.

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

Problems

(2 points) Ruby has a method class that returns the class of an object. For example, 5.class returns Fixnum, and "woof".class returns String. Write a recursive Ruby function same_class?(x) that returns true if all the elements of the list x are of the same class. Example:
```
>> same_class?([1,2,3,4,5])
=> true

>> same_class?(["one", "two", "three", "four", "five"])
=> true

>> same_class?([1, 2, "three", 4, 5])
=> false
```
How can we write this function recursively? Consider this: if the result should be false, there must be at least one element of the list that is of a different type than the element that comes after it. So here is the algorithm:
1. Return true if the list has at most one element.
2. Return false if the first two things in the list are of different classes.
3. Recursively call yourself on the tail of the list (everything but the first element) and return that result.
(2 points) Let x = [1,2,3] and let y = [4,5,6]. For each of the following expressions, executed in the order shown here, write down the value of the expression, and say whether the value of x changed, the value of y changed, both changed, or neither changed. Put your answers in a text file called prob2.txt.
1. x + y
2. x + ["y"]
3. x + []
4. x << []
5. [x, y]
6. x << y
(2 points) In this problem you will write two versions of a Ruby function pairup(x) that takes a list x as input and returns a nested list where the elements have been grouped into pairs. We'll call the two versions pairup_r and pairup_i. You can assume the list is always of even length. Examples:
```
>> pairup_i([1,2,3,4])
=> [[1, 2], [3, 4]]

>> pairup_r(["a", "b", "c", 37, 42, 56])
=> [["a", "b"], ["c", 37], [42, 56]]
```
1. Write pairup_r(x) as a recursive function. It should (i) form a pair from the first two elements of x, and (ii) call itself recursively to form pairs from the rest of the list. How will you combine results (i) and (ii) to produce the result the function returns?
2. Write pairup_i(x) as an iterative function. It should produce the same results as the recursive version, but with a while loop instead of a recursive call.
(2 points) We can use recursive calls to build up nested lists in a variety of ways.
1. Write a recursive function nest_to_depth(n) that returns "woof" nested to depth n. Examples:
```
>> nest_to_depth(3)
=> [[["woof"]]]

>> nest_to_depth(5)
[[[[["woof"]]]]]
```
  Hints: What should be the result of nest_to_depth(0)? What is the relationship between nest_to_depth(n) and nest_to_depth(n-1)?
2. Write a recursive function nest_right(x) that turns a flat list x into a right-nested list. Examples:
```
>> nest_right([1,2,3])
=> [1, [2, [3]]]

>> nest_right(["alpha", "bravo", "charlie", "delta"]
=> ["alpha", ["bravo", ["charlie", ["delta"]]]]

>> nest_right([])
=>[]
```
(2 points) One place where recursion is especially useful is in searching nested arrays. Consider the function find_odd(x) that returns the first component of the array x that is an odd number, or nil if no elements are odd. If x were a simple list we could use an iterator such as each to search it, but in order to work correctly on nested arrays, we must use recursion. This would be harder to solve with a while loop because we'd have to maintain the "stack" ourselves. Examples:
```
>> find_odd([2, [4, [6, 7, 8], 10]])
=> 7

>> find_odd([2, [4, [6, 0, 8], 10]])
=> nil
```
Write the find_odd(x) function using the following algorithm:
1. If x is the empty list, return nil.
2. If x is an integer, then...
  1. If x is odd, return x.
  2. Otherwise return nil.
  You can use x.kind_of?(Integer) to tell if an object is an integer.
3. Otherwise, if a recursive call on the head (first element) of x returns a non-nil value, then return that value.
4. Otherwise, return the result of a recursive call on the tail of x, i.e., every element except the first.

Submission

You should now have a pa5 directory, containing:

same_class.rb
prob2.txt
pairup_r.rb
pairup_i.rb
nest_to_depth.rb
nest_right.rb
find_odd.rb

Zip up your entire pa5 directory and upload it using the handin system.