# Housie (#114)

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Brian C.

A version of Bingo played in the UK and some other countries is called
“Housie”.
Players buy “books” of 6 tickets. Each ticket shows exactly 15 numbers,
and in
each book every number from 1 to 90 is used exactly once.

A ticket is a grid of 3 rows by 9 columns. The first column contains
numbers
from 1 to 9; the second column numbers from 10 to 19; the third 20 to 29
and so
on up until the last column, which contains numbers from 80 to 90.

Each column contains one, two or three numbers, in increasing order
downwards.
Each row contains exactly 5 numbers (and hence 4 blanks).

An example ticket looks like this:

±—±—±—±—±—±—±—±—±—+
| 5 | | | | 49 | | 63 | 75 | 80 |
±—±—±—±—±—±—±—±—±—+
| | | 28 | 34 | | 52 | 66 | 77 | |
±—±—±—±—±—±—±—±—±—+
| 6 | 11 | | | | 59 | 69 | | 82 |
±—±—±—±—±—±—±—±—±—+

There are two levels of quiz difficulty to choose from. Given the above
rules
for the validity of tickets and books, then:

1. Write a Ruby program which generates random individual tickets
or
2. Write a Ruby program which generates random complete books of
tickets

On Feb 16, 11:47 am, Ruby Q. [email protected] wrote:

A ticket is a grid of 3 rows by 9 columns. The first column contains numbers
from 1 to 9; the second column numbers from 10 to 19; the third 20 to 29 and so
on up until the last column, which contains numbers from 80 to 90.

The problem lacks a certain symmetry, and I just want to make sure
that there isn’t a typo. Is it correct that the first column only has
9 possible values (1-9), that the last column has 11 possible values
(80-90), and that the middle columns each have 10 possible values?

Thanks,

Eric

::::

Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

On Feb 16, 2007, at 2:10 PM, Eric I. wrote:

that there isn’t a typo. Is it correct that the first column only has
9 possible values (1-9), that the last column has 11 possible values
(80-90), and that the middle columns each have 10 possible values?

That’s the scoop according to Wikipedia:

James Edward G. II

Here’s my solution. I really enjoyed this quiz. On the surface it
seems relatively simple. But there are some important subtleties.

My solution builds the book ticket by ticket, and each ticket row by
row. Since multiple constraints need to be satisfied, if at any point
it is clear that the constraints cannot be met, the program “backs
up”, to before the last ticket was placed and tries again.

Special care is taken so that as it builds up each row, a number is
more likely to appear in the last column, than in the middle columns,
and in the middle columns, than the first column.

I’m curious as to how others approach this program. I wonder, for
example, if a simpler solution would emerge if the book were built
column by column instead. Or perhaps there are some even more clever
approaches.

Eric

Are you interested in on-site Ruby training that’s been highly
reviewed by former students? http://LearnRuby.com

RequiredCounts = [9] + [10] * 7 + [11]
Line = “±—” * 9 + “+\n” # horizontal line used in text output

# the columns in between intermediate odds (10/18, or 5/9, or 55.6%).

def gen_row_pattern

# copy of RequiredCounts array for relative odds

relative_odds = RequiredCounts.dup
total_odds = relative_odds.inject { |sum, v| sum + v }
row_pattern = Array.new(9, false)
5.times do
pick = rand(total_odds)

# find column for which this random number corresponds
relative_odds.each_with_index do |o, i|
pick -= o               # subtract the odds for column from pick
if pick < 0             # have we reached the indicated column?
row_pattern[i] = true
relative_odds[i] = 0  # can't be true again, so odds is now


zero
total_odds -= o # and total odds have gone down as well
break
end
end
end

row_pattern
end

# true in it since a true corresponds to a number.

def valid_ticket_pattern?(ticket_pattern)
ticket_pattern.transpose.all? { |col| col.any? { |element|
element }}
end

# Generates a valid ticket pattern consisting of three row patterns.

def gen_ticket_pattern
begin
ticket_pattern = Array.new(3) { gen_row_pattern }
end until valid_ticket_pattern? ticket_pattern
ticket_pattern
end

# the ticket patterns).

def valid_book_pattern?(book_pattern)
return true if book_pattern.empty?

tickets_left = 6 - book_pattern.size # how many tickets remain to be
placed in book

# determine how many numbers are in each column of all booklets

