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
# Returns a row pattern for one row of a ticket. It will be an array
# containing five trues and four falses. Each true corresponds to a
# number placement and each false a blank. The positions of the true
# values is random, but weighted by the odds that a number will appear
# in each column. The first column has the lowest odds (9/18, or 1/2,
# or 50%), the last column the greatest odds (11/18, or 61.1%), and
# 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
# Returns true if a ticket pattern (an array of three row patterns) is
# valid. A ticket pattern is valid if every column has at least one
# 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
# Returns true only if the book pattern is valid. A book pattern is
# valid if the numbers in each column either have the correct amount
# (if the book has *all* the ticket patterns) or has the potential to
# have the correct amount (if the book pattern has only a subset of
# 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
# each of the tickets left to fill in the booklet can have from 1 to
3
# numbers, so make sure that that will allow us to fill each column
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
# Generate a book pattern recursively by adding one ticket pattern
# after another. If adding a given ticket pattern makes it so the
# book pattern is invalid, back up and add a different ticket pattern
# 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
# Returns 9 number "feeders", one per column, for an entire book.
# The numbers in each feeder are appropriate for the column in which
# 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
# Generate a book, which is an array of 6 tickets, where each ticket
# is an array of three rows, where each row is an array containing
# 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
# If run from the command-line, produce the output for one book.
if __FILE__ == $0
puts book_to_s(gen_book)
end