15110 Spring 2013 [Kaynar/Gunawardena]

Programming Assignment 3 - due Tuesday, February 5 by 11:59 pm

Note: You are responsible for protecting your solutions to these problems from being seen by other students both physically (e.g., by looking over your shoulder) and electronically. In particular, since the lab machines use the Andrew File System to share files worldwide, you need to be careful that you do not put files in a place that is publicly accessible.

If you are doing the assignment on the Gates-Hillman Cluster machines we use in lab or on unix.andrew.cmu.edu, our recommendation is that you create a pa3 directory under ~/private/15110 for this assignment. That is, the new directory pa3 is inside a directory called 15110, which is inside the directory called private, which is inside your home directory. (Every new andrew account is set up with a private subdirectory within the account's home directory that only that account can access.) Please refer to Setting up Directories for information about managing your directories.


For this assignment, you will create a Ruby source file (that is, a text file containing Ruby code) for each of the problems below. You should store all of these files in a folder named pa3, which you will zip up and submit.

As you will discover this semester, computer programs are rarely correct when they are first written. They often have bugs. In addition to writing the code, you should test your code on multiple inputs, for which you independently know the correct output (e.g., by plugging the inputs into a calculator).

The Algorithms

  1. [2 point] DNA has the shape of a double helix which consists of two bonded nucleotide chains. Each base in these chains can bond with only one other base. Therefore, the sequence of these two chains must match precisely to form a double helix. The four bases are A (adenine), T (thymine), C (cytosine), and G (guanine). A can bond with T, and C can bond with G.

    Write a Ruby function called DNA_match(base), in DNA_match.rb, that takes in a character and returns the complementary base as a character. Your function should following the algorithm below:

    Example Usage:

    >> load "DNA_match.rb"
    => true
    >> DNA_match("A")
    => "T"
    >> DNA_match("T")
    => "A"

  2. [2 point] Recall from pa2 that $/$ and $\%$ can be used to isolate digits in an integer. Write the function digits_squared_sum(n), in digits_squared_sum.rb, that takes a non-negative integer and returns the sum of the squares of the digits.

    For example, the integer $152$ becomes $1^2 + 5^2 + 2^2 = 1 + 25 + 4 = 30$.

    Use the following algorithm:

    1. Set sum to $0$.
    2. While n is not $0$, do the following:
      1. Isolate the rightmost digit in n and set digit to this isolated value.
      2. Divide n by $10$ so that the rightmost digit is no longer there and set n to this new value.
      3. Add \(digit^2\) to sum and set sum to this new value.
    3. Return sum.

    Hint: Apply the above algorithm to the given example (number 152) to observe how it works before coding your function in Ruby.

    Example Usage:

    >> load "digits_squared_sum.rb"
    => true
    >> digits_squared_sum(152)
    => 30
    >> digits_squared_sum(3700)
    => 58

  3. [2 points] ASCII-art.

    By printing out different characters at different locations, it is possible to create images. This is sometimes called ASCII art and works best in a terminal that ues a fixed-width font. Regular shapes, such as the right triangle shown below, are easy to create - even at different sizes - algorithmically.

    				* *
    				*   *
    				*     *
    				*       *
    				* * * * * *

    This right triangle can be created using the following algorithm, which requires the triangle's height (that is, the number of lines in the triangle). It assumes that height is non-negative.

    First, print out 1 asterisk("*") on the first line (this is row 1.). Then, for the next $height - 2$ lines, print out one asterisk, print out $2*row - 3$ spaces where $row$ represents the current row number that is being printed, and then print one asterisk. Finally, for the last line, print out $height$ copies of an asterisk followed by a space ("* ").

    Note that a denegarate case of a right triangle would arise when $height =1$. In that case, we would not need to perform all of the steps decrsibed above; we would print a single asterisk.

    Create a Ruby function right_triangle(height) (in right_triangle.rb) that implements the algorithm described above. Your function must return nil.

    Hint: You will probably need a loop inside of a loop for part of your solution. If you use a loop inside of another loop, make sure to use a different loop variable for each loop (e.g. if the outer loop uses "i", the inner loop can use "j").

    Example usage:

    >> right_triangle(5)
    * *
    *   *
    *     *
    * * * * *
    => nil
    >> right_triangle(8)
    * *
    *   *
    *     *
    *       *
    *         *
    *           *
    * * * * * * * *
    => nil

  4. Imagine how a soda machine works. Before the machine distributes a can, it expects to be paid for the can (often times in exact change). The machine will display how much you owe, and as you feed it coins, it will tell you how much you still need to pay. Say a can of soda costs $\$0.95$. You feed the machine a quarter. It will now read that you owe it $\$0.70$. You keep giving the machine change until you have paid the entire amount and recieve your soda. Assume for the following questions that soda machines only take quarters, dimes, nickles, and pennies.

    1. [2 points] Write the function count_coins(price), in coins.rb, that returns the fewest number of coins needed to pay for a can of soda that costs price amount of dollars. Use the following formula:


      1. Set amount_not_paid equal to (price * 100).to_i()
      2. Set coins_needed equal to $0$.
      3. While amount_not_paid is greater than $0.1$, do the following:
        1. If amount_not_paid is greater than or equal to $25$, do the following:
          1. Decrease amount_not_paid by $25$.
          2. Add $1$ to coins_needed
        2. Otherwise, if amount_not_paid is greater than or equal to $10$ and less than $25$, do the following:
          1. Decrease amount_not_paid by $10$.
          2. Add $1$ to coins_needed
        3. Otherwise, if amount_not_paid is greater than or equal to $5$ and less than $10$, do the following:
          1. Decrease amount_not_paid by $5$.
          2. Add $1$ to coins_needed
        4. Otherwise, do the following:
          1. Decrease amount_not_paid by $1$.
          2. Add $1$ to coins_needed
      4. Return coins_needed.

    2. [2 points] Write the function which_coins(price) in coins.rb(in addition to the code for count_coins ), that prints out how many of each coin type is needed. Use the same basic format as in part a, except instead of keeping track of coins_needed, keep variables for quarter, dime, nickle, and penny. Don't forget to return nil.

    Example Usage:

    >> load "coins.rb"
    => true
    >> count_coins(1.17)
    => 8
    >> which_coins(1.17)
    You need 4 quarter(s), 1 dime(s), 1 nickle(s), and 2 penny(s).
    => nil
    >> count_coins(0.11)
    => 2
    >> which_coins(0.11)
    You need 0 quarter(s), 1 dime(s), 0 nickle(s), and 1 penny(s).
    => nil


You should now have a pa3 directory that contains the files DNA_match.rb, digits_squared_sum.rb, right_triangle.rb, and coins.rb each containing the corresponding function(s). Zip up your directory and hand it in.