module RubyLabs =begin rdoc == RandomLab The RandomLab module has definitions of classes and methods used in the projects for Chapter 9 of Explorations in Computing. The module has methods used in experiments with pseudorandom number generators. =end module RandomLab require "permute.rb" NumberLine = Struct.new(:line, :npoints, :options) Histogram = Struct.new(:bins, :max, :keys, :counts, :base, :options) DotPlot = Struct.new(:max, :options) @@numberLineOptions = { :lineThickness => 3, :lineColor => '#777777', :tickHeight => 20, :tickWidth => 1, :tickColor => '#0000FF', } @@histogramOptions = { :binColor => '#000080', :boxIncrement => 8.0, :rescaleTrigger => 50, } @@dotPlotOptions = { :dotColor => '#000080', :dotRadius => 1.0, } @@drawing = nil @@delay = 0.01 =begin rdoc == PRNG A PRNG object is a pseudorandom number generator based on the mixed congruential method. Sequences generated by a PRNG are defined by three constants, named +a+, +c+, and +m+. If x[i] is the current item in the sequence, the equation for the next item x[i+1] is x[i+1] = (a * x[i] + c) % m =end class PRNG attr_accessor :a, :c, :m, :x # Make a new pseudorandom number generator using constants +a+, +c+, and +m+. # # Example -- a random number generator that has the full period of m = 1000 but some # surprising correlations between successive values: # p = PRNG.new(81, 337, 1000) # => # # # Example: a better PRNG, using values suggested in Numerical Recipes (Press, et al): # >> p = PRNG.new(171, 11213, 53125) # => # def initialize(a, c, m) @a = a @c = c @m = m @x = 0 end # Return the current item in the pseudorandom sequence (the most recently generated random # number). def state return @x end # Set the state of the pseudorandom sequence to +val+. def seed(val) @x = val end # Get the next pseudorandom number in the sequence defined by this PRNG object. #-- # :begin :advance def advance @x = (@x * @a + @c) % @m end # :end :advance # Get a random integer between +min+ and +max+ from this PRNG object. Calls # advance the get the next value from the pseudorandom sequence, then maps it # to an integer between +min+ and +max+. #-- # :begin :random def random(min, max) return nil if max <= min range = max - min + 1 return (advance() % range) + min end # :end :random # Create a string that describes the attributes of this PRNG object. def inspect sprintf "#" end alias to_s inspect end # class PRNG # Return an array of +m+ numbers defined by the pseudorandom sequence with # parameters +a+, +c+, and +m+. The first number in the sequence is 0, and # the remaining numbers are defined by the recurrence # x[i+1] = (a * x[i] + c) % m #-- # :begin :prng_sequence def prng_sequence(a, c, m) seq = [0] (m-1).times do seq << (a * seq.last + c) % m end return seq end # :end :prng_sequence # Make a new deck of cards. Returns an array of 52 card objects, arranged # in order from card #0 (the ace of spades) through card #51 (the two of clubs). def new_deck (0..51).map { |i| Card.new(i) } end # Compute the probability of a duplicate item in a collection of +n+ items # drawn from the range [1..d]. # # Example -- to compute the # probability of drawing the same card twice when sampling with replacement # 5 times from a deck of 52 cards: # >> pdup(5, 52) # => 0.179716221420819 def pdup(n, d) return 1.0 if n > d return 1.0 - (1..(n-1)).inject(1.0) { |p, k| p * (1.0 - (k / 52.0)) } end # A helper method intended to be called via a probe to print the contents # of an array during the execution of the permute! method. The arguments # are the array to display, the location of a left bracket, and the item # location where the item next to the bracket will be moved on the next swap. def brackets(a, i, r) res = "#{r}: " if i <= 0 res += ("[" + a.join(" ") + "]") elsif i >= a.length res += (" " + a.join(" ") + " [ ]") else pre = a.slice(0..(i-1)) post = a.slice(i..-1) res += (" " + pre.join(" ") + " [" + post.join(" ") + "]") end return res end # Given an array of 5 Card objects, determine what type of poker hand is # represented by the cards. The return value is a symbol, e.g. :pair, # :full_house, etc. (call poker_rankings to see the complete list of # symbols). # # Example (assuming +d+ is a complete deck of 52 Card objects): # >> h = permute!(d).first(5) # => [AH, 6S, 7C, JH, AC] # >> poker_rank(h) # => :pair def poker_rank(a) rcount = Array.new(Card::Ranks.length, 0) scount = Array.new(Card::Suits.length, 0) a.each do |x| rcount[ Card::Ranks.index(x.rank) ] += 1 scount[ Card::Suits.index(x.suit) ] += 1 end if rcount.max == 1 straight = (rcount.rindex(1) - rcount.index(1) == 4) flush = scount.max == 5 return :straight_flush if (straight && flush) return :straight if straight return :flush if flush return :high_card else rcount.reject! { |x| x == 0 } rcount.sort! { |x,y| y <=> x } return :four_of_a_kind if rcount[0] == 4 return :full_house if (rcount[0] == 3 && rcount[1] == 2) return :three_of_a_kind if rcount[0] == 3 return :two_pair if (rcount[0] == 2 && rcount[1] == 2) return :pair end end # Return a list of symbols used to classify poker hands. def poker_rankings return [:high_card, :pair, :two_pair, :three_of_a_kind, :straight, :flush, :full_house, :four_of_a_kind, :straight_flush] end # Initialize a Hash object with keys that are poker rank symbols and values that are all initially 0. # Used in experiments that count the number of times various hands are dealt. # # Example: # >> poker_counts # => {:flush=>0, :full_house=>0, ... :high_card=>0} def poker_counts h = Hash.new poker_rankings.each { |x| h[x] = 0 } return h end =begin rdoc == Card A Card object represents a single card from a standard 52-card deck. The two attributes of a card are its rank (represented by a symbol such as :ace, :king, :three, etc) and its suit (:spades, :hearts, etc). =end class Card attr_accessor :rank, :suit unless defined? Suits Suits = [:spades, :hearts, :diamonds, :clubs] end unless defined? Ranks Ranks = [:ace, :king, :queen, :jack, :ten, :nine, :eight, :seven, :six, :five, :four, :three, :two] end # Create a new Card object. Cards are ordered from 0 to 51, with 0 being the ace of spades # and 51 being the two of clubs. If no argument is passed to new, a random card is chosen. # If an +id+ between 0 and 51 is passed the specified card is created. # # Example: # >> Card.new # => 5H # >> Card.new(0) # => AS # >> Card.new(1) # => KS # >> Card.new(51) # => 2C def initialize(id = nil) id = rand(52) if id.nil? raise "card must be between 0 and 51" if id < 0 || id > 51 @suit = Suits[id / 13] @rank = Ranks[id % 13] end # Compare this Card with Card x. Two cards are equal if they have the same # suit and same rank. def ==(x) return @suit == x.suit && @rank == x.rank end # Define the sort ordering for Card objects. Cards are compared first by suit, # and then by rank. The result of sorting a hand (and array of Card objects) is # the common situation for most card games, where cards are grouped by suit. # # Example (assuming +d+ is a complete deck of 52 cards): # >> h = permute!(d).first(13) # => [2C, QS, 8S, 6C, 10H, JS, AD, AS, 7D, 8D, JC, 4C, AH] # >> h.sort # => [AS, QS, JS, 8S, AH, 10H, AD, 8D, 7D, JC, 6C, 4C, 2C] def <=>(x) r0 = Ranks.index(@rank); r1 = Ranks.index(x.rank) s0 = Suits.index(@suit); s1 = Suits.index(x.suit) if (res = (s0 <=> s1)) == 0 return (r0 <=> r1) else return res end end @@outputform = :utf8 # Make a string to display a Card objects on the terminal. Checks # Ruby's $KCODE global variable to see if the system is using UTF-8. If so, the code for a glyph that # shows a spade, heart, diamond, or club is inserted into the string, otherwise a letter is # used. def inspect s = "" s << case @rank when :ace : "A" when :king : "K" when :queen : "Q" when :jack : "J" when :ten : "10" when :nine : "9" when :eight : "8" when :seven : "7" when :six : "6" when :five : "5" when :four : "4" when :three : "3" when :two : "2" end if $KCODE[0] == ?U if @@outputform == :utf8 s << case @suit when :spades : "\xe2\x99\xa0" when :hearts : "\xe2\x99\xa5" when :clubs : "\xe2\x99\xa3" when :diamonds : "\xe2\x99\xa6" end else s << "!irb" + @suit.to_s.chop end else s << case @suit when :spades : "S" when :hearts : "H" when :clubs : "C" when :diamonds : "D" end end return s end alias to_s inspect def Card.print_latex @@outputform = :latex end def Card.print_utf8 @@outputform = :utf8 end end # class Card # Initialize the RubyLabs Canvas with a drawing of a number line for integers from 0 to +npoints+-1. # Options that control the appearance of the display, and their default values, are: # :lineThickness => 3 # :lineColor => '#777777' # :tickHeight => 20 # :tickWidth => 1 # :tickColor => '#0000FF' # # Example: # >> view_numberline(500, :lineColor => 'blue', :lineThickness => 1) # => true def view_numberline(npoints, userOptions = {}) Canvas.init(500, 100, "RandomLab::NumberLine") options = @@numberLineOptions.merge(userOptions) line = Canvas::Line.new(0, 70, 500, 70, :width => options[:lineThickness], :fill => options[:lineColor]) @@drawing = NumberLine.new(line, npoints, options) return true end # Draw a tick mark on the RubyLabs Canvas, provided the canvas has been initialized with a call to # view_numberline. def tick_mark(i) if @@drawing.class != NumberLine puts "call view_numberline to initialize the number line" elsif i < 0 || i >= @@drawing.npoints puts "tick_mark: 0 <= i < #{@@drawing.npoints}" else x0, y0, x1, y1 = @@drawing.line.coords tx = (i.to_f / @@drawing.npoints) * (x1-x0) ty = y0 - @@drawing.options[:tickHeight] Canvas::Line.new(tx, y0, tx, ty, :width => @@drawing.options[:tickWidth], :fill => @@drawing.options[:tickColor]) sleep(@@delay) end return true end # Initialize the RubyLabs Canvas to show a histogram with the specified bins. In the # initial drawing each bin is represented by a rectangle one pixel tall, i.e. a horizontal line. # As items are added to a bin the rectangle will grow in height. If any rectangle reaches the # maximum height, all the rectangles are rescaled so the bins can continue to grow. # # The argument to view_histogram can either be an integer, which specifies the number of bins, # or an array of symbols, in which case there will be one bin for each symbol. If the argument is an integer, # a second argument can specify a maximum data value; for example, calling view_histogram(10,100) # will make a histogram with 10 bins for numbers between 0 and 99, so that data values 0 through # 9 will go in the first bin, 10 through 19 in the second bin, and so on. # # Display options and their default values are: # :binColor => '#000080' # :boxIncrement => 8.0 # :rescaleTrigger => 50 # # Example: make a histogram for the numbers between 0 and 5: # >> view_histogram(6) # => true # Example: make a histogram to count the number of times each type of poker hand is seen in an # experiment: # >> view_histogram(poker_rankings, :binColor => 'darkgreen') # => true def view_histogram(*args) begin if args[0].class == Array userOptions = args.length > 1 ? args[1] : { } raise "usage: view_histogram(keys, options)" unless userOptions.class == Hash keys = args[0] nbins = max = keys.length else userOptions = args.length > 2 ? args[2] : { } raise "usage: view_histogram(nbins, max, options)" unless userOptions.class == Hash nbins = args[0] max = args.length > 1 ? args[1] : nbins keys = nil end rescue Exception => e puts e return false end Canvas.init(500, 300, "RandomLab::Histogram") counts = Hash.new(0) options = @@histogramOptions.merge(userOptions) bins = [] binHeight = 3 binBorder = 2 binWidth = (500/(nbins+1)) binTop = 280 nbins.times do |i| x = i * binWidth + binWidth/2 bins << Canvas::Rectangle.new( x + binBorder, binTop, x + binWidth - binBorder, binTop + binHeight, :outline => options[:binColor], :fill => options[:binColor] ) end @@drawing = Histogram.new(bins, max.to_f, keys, counts, binTop, options) return true end # Update the bin for data item +x+, presuming the RubyLabs Canvas has been initialized to show # a histogram for data of this type. The bin for +x+ increases in height. If it reaches # the maximum height, rescale all the bins and increase the maximum height. def update_bin(x) if @@drawing.class != Histogram puts "call view_histogram to initialize a histogram" return nil end if @@drawing.keys i = @@drawing.keys.index(x) if i.nil? puts "unknown bin: #{x}" return nil end else xmax = @@drawing.max nb = @@drawing.bins.length if x < 0 || x >= xmax puts "x must be between 0 and #{xmax-1}" return nil end i = ((x / xmax) * nb).to_i end @@drawing.counts[i] += 1 rect = @@drawing.bins[i] x1, y1, x2, y2 = rect.coords y1 = y1 - @@drawing.options[:boxIncrement] rect.coords = [x1, y1, x2, y2] if y1 < @@drawing.options[:rescaleTrigger] base = @@drawing.base @@drawing.bins.each do |rect| x1, y1, x2, y2 = rect.coords y1 = base - ((base - y1) / 2) rect.coords = [x1, y1, x2, y2] end @@drawing.options[:boxIncrement] /= 2 end sleep(@@delay) return true end # Return an array of counts for the bins in the histogram currently on the RubyLabs Canvas. def get_counts if @@drawing.class == Histogram return @@drawing.counts else puts "current drawing is not a histogram" return nil end end # Initialize the RubyLabs Canvas to show a dot plot with +npoints+ in both the +x+ # and +y+ dimension. Drawing options and their defaults are # :dotColor => '#000080' # :dotRadius => 1.0 # # Example: intialize the drawing for a 250 x 250 dot plot with green dots: # >> view_dotplot(250, :dotColor => 'darkgreen') # => true def view_dotplot(npoints, userOptions = {}) Canvas.init(500, 500, "RandomLab::DotPlot") options = @@dotPlotOptions.merge(userOptions) @@drawing = DotPlot.new(npoints, options) return true end # Add a point at location 'x', 'y' to the dot plot on the RubyLabs Canvas. # # Example: if the canvas was initialized to show a 250 x 250 plot, this call # will display a point in the center of the drawing: # >> plot_point(125,125) # => nil def plot_point(x,y) if @@drawing.class != DotPlot puts "call view_dotplot to initialize a dot plot" elsif x < 0 || x >= @@drawing.max || y < 0 || y >= @@drawing.max puts "plot_point: 0 <= x, y < #{@@drawing.max}" else px = (x.to_f / @@drawing.max) * Canvas.width py = (y.to_f / @@drawing.max) * Canvas.height r = @@drawing.options[:dotRadius] color = @@drawing.options[:dotColor] Canvas::Circle.new( px, py, r, :outline => color, :fill => color ) end return nil end end # RandomLab end # RubyLabs