Andy Restrepo
2/18/2007 7:20:00 PM
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 = (0...@bins.length).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(c) }
@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