column_counts =
book_pattern.map { |ticket| ticket.transpose }.transpose.map do |
column|
column.flatten.select { |element| element }.size
end

3

with

# the desired number of numbers

(0…RequiredCounts.size).all? do |i|
numbers_left = RequiredCounts[i] - column_counts[i]
numbers_left >= tickets_left && numbers_left <= 3 * tickets_left
end
end

# in its place (via the catch/throw).

def gen_book_pattern(count, book_pattern)
throw :invalid_book_pattern unless valid_book_pattern?(book_pattern)
return book_pattern if count == 0

# loop until a valid ticket pattern is added to the book pattern

loop do
catch(:invalid_book_pattern) do
return gen_book_pattern(count - 1,
book_pattern +
[gen_ticket_pattern])
end
end
end

# they are to feed into, and shuffled randomly.

def gen_number_feeders
feeders = Array.new(9) { Array.new }
(1…89).each { |i| feeders[i / 10] << i }
feeders[8] << 90 # add the extra value in the last feeder

# shuffle the numbers in each feeder

feeders.each_index { |i| feeders[i] = feeders[i].sort_by { rand } }
end

# nine values, five of which are numbers and four of which are nils.

def gen_book
book_pattern = gen_book_pattern(6, [])
feeders = gen_number_feeders

book_pattern.map do |ticket_pattern|
# determine how many numbers will be consumed in each column of
# ticket
nums_in_cols = ticket_pattern.transpose.map do |col|
col.select { |v| v }.size
end

# sort the consumed numbers in the feeders, so the columns will be
# sorted
feeders.each_index do |i|
feeders[i] = feeders[i][0...nums_in_cols[i]].sort +
feeders[i][nums_in_cols[i]..-1]
end

# convert the trues in each column into numbers by pulling them
# from the feeder corresponding to the column
ticket_pattern.map do |row|
new_row = []
row.each_index { |i| new_row << (row[i] ? feeders[i].shift :


nil) }
new_row
end
end
end

# Convert a book into a large string.

def book_to_s(book)
book.map do |ticket|
Line + ticket.map do |row|
“|” + row.map { |v| " %2s " % v.to_s }.join(“|”) + “|\n”
end.join(Line) + Line
end.join(“\n”)
end

def create_grid

# array with all allowed columns

cache = (1…7).map{|i| Array.new(3) {|j| i[j]}.reverse! }
rowcounter = [0,0,0]

# deletes all rows from cache that lead to invalid solutions

0.upto(8) do |column|
$thegrid[column] = cache[ rand(cache.length) ].clone # number of values uses so far per row rowcounter = rowcounter.zip($thegrid[column]).map!{|i,j| i+j}

# test constraints and delete invalid columns from later selection
0.upto(2) do |count|
cache.delete_if {|x| x[count] == 1} if rowcounter[count] == 5
cache.delete_if {|x| x[count] == 0} if 8 - column == 5 -


rowcounter[count]
end

total = rowcounter.inject{|sum, n| sum + n}
cache.delete_if {|x| total + x.inject{|sum, n| sum + n} > 8 +


column }
end
end

# fills the grid with random values, increasing order per column

def fill_grid
$thegrid.each_with_index do |line, i| start = (i==0) ? 1 : i*10 stop = (i==8) ? 90 : ((i+1)*10 - 1) count = line.inject {|sum, n| sum + n } line.each_with_index do |n, j| if n > 0 then$thegrid[i][j] = rand(stop - start - count + 2) + start
start = $thegrid[i][j] + 1 #increasing numbers count -= 1 end end  end end create_grid fill_grid # pretty print the grid sep = “±—”*9 + “+\n” puts$thegrid.transpose.inject(sep) {|str, e|
str += sprintf("| %2d "*9 + “|\n” + sep, *e).gsub(/ 0/, " ")
}

My solution to the quiz. Each of 18 rows is built individually, by
randomly choosing 5 out of the 9 bins to pull a number from. However
the bins are semi-ordered, so that the most filled bins are always
favored in the selection.

All the rows then get shuffled and divided into 6 tickets. Finally each
ticket checks that its columns satisfy the ordering constraint, if not,
the numbers in the column are rearranged while maintaining 5 numbers in
each row.

########

