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.)
[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.
[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:
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]
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 .
[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 points] Write a Ruby function play_baccarat() (in baccarat.rb), that plays this game using the following steps:
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.)