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

on 2007-02-16 17:49

on 2007-02-16 21:11

On Feb 16, 11:47 am, Ruby Quiz <j...@grayproductions.net> 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

on 2007-02-16 21:13

On Feb 16, 2007, at 2:10 PM, Eric I. wrote: > 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

on 2007-02-18 18:16

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

on 2007-02-18 18:34

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..8).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

on 2007-02-18 20:20

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

on 2007-02-18 21:11

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(8) 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==8) ? 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/, " ") }

on 2007-02-18 22:18

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

on 2007-02-18 23:45

Does your solution make sure there is at least one number in each column of the ticket?

on 2007-02-18 23:46

Does your solution make sure there are exactly five numbers on each row?

on 2007-02-18 23:50

On Feb 18, 2007, at 23:45 , Brock Lee wrote: > Does your solution make sure there are exactly five numbers on each > row? Ooops, was that I requirement? Kind of missed that.

on 2007-02-18 23:53

Oops. Missed out the requirement that each column should be filled. Embarassing. Sorry about that folks. /Christoffer On Feb 18, 2007, at 18:33 , Christoffer Lernö wrote:

on 2007-02-19 00:15

Not very elegant, but it's a minimal fix to my original solution so that each ticket has at least a single value in each column. /C 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 random_col = rand(9) while random_col.nil? || @colset [random_col].size < 2 @colset[random_col].shift 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..8).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 = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } } numbers[0].delete 0 numbers[8] << 90 # First make sure every book has at least one entry numbers.each do |col| col.replace col.sort_by { rand } housies.each { |housie| housie.push(col.shift) } end # That done, distribute the rest of the numbers numbers.flatten! 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 numbers = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } } numbers[0].delete 0 numbers[8] << 90 # First make sure this ticket has at least one entry numbers.each do |col| col.replace col.sort_by { rand } housie.push(col.shift) end # Distribute the rest of the numbers numbers = numbers.flatten!.sort_by { rand } until housie.complete? returned = housie.push numbers.shift 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

on 2007-02-19 07:16

Quick and dirty hack that fixes the problem of possibly empty columns with my solution: if a ticket with an empty column is detected, just start over again. ######## 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 = (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 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 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 private :init_bins, :retrieve_row, :build_book 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 @empty_column = false validate_ticket end def is_valid? not @empty_column 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 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, :is_valid? end TicketGenerator.new.print_book

on 2007-02-19 09:33

Here is a different solution. This first populates each ticket with at least 1 entry. After that it treats the tickets as 18 rows and populates it with the "max 5 in a row"-constraint. To avoid getting stuck, it will swap out a random number if there already are 5 numbers in the row. This could cause a ticket to lose its minimum of 1 entry per column, so the initial entries in every ticket column are prevented from being swapped out. Finally the actual numbers are added instead of the placeholders used up to this point. #### class Housie def initialize(housie_array) @housie_array = housie_array raise "Illegal size" unless @housie_array.size == 3 @housie_array.each { |row| raise "Illegal row in housie # {row.inspect}" unless row.compact.size == 5 } 9.times do |col| raise "Illegal column #{col}" unless @housie_array.collect { | row| row[col] }.compact.size > 0 end end # Ugly code to display a ticket. def to_s @housie_array.inject("") do |sum, row| sum + "+----" * 9 + "+\n" + row.inject("|") { | sum, entry | sum + " #{"%2s" % entry} |" } + "\n" end + "+----" * 9 + "+" end def Housie.new_book housies = Array.new(6) { Array.new(3) { Array.new(9) } } columns = Array.new(9) { |col| Array.new(10, col) } columns[0].shift columns[8] << 8 # First make sure every book has at least one entry. # These entires are fixed and can't be swapped out. columns.each do |col| housies.each do |housie| housie.select { |row| row.compact.size < 5 }.sort_by { rand }.first[col.shift] = :fixed end end # Merge all rows all_rows = [] housies.each { |housie| housie.each { |row| all_rows << row } } # Fill all rows, start with the one with fewest entries, resolve ties randomly while (columns.flatten.compact.size > 0) do columns.select { |col| col.size > 0 }.each do |col| all_rows.reject { |row| row[col.first] }.sort_by { rand }.each do |row| break unless col.first # A full row needs to have a value swapped out if row.compact.size == 5 # Only try to swap if we have swappable entries if row.member? :selected removed_col = rand(9) while removed_col.nil? || row [removed_col] != :selected; row[removed_col] = nil columns[removed_col] << removed_col row[col.shift] = :selected end else row[col.shift] = :selected end end end end # Populate actual numbers values = Array.new(9) { |col| Array.new(10) { |i| i + col * 10 } } values[0].shift # remove 0 values[8] << 90 # add 90 values.each_with_index do |col, index| col = col.sort_by { rand } housies.each do |housie| entries = housie.inject(0) { |sum, row| sum + (row[index] ? 1 : 0) } values = col.slice!(0...entries).sort housie.each { |row| row[index] = values.shift if row[index] } end end housies.collect { |housie| Housie.new(housie) } end end