class TicketGenerator
def init_bins
# Create and fill the 9 bins of numbers, corresponding to
# the allowed numbers for each column.
@bins = Array.new
# 1 through 9
@bins << (1…9).sort_by{ rand }
# 10 through 19, 20 through 29, etc.
10.step(70, 10) do |x|
@bins << (x…x+9).sort_by{ rand }
end
# 80 through 90
@bins << (80…90).sort_by{ rand }
end

def retrieve_row
# Create a row by pulling one number from each of five non-empty
bins.
row = Array.new(9, nil)
# Randomize which bins to choose from, but then favor the most
filled bins –
# so we don’t end up with less than 5 non-empty bins with still more
rows to create.
bin_index_array = (re[email protected]).sort_by{ rand }.sort_by{ |b|
@bins[b].length }
5.times do
bin_index = bin_index_array.pop
row[bin_index] = @bins[bin_index].pop
end
row
end

def print_book
# Generate 18 rows, shuffle them, and print six tickets.
init_bins
all_rows = Array.new(18){ retrieve_row }.sort_by{ rand }
0.step(15, 3) do |x|
ticket = Ticket.new(all_rows[x…x+3])
ticket.print_ticket
puts “\n”
end
end

private :init_bins, :retrieve_row
public :print_book
end

class Ticket
def initialize(rows)
# A ticket consists of an array of three rows,
# with 5 numbers and 4 nil entries per row.
@rows = rows
validate_ticket
end

def validate_ticket
# Convert three rows of 9 numbers into 9 columns of three numbers,
# check that each column satisfies the ascending order constraint,
# and then convert back into rows.
columns = Array.new(9) { [] }
columns.each { |c| @rows.each { |r| c << r.shift }; rectify© }
@rows.each { |r| columns.each { |c| r << c.shift } }
end

def rectify(column)
# If there are 2 or 3 numbers in a column, they must
# appear in increasing order downward. If they don’t, then
# swap the numbers around while maintaining 5 numbers
# in each row.
case column.nitems
when 0…1 then column # do nothing
when 2
nil_index = column.index(nil)
non_nils = [0,1,2] - [nil_index]
first_nn, last_nn = non_nils.first, non_nils.last
# Swap the two non-nil elements
if column[first_nn] > column[last_nn]
column[first_nn], column[last_nn] = column[last_nn],
column[first_nn]
end
when 3 then column.sort! # just sort the three numbers
end
end

def print_ticket
puts “±—” * 9 + “+”
@rows.each do |row|
line = row.inject("|") do |str, x|
if not x
str + " |"
elsif x < 10
str + " #{x} |"
else
str + " #{x} |"
end
end
puts line
puts “±—” * 9 + “+”
end
end

private :validate_ticket, :rectify
public :print_ticket
end

TicketGenerator.new.print_book

On Feb 18, 2007, at 20:19 , Andy Restrepo wrote:

My solution to the quiz. Each of 18 rows is built individually, by
randomly choosing 5 out of the 9 bins to pull a number from.
However the bins are semi-ordered, so that the most filled bins are
always favored in the selection.

All the rows then get shuffled and divided into 6 tickets. Finally
each ticket checks that its columns satisfy the ordering
constraint, if not, the numbers in the column are rearranged while
maintaining 5 numbers in each row.

Nice. A whole lot more straightforward that my solution.

/Christoffer

Does your solution make sure there is at least one number in each
column of the ticket?

Does your solution make sure there are exactly five numbers on each
row?

On Feb 18, 2007, at 23:45 , Brock Lee wrote:

Does your solution make sure there are exactly five numbers on each
row?

Ooops, was that I requirement? Kind of missed that.

Oops. Missed out the requirement that each column should be filled.

/Christoffer

On Feb 18, 2007, at 18:33 , Christoffer Lernö wrote:

Quick and dirty hack that fixes the problem of possibly empty columns
with my solution: if a ticket with an empty column is detected, just
start over again.

########

class TicketGenerator
def init_bins
# Create and fill the 9 bins of numbers, corresponding to
# the allowed numbers for each column.
@bins = Array.new
# 1 through 9
@bins << (1…9).sort_by{ rand }
# 10 through 19, 20 through 29, etc.
10.step(70, 10) do |x|
@bins << (x…x+9).sort_by{ rand }
end
# 80 through 90
@bins << (80…90).sort_by{ rand }
end

