[QUIZ] Housie (#114)

Discussion in 'Ruby' started by Ruby Quiz, Feb 16, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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
    Ruby Quiz, Feb 16, 2007
    #1
    1. Advertising

  2. Ruby Quiz

    Eric I. Guest

    Re: Housie (#114)

    On Feb 16, 11:47 am, Ruby Quiz <> 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
    Eric I., Feb 16, 2007
    #2
    1. Advertising

  3. Re: Housie (#114)

    On Feb 16, 2007, at 2:10 PM, Eric I. wrote:

    > On Feb 16, 11:47 am, Ruby Quiz <> 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
    James Edward Gray II, Feb 16, 2007
    #3
  4. Ruby Quiz

    Eric I. Guest

    Re: Housie (#114)

    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 = true
    relative_odds = 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 - column_counts
    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 = feeders.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 = feeders[0...nums_in_cols].sort +
    feeders[nums_in_cols..-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 ? feeders.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
    Eric I., Feb 18, 2007
    #4
  5. 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
    Christoffer Lernö, Feb 18, 2007
    #5
  6. 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 = ().sort_by{ rand }.sort_by{ |b|
    @bins.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
    Andy Restrepo, Feb 18, 2007
    #6
  7. Ruby Quiz

    Guest

    Re: Housie (#114)

    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[j] = rand(stop - start - count + 2) + start
    start = $thegrid[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/, " ")
    }
    , Feb 18, 2007
    #7
  8. 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
    Christoffer Lernö, Feb 18, 2007
    #8
  9. Ruby Quiz

    Brock Lee Guest

    Re: Housie (#114)

    Does your solution make sure there are exactly five numbers on each
    row?
    Brock Lee, Feb 18, 2007
    #9
  10. Ruby Quiz

    Brock Lee Guest

    Re: Housie (#114)

    Does your solution make sure there is at least one number in each
    column of the ticket?
    Brock Lee, Feb 18, 2007
    #10
  11. Re: Housie (#114)

    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.
    Christoffer Lernö, Feb 18, 2007
    #11
  12. Oops. Missed out the requirement that each column should be filled. =20
    Embarassing. Sorry about that folks.

    /Christoffer

    On Feb 18, 2007, at 18:33 , Christoffer Lern=F6 wrote:

    > My solution drops the numbers 1-90 into the tickets at random. If =20
    > there are more than 3 numbers of the same column for a ticket, or =20
    > it already has 15 numbers then it kicks out one of its other =20
    > numbers at random. This number is put back to be distributed to =20
    > some other ticket.
    >
    > After all the numbers are distributed, each Housie generates itself =20=


    > using the values it has been given. It will add one number at a =20
    > time to the row with the least amount of numbers. If two rows have =20
    > the same amount of numbers then their positions will be chosen =20
    > 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 =20
    > force-generation and seem to generate tickets quickly.
    >
    Christoffer Lernö, Feb 18, 2007
    #12
  13. 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
    Christoffer Lernö, Feb 18, 2007
    #13
  14. 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 = ().sort_by{ rand }.sort_by{ |b|
    @bins.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
    Andy Restrepo, Feb 19, 2007
    #14
  15. Re: [QUIZ] Housie (#114) variant solution

    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
    Christoffer Lernö, Feb 19, 2007
    #15
  16. Ruby Quiz

    Daniel N Guest

    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 += 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
    Daniel N, Feb 19, 2007
    #16
  17. Re: Housie (#114)

    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] - num)
    #if so, increment and decrement the numbers.
    self[row][column] += num
    self[row] -= 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

    --
    Posted via http://www.ruby-forum.com/.
    Ruben Medellin, Feb 20, 2007
    #17
  18. Ruby Quiz

    Guest

    Re: Housie (#114)

    On 16 Feb., 17:47, Ruby Quiz <> wrote:
    > The three rules of RubyQuiz:
    >
    > 1. Please do not post any solutions or spoiler discussion for thisquizuntil
    > 48 hours have passed from the time on this message.
    >
    > 2. Support RubyQuizby 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 originalquizmessage,
    > 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 ofquizdifficulty 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


    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 :>
    , Feb 21, 2007
    #18
  19. Re: Housie (#114)

    <SPOILER>
    On Wed, Feb 21, 2007 at 07:50:09PM +0900, 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>
    Brian Candler, Feb 21, 2007
    #19
  20. Re: Housie (#114)

    On Feb 21, 2007, at 4:50 AM, 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
    James Edward Gray II, Feb 21, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    366
    James Edward Gray II
    Jan 18, 2005
  2. David Tran
    Replies:
    9
    Views:
    187
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    325
    gabriele renzi
    Feb 24, 2005
  4. Ruby Quiz

    [SUMMARY] Housie (#114)

    Ruby Quiz, Feb 22, 2007, in forum: Ruby
    Replies:
    0
    Views:
    110
    Ruby Quiz
    Feb 22, 2007
  5. Levi Nie
    Replies:
    0
    Views:
    151
    Levi Nie
    Jan 16, 2013
Loading...

Share This Page