on 2007-02-19 13:05

Well this is my first attempt at solving one of these quizzes. Please be gentle, especially with the comments I think. This solution uese Ranges extensivley and relies on a method choose_uniq_members on any given range. This will randomly select the specified number of entries from the range. The output grid is constructed by first selecting which columns will be filled, ie 5 columns per row, and 3 rows. This is then used as a specification for each column which tells the choose_uniq_members method on the column range how many, 0 to 3, members of the range to select. It's then collected up into the @rows variable and displayed. Please be gentle ;) # Ruby quiz 114 # class Range # Choose the specified number of random elements of the range def choose_uniq_members( num = 1 ) # Make sure the range is large enough to select correct number of uniq members raise "RangeBoundaryError" if self.size < num return self.to_a if self.size == num # Select the specified number of random entries from the range tmp = self.dup.to_a selected = [] num.times { selected << tmp.delete_at( rand( tmp.size ) ) } selected.sort end def size @size ||= self.to_a.size end end class HousieTicket COLUMNS = [ 1..9, 10..19, 20..29,30..39,40..49,50..59,60..69,70..79,80..90] def initialize # an array of arrays for rows and columns for the final data @rows = Array.new(3){ Array.new(9) } # Maps out in a 3 x 5 array, which of the final @rows indicies should contain numbers row_map = (1..3).inject([]){ |arr, i| arr << (0...COLUMNS.size).choose_uniq_members(5) } # Maps the indicies of row_map into column counts so that each column may be populated. # The number found for each column will be used to choose from the relevant range. # ie column 0 = 2, therefore two numbers from the range 1..9 should be selected the_map = row_map.flatten.inject( Hash.new(0) ){ |col_map, i| col_map[i] += 1; col_map } # Populate the final @rows array with the real numbers based on the prototype matrix developed # in row_map by choosing the number of uniq values from the columns range as specified in the_map (0...9).each do | col_index | numbers = COLUMNS[col_index].choose_uniq_members( the_map[col_index] ).reverse (0...3).each do | row_index | @rows[ row_index ][ col_index ] = numbers.pop if row_map[ row_index ].include?( col_index ) end end end # From here down is display methods # Various display methods to print out the ticket to the terminal def display array = stringify_rows print_line_seperator array.each do |row| puts "|" << row.join( "|" ) << "|" print_line_seperator end end def stringify_rows rows = @rows.dup rows.map do |row| row.map{ |e| if(e) then sprintf(" %02d ", e) else " " end } end end def print_line_seperator puts "|" << "----|" * 9 end end # Runs the program from the terminal number_of_tickets = ARGV[0] unless number_of_tickets.to_i > 0 puts "How many tickets would you like to generate?\n" until number_of_tickets.to_i > 0 number_of_tickets = gets.chomp end end 1.upto(number_of_tickets.to_i ) do |n| ticket = HousieTicket.new puts "\n\n" puts "Ticket #{n}" ticket.display end

on 2007-02-19 19:03