def retrieve_row
# Create a row by pulling one number from each of five non-empty
bins.
row = Array.new(9, nil)
# Randomize which bins to choose from, but favor the most filled
bins –
# so we don’t end up with less than 5 non-empty bins with still more
rows to create.
bin_index_array = (re[email protected]).sort_by{ rand }.sort_by{ |b|
@bins[b].length }
5.times do
bin_index = bin_index_array.pop
row[bin_index] = @bins[bin_index].pop
end
row
end

def build_book
# Generate 18 rows and divide them between six tickets
init_bins
all_rows = Array.new(18){ retrieve_row }
tickets = Array.new
0.step(15, 3) do |x|
ticket = Ticket.new(all_rows[x…x+3].sort_by { rand })
tickets.push(ticket)
# If an invalid ticket is found, indicate failure
# by setting the return value to false.
if not ticket.is_valid?
tickets = false; break
end
end
tickets
end

def print_book
# Keep generating ticket books until a valid
# one is returned. Then, print out the tickets.
book = build_book until book
book.each { |t| t.print_ticket; puts “\n”}
end

private :init_bins, :retrieve_row, :build_book
public :print_book
end

class Ticket
def initialize(rows)
# A ticket consists of an array of three rows,
# with 5 numbers and 4 nil entries per row.
@rows = rows
@empty_column = false
validate_ticket
end

def is_valid?
not @empty_column
end

def validate_ticket
# Convert three rows of 9 numbers into 9 columns of three numbers,
# check that each column satisfies the ascending order constraint,
# and then convert back into rows.
columns = Array.new(9) { [] }
columns.each { |c| @rows.each { |r| c << r.shift }; rectify© }
@rows.each { |r| columns.each { |c| r << c.shift } }
end

def rectify(column)
# If there are 2 or 3 numbers in a column, they must
# appear in increasing order downward. If they don’t, then
# swap the numbers around while maintaining 5 numbers
# in each row.
case column.nitems
when 0 then @empty_column = true
when 1 then column # do nothing
when 2
nil_index = column.index(nil)
non_nils = [0,1,2] - [nil_index]
first_nn, last_nn = non_nils.first, non_nils.last
# Swap the two non-nil elements
if column[first_nn] > column[last_nn]
column[first_nn], column[last_nn] = column[last_nn],
column[first_nn]
end
when 3 then column.sort! # just sort the three numbers
end
end

def print_ticket
puts “±—” * 9 + “+”
@rows.each do |row|
line = row.inject("|") do |str, x|
if not x
str + " |"
elsif x < 10
str + " #{x} |"
else
str + " #{x} |"
end
end
puts line
puts “±—” * 9 + “+”
end
end

private :validate_ticket, :rectify
public :print_ticket, :is_valid?
end

TicketGenerator.new.print_book

Not very elegant, but it’s a minimal fix to my original solution so
that each ticket has at least a single value in each column.

/C

class Housie

def initialize
@colset = Array.new(9) { [] }
@numbers = 0
end

# If this number can’t fit with the numbers already in this

housie, we return

# one of the old numbers in the housie that we removed to make

this number fit.

def push(number)
raise “Tried to push to generated housie ticket” if @housie
column = number == 90 ? 8 : number / 10
@colset[column] << number
if @colset[column].size == 4
@colset[column].shift
elsif @numbers == 15
random_col = rand(9) while random_col.nil? || @colset
[random_col].size < 2
@colset[random_col].shift
else
@numbers += 1
nil
end
end

know we

# can create a ticket, but we want a randomized look to it.

def generate
raise “Not enough data to generate ticket” unless complete?
@housie = Array.new(3) { Array.new(9) }
(0…8).sort_by { rand }.each do |column|
@colset[column].size.times do
rows = @housie.sort_by { rand }.sort { |row1, row2|
row1.compact.size <=> row2.compact.size }
rows.shift until rows.first[column].nil?
rows.first[column] = true
end
end
9.times do |column|
@colset[column].sort!
@housie.each { |row| row[column] = @colset[column].shift if row
[column] }
end
self
end

# Ugly code to display a ticket.

def to_s
return “Not valid” unless @housie
@housie.inject("") do |sum, row|
sum + “±—” * 9 + “+\n” +
row.inject("|") { | sum, entry | sum + " #{"%2s" % entry} |" }

• “\n”
end +
“±—” * 9 + “+”
end

def complete?
@numbers == 15
end

