# Housie (#114)

**URL:** <https://www.ruby-forum.com/t/housie-114/86489>\
**Category:** Ruby\
**Created:** [February 22, 2007, 6:04pm UTC](https://www.ruby-forum.com/t/housie-114/86489 "2007-02-22T18:04:20Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 22, 2007, 6:04pm UTC](https://www.ruby-forum.com/t/housie-114/86489/1 "2007-02-22T18:04:20Z")

</div>

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 = (removed\_email\_address@domain.invalid).sort\_by{ |b|  
[@bins[b].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 :print\_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© }  
@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 :print\_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 Q.  
issue…