Ruby Quiz <james@grayproductions.net> writes: > 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. > 1. Write a Ruby program which generates random individual tickets > or > 2. Write a Ruby program which generates random complete books of tickets When I first read the description, I thought "I already did that". And in fact, I did. Back in 2002, after only a few weeks using Ruby. Have a look at the timestamp: -rw-r--r-- 1 chris chris 1472 Jan 13 2002 bingo.rb (Incidentally, that's my sisters birthday and I remember the guests liked it.) Anyway, my bingo solution from 2002 generates plain TeX output suitable for printing. The macro package is appended. You'd call it like ruby bingo.rb > entries.tex && pdftex bingo.tex. Remember that this code has been untouched for 5 years, I wouldn't necessarily code it that way today. #!/usr/bin/env ruby # -*- ruby -*- Num = 14 class Bingo def initialize @width = 9 @height = 3 @field = [[0,0,0],[0,0,0],[0,0,0], [0,0,0],[0,0,0],[0,0,0], [0,0,0],[0,0,0],[0,0,0]] end def insert_numbers 0.upto (@width-1) { |x| arr = ((x*10)..((x*10)+10)-1).to_a # Special cases: don't insert a 0, add 90 to the row with 80 arr.delete(0) if arr.index(89) != nil arr = arr + [90] end 0.upto (@height-1) { |y| r = arr[rand (arr.length)] arr.delete(r) @field[x][y] = r } @field[x].sort! } end def remove_some 0.upto(@height-1) { |x| cnt = 0 while cnt < 4 cnt+=1 r = rand @field.length # The following crap eludes `three in a row' if @field[r][x] != nil && !((@field[r][0] == nil && @field[r][1] == nil) || (@field[r][1] == nil && @field[r][2] == nil) || (@field[r][2] == nil && @field[r][0] == nil)) @field[r][x] = nil else cnt-=1 end end 0.upto (@width-1) { |y| } } puts end def dump 0.upto(@height-1) { |x| 0.upto(@width-1) { |y| value = @field[y][x] if (0..9).to_a.index(value) != nil value = '?' + value.to_s end if value == nil value = '\X' end print "&& ", value, " " } if x != @height-1 print "&\\nl\n" else print "&\\newsheet\n" end } end end Num.times { b = Bingo.new b.insert_numbers b.remove_some b.dump } % Print ``bingo'' sheets. \font\mainfont=cmbx14 \mainfont \newbox\strutbox \setbox\strutbox=\hbox{\vrule height18.5pt depth13.5pt width0pt} \def\strut{\relax\ifmmode\copy\strutbox\else\unhcopy\strutbox\fi} \newdimen\onedigitwidth \newdimen\digitwidth \setbox0=\hbox{\mainfont0} \onedigitwidth=\wd0 \setbox0=\hbox{\mainfont00} \digitwidth=\wd0 \catcode`?=\active \def?{\hbox to \onedigitwidth{}} \def\X{\hbox to \digitwidth{\hfil$\bigcirc$\hfil}} \begingroup \tabskip=0pt \offinterlineskip \def\nl{\cr\noalign{\hrule}} \def\newsheet{\cr\noalign{\hrule\vskip1cm\hrule}} \halign{\strut#& \vrule#\tabskip=0.50em& \hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#&\hfil#\hfil& \vrule#\tabskip=0pt\nl \input entries.tex \cr} \endgroup \bye Enjoy,

on 2007-02-20 02:04

James Gray wrote: > 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 Yay, I finally got time for this, my first try to submit one. It might be a little tricky, but it does what it has to :) _________________________________________________________________ #First of all, let's look at the books. #Assuming a symetrical distribution of tens, we have that for all nine rows, #tickets can have one of the following distributions of numbers in a columnn: def make_poss [ [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 3, 3, 3] ] end #Don't forget to put the numbers in the bag! def make_container initial = (0..8).to_a.collect{|n| ((10*n)..(10*(n+1) - 1)).to_a } initial[0].delete(0); initial[-1].push(90) initial end class Array #Tricked so it adds only the non-nil elements def sum inject(0) {|sum, n| n.nil? ? sum : sum + n } end def column(n) collect{|row| row[n]} end end class Book < Array attr_accessor :tickets, :distribution def initialize #Lets's the fun begin. As stated before, a ticket can have on of 4 possible #distribution of tickets (and they are ALL the possibilities). #So, we start defining randomly the distributions of our tickets. #Furthermore, we scramble the possibilities, so any row can have any distribution provided. super(Array.new(6).collect{|i| (poss = make_poss)[rand(poss.size)].sort_by{rand} }) #Now we have to distribute our matrix. Because of the above, each row sums 15, but we have to make #each column sum 10. make_distribution #Now we adjust the numbers on each ten. balance @tickets = [] #And we're ready make_tickets end #This method iterates each column, and accomodate the numbers until the sum of each column is 10. def make_distribution for i in 0...9 s = column(i).sum remaining = (10 - s).abs if s != 10 #If the sum is different than 10, decrement one to the greater #and increment it to the possible in the row, or viceversa. #If that's not possible, go onto the next row, and repeat if necessary. remaining.times do index = 0 until gain(index, i, (s < 10 ? 1 : -1)) index += 1 index = 0 if index == 5 end end end end end def display @tickets.each {|ticket| ticket.display} end #Knowing the distribution of the tickets, they are done almost automatically. def make_tickets container = make_container each{ |row| @tickets << Ticket.new(row, container) } end #Returns the index where the increment occured, or nil if cannot be done def gain(row, column, num = 1) item = self[row][column] #We know a priori that the numbers must be between 1 and 3 return nil if (item == 3 && num == 1) or (item == 1 && num == -1) #iterate over the array, starting from the right of the column for i in (column + 1)...(self[row].size) #Find the first element that can accept a loss of -num (or a gain) if (1..3) === (self[row][i] - num) #if so, increment and decrement the numbers. self[row][column] += num self[row][i] -= num return i end end return nil end #Balances the ticket distribution so the first row has 9 numbers and #the last one 11, without affecting the sum. def balance for row in self if row[0] > 1 and row[-1] < 3 row[0] -= 1 row[-1] += 1 break end end end end class Ticket < Array def initialize(distribution = (poss = make_poss)[rand(poss.size)], container = make_container) #When initializing, we first make the ticket 'vertical' so its easier to keep track of the #numbers in each row. super(9); collect! {|row| []} distribution.each_with_index do |distr, index| choose = container[index] distr.times do #Exhausting possibilities self[index] << choose.slice!(rand(choose.size)) end end collect! { |row| row.sort! } make_format end def make_format #Iterate over the colums for i in 0...3 #Do this until we have 5 elements per column. until (s = column(i).compact.length) == 5 #If the number of elements in the column is more than 5, #move one randomly to the next place if s > 5 x = rand(9) self[x].insert(i, nil) unless self[x].length == 3 else #If the number is less than four (that can only happen in the second column), #remove one nil for row in self if row[1] == nil and row[2] != nil row[1], row[2] = row[2], nil break end end end end end #Now we just transpose the ticket. replace((0...3).collect{ |i| column(i) }) end def display print(top = "+----" * 9 + "+\n") each do |row| row.each{ |number| print("|" + " " * (3 - number.to_s.length) + number.to_s + " ") } print "|\n", top end puts end end puts "Type B for a complete book, or T for a single ticket.\nType anything else to exit" while (option = gets.chomp) =~ /\A[BbTt]/ if option =~ /\A[Bb]/ #Now all we have to do is to create a new book... book = Book.new #and display it... puts "BINGO!\n" book.display else #Or we can make single tickets... for cheating... you know puts "Today's my lucky day" x = Ticket.new x.display end puts "Play again?" end