def Housie.new_book
housies = Array.new(6) { Housie.new }
numbers = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } }
numbers[0].delete 0
numbers[8] << 90

# First make sure every book has at least one entry

numbers.each do |col|
col.replace col.sort_by { rand }
housies.each { |housie| housie.push(col.shift) }
end

# That done, distribute the rest of the numbers

numbers.flatten!
while numbers.size > 0 do
pushed_out = housies[rand(6)].push(numbers.shift)
numbers << pushed_out if pushed_out
end
housies.collect { |housie| housie.generate }
end

def Housie.new_ticket
housie = Housie.new
numbers = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } }
numbers[0].delete 0
numbers[8] << 90

# First make sure this ticket has at least one entry

numbers.each do |col|
col.replace col.sort_by { rand }
housie.push(col.shift)
end

# Distribute the rest of the numbers

numbers = numbers.flatten!.sort_by { rand }
until housie.complete?
returned = housie.push numbers.shift
numbers << returned if returned
end
housie.generate
end

end

puts “A book of tickets:”
Housie.new_book.each_with_index { |housie, index| puts “Ticket #
{index + 1}”; puts housie.to_s }

puts “A single ticket:”
puts Housie.new_ticket.to_s

Well this is my first attempt at solving one of these quizzes. Please
be gentle, especially with the comments I think.

This solution uese Ranges extensivley and relies on a method
choose_uniq_members on any given range. This will randomly select the
specified number of entries from the range.

The output grid is constructed by first selecting which columns will
be filled, ie 5 columns per row, and 3 rows. This is then used as a
specification for each column which tells the choose_uniq_members
method on the column range how many, 0 to 3, members of the range to
select. It’s then collected up into the @rows variable and displayed.

class Range

# Choose the specified number of random elements of the range

def choose_uniq_members( num = 1 )
# Make sure the range is large enough to select correct number of
uniq members
raise “RangeBoundaryError” if self.size < num
return self.to_a if self.size == num

# Select the specified number of random entries from the range
tmp = self.dup.to_a
selected = []
num.times {  selected << tmp.delete_at( rand( tmp.size )  ) }
selected.sort


end

def size
@size ||= self.to_a.size
end

end

class HousieTicket

COLUMNS = [ 1…9, 10…19,
20…29,30…39,40…49,50…59,60…69,70…79,80…90]

def initialize

# an array of arrays for rows and columns for the final data

@rows = Array.new(3){ Array.new(9) }

# Maps out in a 3 x 5 array, which of the final @rows indicies

should contain numbers
row_map = (1…3).inject([]){ |arr, i| arr <<
(0…COLUMNS.size).choose_uniq_members(5) }

# Maps the indicies of row_map into column counts so that each

column may be populated.

relevant range.

# ie column 0 = 2, therefore two numbers from the range 1…9 should

be selected
the_map = row_map.flatten.inject( Hash.new(0) ){ |col_map, i|
col_map[i] += 1; col_map }

# Populate the final @rows array with the real numbers based on the

prototype matrix developed

# in row_map by choosing the number of uniq values from the columns

range as specified in the_map
(0…9).each do | col_index |
numbers = COLUMNS[col_index].choose_uniq_members(
the_map[col_index] ).reverse
(0…3).each do | row_index |
@rows[ row_index ][ col_index ] = numbers.pop if row_map[
row_index ].include?( col_index )
end
end
end

# Various display methods to print out the ticket to the terminal

def display
array = stringify_rows
print_line_seperator
array.each do |row|
puts “|” << row.join( “|” ) << “|”
print_line_seperator
end
end

def stringify_rows
rows = @rows.dup
rows.map do |row|
row.map{ |e| if(e) then sprintf(" %02d ", e) else " " end }
end
end

def print_line_seperator
puts “|” << “----|” * 9
end

end

# Runs the program from the terminal

number_of_tickets = ARGV[0]

unless number_of_tickets.to_i > 0
puts “How many tickets would you like to generate?\n”
until number_of_tickets.to_i > 0
number_of_tickets = gets.chomp
end
end

1.upto(number_of_tickets.to_i ) do |n|
ticket = HousieTicket.new
puts “\n\n”
puts “Ticket #{n}”
ticket.display
end

