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