on 2007-02-21 11:51

On 16 Feb., 17:47, Ruby Quiz <j...@grayproductions.net> wrote: > > each book every number from 1 to 90 is used exactly once. > +----+----+----+----+----+----+----+----+----+ > 1. Write a Ruby program which generates random individual tickets > or > 2. Write a Ruby program which generates random complete books of tickets I wanted to participate to a ruby quiz again - took a 40 quizzes break. But I can't get a perfect algo for creating a Book. This is probably a spoiler, maybe not <SPOILER> One Idea was to create each ticket, by building 2 rows and complete the last row: if both elements of the column were nil, mark the third element as "to be filled" and so on. But by doing this, I would actually change the probabilities, because the last row depends on the first two rows. So far the only perfect "algo" that came to my mind was to create all possible books and chose one randomly. By this method the chances are perfectly balanged. I mean we're talking about BINGO! It's about money... and you should be able to proof that your algo generates all possible books at equal probability. </SPOILER> Am I right with that, or is this totally nonsense? Either way, please feedback to me :>

on 2007-02-21 12:46

<SPOILER> On Wed, Feb 21, 2007 at 07:50:09PM +0900, rretzbach@googlemail.com wrote: > So far the only perfect "algo" that came to my mind was to create > all possible books and chose one randomly. Directly enumerating all possible patterns for an individual ticket is certainly doable. There are 735,210. This means that the simple set of 'all possible books' is enormous, but there may be some way to fold it to a manageable size. I look forward with interest to seeing the solutions in this area :-) </SPOILER>

on 2007-02-21 14:00

On Feb 21, 2007, at 4:50 AM, rretzbach@googlemail.com wrote: > So far the only perfect "algo" that came to my mind was to create > all possible books and chose one randomly. You can create a lot less than "all possible books" if you think in terms of patterns, and still be able to create all of the combinations. Think about what moves around in the tickets/books besides the numbers. James Edward Gray II

on 2007-03-23 02:58

rretzbach's first proposal is exactly the same as mine. I don't think the probabilities are not evenly distributed in the proposed. And my program generates the row pattern is the following: def make_rows row1 = gen_rands_nodup(9, 0, 5, Array.new) row2 = gen_rands_nodup(9, 0, 5, Array.new) row3= [0,1,2,3,4,5,6,7,8]-(row1+row2) row3 = gen_rands_nodup(9, 0, 5, row3) end def gen_rand max,range rand(max) + range * 10 end def gen_rands_nodup max,range,num,arr i = arr.length while i < num do rand_val = gen_rand(max,range) while arr.include?(rand_val) do rand_val = gen_rand(max,range) end arr[i] = rand_val i += 1 end arr end Is there any bug in this algorithm?

on 2007-03-26 20:05

On Mar 22, 2007, at 8:58 PM, Quest Lee wrote: > row3= [0,1,2,3,4,5,6,7,8]-(row1+row2) > while i < num do > Is there any bug in this algorithm? I don't think so, but it's a little hard to follow the logic. You could definitely simplify gen_rands_nodup using upto(), times(), or inject(). I would begin by trying to remove the index. I'm not immediately sure how to prove it's not purely random, though my hunch is that it is not. James Edward Gray II

on 2007-09-25 23:03

```
On Feb 21, 2007, at 15:31 , Brian Candler wrote:
> Since I posed the problem in the first place, here's my solution.
Since there was a benchmark in your solution, I did some checks on
the other solutions as well.
Of those who provide a complete book I find that on my computer Ruben
Medellin's solution is the fastest, followed by Andy Restrepo's
solution. Someone interested in doing a benchmark on all the
solutions and share? (I'd do it myself but I don't trust my computer
to produce consistent results when benchmarking)
/Christoffer
```

on 2007-09-25 23:09

Since I posed the problem in the first place, here's my solution. As a bit of background: after submitting the first draft of the quiz to James, I made it an explicit requirement that numbers had to be placed in a column in increasing order downwards, e.g. +----+ +----+ | 85 | | 86 | +----+ +----+ | | is OK, but | | is not. +----+ +----+ | 86 | | 85 | +----+ +----+ A little thought shows that it's always possible to transform a "bad" solution like the RHS into a "good" solution like the LHS, just by swapping the values around, keeping any blanks in the same position. This in turn led me to realise that the only thing which matters is the position of blanks and non-blanks, and this can be represented in a bitmap. The attached solution enumerates all possible tickets grids up-front, which is remarkably quick when using a Fixnum to represent each bitmap. Then, assembling together 6 grids to form a book is a case of picking 6 grids which have a total of 9 non-blanks across the first column, 10 non-blanks across the second..eighth columns, and 11 non-blanks across the last column. I couldn't think of a deterministic way of doing this, so it just picks 5 grids at random and looks in an index to find if there is any 6th grid which could be used to complete the book. After implementing the solution, I realised that the three rows in a ticket can be shuffled around in any order without breaking the structure of either the ticket or the book. This could be used to reduce the number of stored grid patterns by a factor of 6; then when you generate a book, as a last step you can randomly shuffle the rows in each ticket. Regards, Brian. P.S. Note to James: I just discovered a silly bug in Bookpattern.make_random which has been fixed in the attached version :-)