Here is a different solution. This first populates each ticket with
at least 1 entry. After that it treats the tickets as 18 rows and
populates it with the “max 5 in a row”-constraint. To avoid getting
stuck, it will swap out a random number if there already are 5
numbers in the row. This could cause a ticket to lose its minimum of
1 entry per column, so the initial entries in every ticket column are
prevented from being swapped out.
up to this point.

class Housie

def initialize(housie_array)
@housie_array = housie_array
raise “Illegal size” unless @housie_array.size == 3
@housie_array.each { |row| raise “Illegal row in housie #
{row.inspect}” unless row.compact.size == 5 }
9.times do |col|
raise “Illegal column #{col}” unless @housie_array.collect { |
row| row[col] }.compact.size > 0
end
end

# Ugly code to display a ticket.

def to_s
@housie_array.inject("") do |sum, row|
sum + “±—” * 9 + “+\n” +
row.inject("|") { | sum, entry | sum + " #{"%2s" % entry} |" }

• “\n”
end +
“±—” * 9 + “+”
end

def Housie.new_book
housies = Array.new(6) { Array.new(3) { Array.new(9) } }
columns = Array.new(9) { |col| Array.new(10, col) }
columns[0].shift
columns[8] << 8

# These entires are fixed and can’t be swapped out.

columns.each do |col|
housies.each do |housie|
housie.select { |row| row.compact.size < 5 }.sort_by
{ rand }.first[col.shift] = :fixed
end
end

# Merge all rows

all_rows = []
housies.each { |housie| housie.each { |row| all_rows << row } }

# Fill all rows, start with the one with fewest entries, resolve

ties randomly
while (columns.flatten.compact.size > 0) do
columns.select { |col| col.size > 0 }.each do |col|
all_rows.reject { |row| row[col.first] }.sort_by
{ rand }.each do |row|
break unless col.first
# A full row needs to have a value swapped out
if row.compact.size == 5
# Only try to swap if we have swappable entries
if row.member? :selected
removed_col = rand(9) while removed_col.nil? || row
[removed_col] != :selected;
row[removed_col] = nil
columns[removed_col] << removed_col
row[col.shift] = :selected
end
else
row[col.shift] = :selected
end
end
end
end

 # Populate actual numbers
values = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } }
values[0].shift # remove 0
values[8] << 90 # add 90

values.each_with_index do |col, index|
col = col.sort_by { rand }
housies.each do |housie|
entries = housie.inject(0) { |sum, row| sum + (row[index] ?


1 : 0) }
values = col.slice!(0…entries).sort
housie.each { |row| row[index] = values.shift if row[index] }
end
end

 housies.collect { |housie| Housie.new(housie) }


end

end

Ruby Q. [email protected] writes:

by Brian C.

A version of Bingo played in the UK and some other countries is called “Housie”.
Players buy “books” of 6 tickets. Each ticket shows exactly 15 numbers, and in
each book every number from 1 to 90 is used exactly once.

1. Write a Ruby program which generates random individual tickets
or
2. Write a Ruby program which generates random complete books of tickets

When I first read the description, I thought “I already did that”.
And in fact, I did. Back in 2002, after only a few weeks using Ruby.

Have a look at the timestamp:
-rw-r–r-- 1 chris chris 1472 Jan 13 2002 bingo.rb
(Incidentally, that’s my sisters birthday and I remember the guests
liked it.)

Anyway, my bingo solution from 2002 generates plain TeX output
suitable for printing. The macro package is appended.
You’d call it like ruby bingo.rb > entries.tex && pdftex bingo.tex.

Remember that this code has been untouched for 5 years, I wouldn’t
necessarily code it that way today.

#!/usr/bin/env ruby

# -- ruby --

Num = 14

class Bingo
def initialize
@width = 9
@height = 3
@field = [[0,0,0],[0,0,0],[0,0,0],
[0,0,0],[0,0,0],[0,0,0],
[0,0,0],[0,0,0],[0,0,0]]
end

def insert_numbers
0.upto (@width-1) { |x|
arr = ((x10)…((x10)+10)-1).to_a
# Special cases: don’t insert a 0, add 90 to the row with 80
arr.delete(0)
if arr.index(89) != nil
arr = arr + [90]
end

  0.upto (@height-1) { |y|


r = arr[rand (arr.length)]
arr.delete(r)
@field[x][y] = r
}
@field[x].sort!
}
end

def remove_some
0.upto(@height-1) { |x|
cnt = 0
while cnt < 4
cnt+=1
r = rand @field.length

# The following crap eludes three in a row’

if @field[r][x] != nil &&
!((@field[r][0] == nil && @field[r][1] == nil) ||
(@field[r][1] == nil && @field[r][2] == nil) ||
(@field[r][2] == nil && @field[r][0] == nil))
@field[r][x] = nil
else
cnt-=1
end
end
0.upto (@width-1) { |y|
}
}
puts
end

def dump
0.upto(@height-1) { |x|
0.upto(@width-1) { |y|
value = @field[y][x]
if (0…9).to_a.index(value) != nil
value = ‘?’ + value.to_s
end
if value == nil
value = ‘\X’
end
print "&& ", value, " "
}
if x != @height-1
print “&\nl\n”
else
print “&\newsheet\n”
end
}
end
end

Num.times {
b = Bingo.new
b.insert_numbers
b.remove_some
b.dump
}

% Print bingo’’ sheets.

\font\mainfont=cmbx14
\mainfont

\newbox\strutbox
\setbox\strutbox=\hbox{\vrule height18.5pt depth13.5pt width0pt}
\def\strut{\relax\ifmmode\copy\strutbox\else\unhcopy\strutbox\fi}

\newdimen\onedigitwidth
\newdimen\digitwidth
\setbox0=\hbox{\mainfont0}
\onedigitwidth=\wd0
\setbox0=\hbox{\mainfont00}
\digitwidth=\wd0

\catcode?=\active
\def?{\hbox to \onedigitwidth{}}
\def\X{\hbox to \digitwidth{\hfil$\bigcirc$\hfil}}

\begingroup

\tabskip=0pt
\offinterlineskip
\def\nl{\cr\noalign{\hrule}}
\def\newsheet{\cr\noalign{\hrule\vskip1cm\hrule}}
\halign{\strut#& \vrule#\tabskip=0.50em&
\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil&
\vrule#\tabskip=0pt\nl
\input entries.tex
\cr}

\endgroup

\bye

Enjoy,

James G. wrote:

There are two levels of quiz difficulty to choose from. Given the above
rules
for the validity of tickets and books, then:

1. Write a Ruby program which generates random individual tickets
or
2. Write a Ruby program which generates random complete books of
tickets

Yay, I finally got time for this, my first try to submit one. It might
be a little tricky, but it does what it has to

#First of all, let’s look at the books.
#Assuming a symetrical distribution of tens, we have that for all nine
rows,
#tickets can have one of the following distributions of numbers in a
columnn:
def make_poss
[ [1, 1, 1, 2, 2, 2, 2, 2, 2],
[1, 1, 1, 1, 2, 2, 2, 2, 3],
[1, 1, 1, 1, 1, 2, 2, 3, 3],
[1, 1, 1, 1, 1, 1, 3, 3, 3] ]
end

#Don’t forget to put the numbers in the bag!
def make_container
initial = (0…8).to_a.collect{|n| ((10n)…(10(n+1) - 1)).to_a }
initial[0].delete(0); initial[-1].push(90)
initial
end

class Array
#Tricked so it adds only the non-nil elements
def sum
inject(0) {|sum, n| n.nil? ? sum : sum + n }
end

def column(n)
collect{|row| row[n]}
end
end

class Book < Array

attr_accessor :tickets, :distribution

def initialize
#Lets’s the fun begin. As stated before, a ticket can have on of 4
possible
#distribution of tickets (and they are ALL the possibilities).
#So, we start defining randomly the distributions of our tickets.
#Furthermore, we scramble the possibilities, so any row can have any
distribution provided.
super(Array.new(6).collect{|i| (poss =
make_poss)[rand(poss.size)].sort_by{rand} })

#Now we have to distribute our matrix. Because of the above, each


row sums 15, but we have to make
#each column sum 10.
make_distribution

#Now we adjust the numbers on each ten.
balance
@tickets = []

make_tickets


end

#This method iterates each column, and accomodate the numbers until
the sum of each column is 10.
def make_distribution
for i in 0…9
s = column(i).sum
remaining = (10 - s).abs
if s != 10
#If the sum is different than 10, decrement one to the greater
#and increment it to the possible in the row, or viceversa.
#If that’s not possible, go onto the next row, and repeat if
necessary.
remaining.times do
index = 0
until gain(index, i, (s < 10 ? 1 : -1))
index += 1
index = 0 if index == 5
end
end
end
end
end

def display
@tickets.each {|ticket| ticket.display}
end

#Knowing the distribution of the tickets, they are done almost
automatically.
def make_tickets
container = make_container
each{ |row| @tickets << Ticket.new(row, container) }
end

#Returns the index where the increment occured, or nil if cannot be
done
def gain(row, column, num = 1)
item = self[row][column]

#We know a priori that the numbers must be between 1 and 3
return nil if (item == 3 && num == 1) or (item == 1 && num == -1)

#iterate over the array, starting from the right of the column
for i in (column + 1)...(self[row].size)

#Find the first element that can accept a loss of -num (or a gain)
if (1..3) === (self[row][i] - num)
#if so, increment and decrement the numbers.
self[row][column] += num
self[row][i] -= num
return i
end
end
return nil


end

#Balances the ticket distribution so the first row has 9 numbers and
#the last one 11, without affecting the sum.
def balance
for row in self
if row[0] > 1 and row[-1] < 3
row[0] -= 1
row[-1] += 1
break
end
end
end

end

class Ticket < Array

def initialize(distribution = (poss = make_poss)[rand(poss.size)],
container = make_container)
#When initializing, we first make the ticket ‘vertical’ so its
easier to keep track of the
#numbers in each row.
super(9); collect! {|row| []}
distribution.each_with_index do |distr, index|
choose = container[index]
distr.times do
#Exhausting possibilities
self[index] << choose.slice!(rand(choose.size))
end
end
collect! { |row| row.sort! }
make_format
end

def make_format
#Iterate over the colums
for i in 0…3
#Do this until we have 5 elements per column.
until (s = column(i).compact.length) == 5
#If the number of elements in the column is more than 5,
#move one randomly to the next place
if s > 5
x = rand(9)
self[x].insert(i, nil) unless self[x].length == 3
else
#If the number is less than four (that can only happen in the
second column),
#remove one nil
for row in self
if row[1] == nil and row[2] != nil
row[1], row[2] = row[2], nil
break
end
end
end
end
end
#Now we just transpose the ticket.
replace((0…3).collect{ |i| column(i) })
end

def display
print(top = “±—” * 9 + “+\n”)
each do |row|
row.each{ |number| print("|" + " " * (3 - number.to_s.length) +
number.to_s + " ") }
print “|\n”, top
end
puts
end

end

puts “Type B for a complete book, or T for a single ticket.\nType
anything else to exit”
while (option = gets.chomp) =~ /\A[BbTt]/
if option =~ /\A[Bb]/
#Now all we have to do is to create a new book…
book = Book.new
#and display it…
puts “BINGO!\n”
book.display
else
#Or we can make single tickets… for cheating… you know
puts “Today’s my lucky day”
x = Ticket.new
x.display
end
puts “Play again?”
end

On 16 Feb., 17:47, Ruby Q. [email protected] wrote:

each book every number from 1 to 90 is used exactly once.
±—±—±—±—±—±—±—±—±—+
1. Write a Ruby program which generates random individual tickets
or
2. Write a Ruby program which generates random complete books of tickets

I wanted to participate to a ruby quiz again - took a 40 quizzes
break.
But I can’t get a perfect algo for creating a Book.

This is probably a spoiler, maybe not

One Idea was to create each ticket, by building 2 rows and complete
the last row:
if both elements of the column were nil, mark the third element as
“to be filled”
and so on.

But by doing this, I would actually change the probabilities,
because the last row depends on the first two rows.

So far the only perfect “algo” that came to my mind was to create
all possible books and chose one randomly.
By this method the chances are perfectly balanged.
I mean we’re talking about BINGO!
It’s about money… and you should be able to proof that your algo
generates all possible books at equal probability.

Am I right with that, or is this totally nonsense?
Either way, please feedback to me :>

On Wed, Feb 21, 2007 at 07:50:09PM +0900, [email protected] wrote: > So far the only perfect "algo" that came to my mind was to create > all possible books and chose one randomly.

Directly enumerating all possible patterns for an individual ticket is
certainly doable. There are 735,210.

This means that the simple set of ‘all possible books’ is enormous, but
there may be some way to fold it to a manageable size. I look forward
with
interest to seeing the solutions in this area