R
Ruby Quiz
Eric I. said it best in a note attached to his solution:
I really enjoyed this quiz. On the surface it seems relatively simple.
But there are some important subtleties.
This is the realization I came to as well. When Brian first suggested the quiz,
we discussed the possible solutions. When I say discussed, I mean that Brian
generated a nearly endless stream of excellent ideas while I watched it all
happen. The more he generated, the more I realized how much I liked the
problem. It's quite rich.
There are many ways to approach this quiz. Brian's own solution generates bit
map patterns representing blanks and non-blanks in a ticket, then uses those
patterns to construct books filling in numbers as it works. Eric I. used a
backtracking search, verifying that a solution is still possible as each ticket
is added. Below I will examine a slightly simpler solution, that still produces
pretty good results.
Andy Restrepo's code is a random generation scheme. It builds random books from
random tickets made out of random rows. If the book doesn't end up being valid,
it just tries again. However, it arranges the random generation such that rows
are correct more often than you might expect.
Let's jump into the code to see how it does that. The process begins with this
trivial call:
TicketGenerator.new.print_book
That's Ruby's default new() and TicketGenerator doesn't define an initialize()
method, so let's skip to print_book():
class TicketGenerator
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
end
This is the process I explained earlier. An attempt is made to build a book.
If we get one, we're done. Otherwise we try again. When we have them all, the
tickets in the book are printed.
Let's dig deeper into book creation:
class TicketGenerator
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
end
The first two lines here make use of other methods in the class to create a set
of 18 rows. We will get to those methods in a moment, but take it on faith for
now.
The rest of the method walks those rows in threes, making Ticket objects out of
them. Each time a Ticket is made, the code ensures it is valid or bails out. We
haven't seen this class yet either, but it shouldn't too hard to guess what the
is_valid?() method does.
Here are the row making methods (with one minor edit by me):
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 = ([email protected]).sort_by{ |b|
[@bins.length, rand]
}
5.times do
bin_index = bin_index_array.pop
row[bin_index] = @bins[bin_index].pop
end
row
end
end
First, init_bins() fills an Array with Arrays of randomized numbers for each
column. These columns span six tickets and are used to build the entire book.
Now, retrieve_row() is used to create the 18 rows the code eventually builds
books out of. It works by creating an empty row, choosing five of the column
bins, and adding a random number to the row from each bin. The selection of
bins is not-quite-random and that turns out to be the best and worst feature of
this solution.
Bins are sorted first by length and then in random order before a pick is made
from the end. This means that a selection will always be made from a bin with
the most members remaining. That bin is selected randomly from those with the
same number of members remaining, but that doesn't mean the choice is random.
Think of it this way, the bins don't even start with the same number of members.
The eighth bin has eleven and will always sort to be chosen first. Likewise,
the zeroth bin always sorts first and thus cannot be selected by this algorithm
during the creation of the first row. Even after the first row is created the
eighth bin will still be tied for most entries and thus it will always come up
again in the second row. That means the first ticket produced by this solution
will always have two or three numbers in the final column. Never just one.
The downside of all of this is that the tickets aren't completely random.
There's a pattern to them and you can find it if you look for it. Given that,
these books would be fine for casual play, but probably not for games where
money is on the line.
The upside is speed. Even though tickets are randomly generated, the sorting
keeps valid combination extremely likely. In a set of ten sample runs I
conducted the code only called build_book() a maximum of two times per run and
it only needed one call eight out of ten times. A truly random pattern would
need a lot more attempts to find a workable solution. You can simulate this
scenario by removing the bin length sort condition from Andy's code. It still
finds answers, but it can take some time.
The last bit of TicketGenerator code sets method visibility:
class TicketGenerator
private :init_bins, :retrieve_row, :build_book
public
rint_book
end
The other piece of this puzzle is the Ticket class, so we will look at that now.
Tickets are just three rows that know how to validate and draw themselves. The
initialization process for a Ticket is spread over three methods, so let's begin
with those:
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 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 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
end
You can see that initialize() just stores the rows and kicks off
validate_ticket(). That method does a bit of a dance to rearrange the rows into
columns, clean and validate those columns, and change them back.
Array#transpose() probably would have simplified this process a bit.
The real work happens in rectify(). This method serves two purposes. Its main
job is to reorder the numbers in a column to ensure they count down. As it
works though, it watches for empty columns that would invalidate the Ticket.
Once we know whether or not a Ticket is valid, we need to provide easy access to
that information:
class Ticket
def is_valid?
not @empty_column
end
end
That's the method we saw TicketGenerator using to determine when a book build
needed to be restarted.
Tickets can also print themselves:
class Ticket
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
end
That code just walks the rows, printing fields as it goes. The if chain in the
middle could be simplified a bit to:
str + " %2s |" % x
Finally, the code again sets the visibility for these methods:
class Ticket
private :validate_ticket, :rectify
publicrint_ticket, :is_valid?
end
My thanks to all the book builders. I didn't expect to see so many varied
approaches.
Tomorrow, I will put you to work solving a long-standing Ruby Quiz issue...
I really enjoyed this quiz. On the surface it seems relatively simple.
But there are some important subtleties.
This is the realization I came to as well. When Brian first suggested the quiz,
we discussed the possible solutions. When I say discussed, I mean that Brian
generated a nearly endless stream of excellent ideas while I watched it all
happen. The more he generated, the more I realized how much I liked the
problem. It's quite rich.
There are many ways to approach this quiz. Brian's own solution generates bit
map patterns representing blanks and non-blanks in a ticket, then uses those
patterns to construct books filling in numbers as it works. Eric I. used a
backtracking search, verifying that a solution is still possible as each ticket
is added. Below I will examine a slightly simpler solution, that still produces
pretty good results.
Andy Restrepo's code is a random generation scheme. It builds random books from
random tickets made out of random rows. If the book doesn't end up being valid,
it just tries again. However, it arranges the random generation such that rows
are correct more often than you might expect.
Let's jump into the code to see how it does that. The process begins with this
trivial call:
TicketGenerator.new.print_book
That's Ruby's default new() and TicketGenerator doesn't define an initialize()
method, so let's skip to print_book():
class TicketGenerator
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
end
This is the process I explained earlier. An attempt is made to build a book.
If we get one, we're done. Otherwise we try again. When we have them all, the
tickets in the book are printed.
Let's dig deeper into book creation:
class TicketGenerator
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
end
The first two lines here make use of other methods in the class to create a set
of 18 rows. We will get to those methods in a moment, but take it on faith for
now.
The rest of the method walks those rows in threes, making Ticket objects out of
them. Each time a Ticket is made, the code ensures it is valid or bails out. We
haven't seen this class yet either, but it shouldn't too hard to guess what the
is_valid?() method does.
Here are the row making methods (with one minor edit by me):
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 = ([email protected]).sort_by{ |b|
[@bins.length, rand]
}
5.times do
bin_index = bin_index_array.pop
row[bin_index] = @bins[bin_index].pop
end
row
end
end
First, init_bins() fills an Array with Arrays of randomized numbers for each
column. These columns span six tickets and are used to build the entire book.
Now, retrieve_row() is used to create the 18 rows the code eventually builds
books out of. It works by creating an empty row, choosing five of the column
bins, and adding a random number to the row from each bin. The selection of
bins is not-quite-random and that turns out to be the best and worst feature of
this solution.
Bins are sorted first by length and then in random order before a pick is made
from the end. This means that a selection will always be made from a bin with
the most members remaining. That bin is selected randomly from those with the
same number of members remaining, but that doesn't mean the choice is random.
Think of it this way, the bins don't even start with the same number of members.
The eighth bin has eleven and will always sort to be chosen first. Likewise,
the zeroth bin always sorts first and thus cannot be selected by this algorithm
during the creation of the first row. Even after the first row is created the
eighth bin will still be tied for most entries and thus it will always come up
again in the second row. That means the first ticket produced by this solution
will always have two or three numbers in the final column. Never just one.
The downside of all of this is that the tickets aren't completely random.
There's a pattern to them and you can find it if you look for it. Given that,
these books would be fine for casual play, but probably not for games where
money is on the line.
The upside is speed. Even though tickets are randomly generated, the sorting
keeps valid combination extremely likely. In a set of ten sample runs I
conducted the code only called build_book() a maximum of two times per run and
it only needed one call eight out of ten times. A truly random pattern would
need a lot more attempts to find a workable solution. You can simulate this
scenario by removing the bin length sort condition from Andy's code. It still
finds answers, but it can take some time.
The last bit of TicketGenerator code sets method visibility:
class TicketGenerator
private :init_bins, :retrieve_row, :build_book
public
rint_bookend
The other piece of this puzzle is the Ticket class, so we will look at that now.
Tickets are just three rows that know how to validate and draw themselves. The
initialization process for a Ticket is spread over three methods, so let's begin
with those:
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 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 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
end
You can see that initialize() just stores the rows and kicks off
validate_ticket(). That method does a bit of a dance to rearrange the rows into
columns, clean and validate those columns, and change them back.
Array#transpose() probably would have simplified this process a bit.
The real work happens in rectify(). This method serves two purposes. Its main
job is to reorder the numbers in a column to ensure they count down. As it
works though, it watches for empty columns that would invalidate the Ticket.
Once we know whether or not a Ticket is valid, we need to provide easy access to
that information:
class Ticket
def is_valid?
not @empty_column
end
end
That's the method we saw TicketGenerator using to determine when a book build
needed to be restarted.
Tickets can also print themselves:
class Ticket
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
end
That code just walks the rows, printing fields as it goes. The if chain in the
middle could be simplified a bit to:
str + " %2s |" % x
Finally, the code again sets the visibility for these methods:
class Ticket
private :validate_ticket, :rectify
public
rint_ticket, :is_valid?end
My thanks to all the book builders. I didn't expect to see so many varied
approaches.
Tomorrow, I will put you to work solving a long-standing Ruby Quiz issue...