Housie (#114)

Ruby
21

On Feb 21, 2007, at 4:50 AM, [email protected] 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 G. II

22

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?

23

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 G. II

24

On Feb 21, 2007, at 15:31 , Brian C. 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

25

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 :slight_smile: