15110 Fall 2011 [Cortina/von Ronne]

Programming Assignment 8 - due Tuesday, November 8


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 for each problem in a folder named pa8.

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


  1. [3 points] Recall in class that the Linear Congruential random number generator (LCG) creates random numbers using the formula:

    \(x_{i+1} = (a \times x_i + c ) \text{ mod } m\),

    That is, if you know the ith random number xi, then you can compute the next number in the sequence xi+1 using the formula.

    Another pseudo random number generator is the Blum Blum Shub (BBS) pseudorandom number generator. (The Blums are faculty members here at Carnegie Mellon University!) Blum Blum Shub uses the formula

    \(x_{i+1} = x_i^2 \text{ mod } m\)

    (with certain restrictions on the seed \(x_0\) and modulus \(m\)) to compute a new pseudorandom number based on a previous one. In general, compared to LCG, BBS is slower, but provides higher quality random numbers that can't be predicted without first factoring \(m\), which is hard when \(m\) is the product of two large prime numbers. An example of an \(m\) that satisfies the requirements is 2006591449, which is the product of the prime numers 44771 and 44819.

    Implement a function bbs_seq(x0,n) (in bbs_seq.rb) that returns an array of \(n\) pseudorandom numbers (\(x_0 \ldots x_{n-1}\)) generated using Blum Blum Shub starting with a seed \(x_0\) of x0 with an \(m\) of 2006591449.

    Example usage:

    >> bbs_seq(1320173001,10)
    => [1320173001, 1250489923, 1654713313, 317068542, 1414597374, 1257516709, 1036152133, 891491908, 1351900575, 896699609]

    General idea: In your function, create an array of size n using Array.new, storing the seed in the first position of the array. Then, using a loop, for every position in the array except the first position, use the value in the previous position and the formula to compute its value. Return the resulting array as your final instruction.

  2. [3 points] Your textbook and lecture presented a function called permute! that shuffles a sequence using an algorithm that is a variant of the Fisher-Yates shuffle. Here is another algorithm for shuffling, which requires an array a with n elements and returns an array containing a random permutation of those n elements:

    1. Set n equal to the length of array a.
    2. Create an empty array pairs.
    3. Create an array rnd_seq that contains n random numbers.
    4. For i in 0..n-1 do the following:
      1. Create a new array consisting of two elements: 1) the element at position i in array rnd_seq and 2) the element at position i in array a.
      2. Append the array created in the previous step to pairs, making that two element array the last element of pairs.
    5. Create a new array sorted_pairs containing the elements of pairs (which are themselves each a two element array) ordered according to their first (random number) part. (See below for how to do this in Ruby.)
    6. Create an array shuffled containing the second element of each 2-element array in sorted_pairs in the same order as they are stored in sorted_pairs. (correction)
    7. Return the array shuffled as the result of this algorithm.

    Step V can be accomplished using the Ruby array operation sort_by. For example, to sort a list of pairs by the last element in each pair, we can do this:

    >> pairs = [[5, "Z"], [2, "C"], [7, "A"]]
    => [[5, "Z"], [2, "C"], [7, "A"]]
    >> pairs.sort_by {|x| x.last}
    => [[7, "A"], [2, "C"], [5, "Z"]]

    To sort a list of pairs by the first element in each pair, we can do this instead:

    >> pairs = [[5, "Z"], [2, "C"], [7, "A"]]
    => [[5, "Z"], [2, "C"], [7, "A"]]
    >> pairs.sort_by {|x| x.first}
    => [[2, "C"], [5, "Z"], [7, "A"]]

    Define a Ruby function shuffle(a) (in shuffle.rb) that implements this algorithm. Step III (correction) should be implemented by calling your bbs_seq method with a seed of Time.now.to_i.

    Example usage:

    >> include RandomLab
    => Object
    >> shuffle(new_deck)
    => [4S, 10C, QS, KC, 7S, KD, AH, JC, 3S, 9C, QC, 8D, AD, 7D, 8H, QH, 10D, JS, 6C, 7H, 10S, 6H, 3C, 5S, 8C, JH, 2S, 8S, 2D, 10H, 6S, 4C, 5C, 9H, AS, 3D, 2H, 5H, JD, 3H, KS, 2C, QD, 5D, KH, 9S, 7C, 6D, AC, 4D, 4H, 9D]
  3. Baccarat is a card game in which cards are dealt into two hands, one for the "player" and one for the "banker". In this slightly simplified version of the game, each hand consists of either two or three cards. At the conclusion of play, the hand with the highest value wins.

    The value of a hand is based on values assigned to each card. Cards with ranks of 2 through 9 have a value equal to their rank. The Ace is assigned a value of 1. The cards of other ranks, King, Queen, Jack, and 10 have a value of 0. The suit of each card (spades, hearts, diamonds, or clubs) is irrelevant. The value of a hand is the last decimal digit of the sum of the values of the individual cards. For example, a hand with a 7 of Spades, Queen of Hearts, and 8 of Diamonds, would have a value of 5, because 7 + 0 + 8 = 15, and the last digit of 15 is 5.

    Initially, two cards are dealt to the player and then two cards are dealt to the banker. Then, the player receives a third card if the current value of the player's (2-card) hand is less than six. Finally, the banker receives a third card if the current value of the banker's (2-card) hand is less than six.

    The player wins if the player's final hand has a value greater than that of the banker. The banker wins if the banker's final hand has a value greater than that of the player. If there is a tie, the banker wins .

    1. [2 points] Write a Ruby function score_hand(hand) (in baccarat.rb) that takes an array hand containing Card objects (as defined RandomLab) and computes the value of that hand as described above. Note that the hand can contain either 2 or 3 cards.

      Sample usage:

      >> h = [Card.new(6), Card.new(15), Card.new(31)]
      => [8S, QH, 9D]
      >> score_hand(h)
      => 7
    2. [2 points] Write a Ruby function play_baccarat() (in baccarat.rb), that plays this game using the following steps:

      1. Shuffle a new deck (using the shuffle function from part 2 or permute! from RandomLab, treating position 0 as the top of the deck).
      2. Create two new empty arrays for the hands for the player and banker.
      3. Add the top two cards of the deck to the player's hand and then add the next two cards from the top of the deck to the banker's hand.
      4. Add an additional card to the player's hand if the current value of the player's hand is less than six. Call the score_hand function you wrote for part (a) to simplify this step.
      5. Add an additional card to the banker's hand if the current value of the banker's hand is less than six. Call the score_hand function you wrote for part (a) to simplify this step.
      6. Print out the game's result. The output should contain the player's and banker's final hands (with the cards in the order they were "dealt"), the value of the hands, and the text "The player wins." or "The banker wins.", as appropriate. See the sample output below for the formatting for your results. You should match the formatting as closely as possible so we can test your code easily.

      Sample usage:

      >> play_baccarat()
      The value of the player's hand is 7: 6C 9C 2S
      The value of the banker's hand is 6: 8C 8D
      The player wins.
      => nil
      >> play_baccarat()
      The value of the player's hand is 0: QD 10C QS
      The value of the banker's hand is 7: 5S KS 2C
      The banker wins.
      => nil


You should now have a pa8 directory that contains the required files, bbs_seq.rb, shuffle.rb, baccarat.rb, each—in turn—containing the corresponding function(s). Zip up your directory and upload it using the handin system. (The handin system will accept submissions beginning on Friday until the deadline Tuesday night.)