Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] Housie (#114)

Reply
Thread Tools

[QUIZ] Housie (#114)

 
 
Ruby Quiz
Guest
Posts: n/a
 
      02-16-2007
The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

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

by Brian Candler

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

 
Reply With Quote
 
 
 
 
Eric I.
Guest
Posts: n/a
 
      02-16-2007
On Feb 16, 11:47 am, Ruby Quiz <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
James Edward Gray II
Guest
Posts: n/a
 
      02-16-2007
On Feb 16, 2007, at 2:10 PM, Eric I. wrote:

> On Feb 16, 11:47 am, Ruby Quiz <(E-Mail Removed)> 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?


That's the scoop according to Wikipedia:

http://en.wikipedia.org/wiki/Housie

James Edward Gray II

 
Reply With Quote
 
Eric I.
Guest
Posts: n/a
 
      02-18-2007
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

 
Reply With Quote
 
Christoffer Lernö
Guest
Posts: n/a
 
      02-18-2007
My solution drops the numbers 1-90 into the tickets at random. If
there are more than 3 numbers of the same column for a ticket, or it
already has 15 numbers then it kicks out one of its other numbers at
random. This number is put back to be distributed to some other ticket.

After all the numbers are distributed, each Housie generates itself
using the values it has been given. It will add one number at a time
to the row with the least amount of numbers. If two rows have the
same amount of numbers then their positions will be chosen randomly.

I also included a method to generate a single ticket.

The code got a bit messier than I'd like it, but it avoids brute
force-generation and seem to generate tickets quickly.


/Christoffer


#####

class Housie

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

# Push a number to this ticket.
#
# 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
value = @colset[rand(9)].shift while value.nil?
value
else
@numbers += 1
nil
end
end

# Generates a ticket from added data
# Since we have 15 numbers, not more than 3 of each column type we
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...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 = (1..90).to_a
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
random_numbers = (1..90).sort_by { rand }
until housie.complete?
returned = housie.push random_numbers.shift
random_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

 
Reply With Quote
 
Andy Restrepo
Guest
Posts: n/a
 
      02-18-2007
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 = ((E-Mail Removed)).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(1{ 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 rint_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 rint_ticket
end

TicketGenerator.new.print_book


 
Reply With Quote
 
d.frommknecht@googlemail.com
Guest
Posts: n/a
 
      02-18-2007
Hi,

my solution first figures out which postitions in the ticket should be
filled with numbers (setting those to 1, the others to 0).
It moves from column to column starting on the left and selects a
random valid column. At each step, all columns that would lead to
invalid solutions are deleted from the set of possible columns.

The second step is to fill the ticket with real values. It just
replaces the 1s from the creation with allowed values.

I didn't implement the creation of the complete book.

Regards,
Dennis

----- THE CODE ---------------


$thegrid = []

# creates the grid
# inserts 1 for positions that should be filled later on,
# sets it to 0 otherwise
def create_grid
# array with all allowed columns
cache = (1..7).map{|i| Array.new(3) {|j| i[j]}.reverse! }
rowcounter = [0,0,0]

# step through each colum, choosing a random valid column from cache
# deletes all rows from cache that lead to invalid solutions
0.upto( 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== ? 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/, " ")
}


 
Reply With Quote
 
Christoffer Lernö
Guest
Posts: n/a
 
      02-18-2007
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

 
Reply With Quote
 
Brock Lee
Guest
Posts: n/a
 
      02-18-2007
Does your solution make sure there are exactly five numbers on each
row?

 
Reply With Quote
 
Brock Lee
Guest
Posts: n/a
 
      02-18-2007
Does your solution make sure there is at least one number in each
column of the ticket?

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SUMMARY] Housie (#114) Ruby Quiz Ruby 0 02-22-2007 05:03 PM



Advertisments