Slightlly OT - Bingo problem

[Geoff Berrow]

I may have mentioned that I run an Introduction to PHP course at a local
college (very basic - I'm no PHP expert). Well, one of my students was
doing really well so I set him some extension work. The task was to use
PHP to generate a random bingo card. The standard UK card has nine rows
and three columns. Each row has five numbers. All numbers are
different, out of a pool of 90.

I asked my student to design one card. He came back a few days later
with a solution that generated six cards, using each of the90 numbers
just once. Or so I thought.

Although I'd set the problem I had not coded the solution myself so I
set to it. I tried various methods but could not get a script which
would work reliably every time. More often than not I could not get all
the numbers to fit. I eventually solved the problem by brute force, ie
I discard all attempts that don't work. See
http://www.ckdog.co.uk/php/test/bingo.php for my solution
Code is here:
http://www.ckdog.co.uk/php/test/bingo_code.phps

I was still smarting because I thought my student had come up with a
better solution than me so I took another look at his. He had the same
problem, occasionally, the last line was not complete. It's a bit like
the card game patience, sometimes it doesn't work out. If you are
reading this Craig, don't look at my solution :-)

The question I have is this. Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?

Please help this poor lecturer stay one step ahead of his students. :-)
--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/

[Dani CS]

Geoff Berrow wrote:

I may have mentioned that I run an Introduction to PHP course at a local
college (very basic - I'm no PHP expert). Well, one of my students was
doing really well so I set him some extension work. The task was to use
PHP to generate a random bingo card. The standard UK card has nine rows
and three columns. Each row has five numbers. All numbers are
different, out of a pool of 90.
I guess you mean three rows and nine columns (so that 5 numbers in each
row sum up to 15 numbers per card).

I asked my student to design one card. He came back a few days later
with a solution that generated six cards, using each of the90 numbers
just once. Or so I thought.

<snip>

The question I have is this. Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?
This solution seems trivial to me, so it must be wrong:

1. Generate a random permutation of the 90 numbers.
(Google knows how to do it.)

2. Split the permutation in 6 blocks of 15 numbers.

3. Sort each block.

4. Assign each block to a card.

Am I missing something?

Please help this poor lecturer stay one step ahead of his students. :-)

[Michael Fesser]

.oO(Geoff Berrow)

The question I have is this. Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?

There's a mathematical approach for doing that (can't remember exactly,
would have to look it up), but PHP is already capable of doing it.

A quick 'n dirty hack:

<?php
// too lazy to write HTML tables ... ;-D
header('Content-type: text/plain');

// create array with 90 numbers, ordered randomly
$numbers = range(1, 90);
shuffle($number s);

// create six cards
for ($i = 0; $i < 6; $i++) {
// get 15 numbers for each card and fill up to 27 with empty elements
$card = array_pad(array _slice($numbers , $i * 15, 15), 27, 0);
// randomize positions on the card
shuffle($card);
// print the card out
for ($j = 0; $j < 27; $j++) {
print $card[$j] != 0 ? sprintf(' %02u', $card[$j]) : ' ..';
print ($j + 1) % 9 ? '' : "\n";
}
print "\n\n";
}
?>

HTH
Micha

[Janwillem Borleffs]

Geoff Berrow wrote:

The question I have is this. Is it possible to write an algorithm
that will place all 90 numbers in the matrix in a random fashion that
will not have to loop because of failed attempts?

Something like this?

http://www.jwscripts.com/playground/bingo.phps
JW

[Michael Fesser]

.oO(Michael Fesser)

A quick 'n dirty hack:
[...]

OK, I missed that 5-per-row issue (never played Bingo), but it should
not be hard to add.

Micha

[Geoff Berrow]

I noticed that Message-ID: <41************ ***********@new s.euronet.nl>
from Janwillem Borleffs contained the following:

The question I have is this. Is it possible to write an algorithm
that will place all 90 numbers in the matrix in a random fashion that
will not have to loop because of failed attempts?

Something like this?

http://www.jwscripts.com/playground/bingo.phps

Nice but I forgot to give you all some information.

The numbers have to be aligned so that people can mark them off easily.
That means 1-9 go in column 1, 10-19 in column 2 20-29 in column 3 and
so on. The last column has numbers in the range 80-90

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/

[Geoff Berrow]

I noticed that Message-ID: <cq**********@n ews.ya.com> from Dani CS
contained the following:

I guess you mean three rows and nine columns (so that 5 numbers in each
row sum up to 15 numbers per card).

Doh! Yes of course. I've been working on this too long...

I asked my student to design one card. He came back a few days later
with a solution that generated six cards, using each of the90 numbers
just once. Or so I thought.

<snip>

The question I have is this. Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?

This solution seems trivial to me, so it must be wrong:

Yes, I didn't give you all the information. The columns represent the
ranges 1-9, 10-19, 20-29, and so on up to 80-90 for the last one.

It follows then that for each card there cannot be more than 3 numbers
from each range.

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/

[Geoff Berrow]

I noticed that Message-ID: <sl************ *************** *****@4ax.com>
from Geoff Berrow contained the following:

Something like this?

http://www.jwscripts.com/playground/bingo.phps

Nice but I forgot to give you all some information.

However, it also prints the same cards each time.
--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/

[Andy Hassall]

On Sat, 18 Dec 2004 09:57:50 +0000, Geoff Berrow <bl******@ckdog .co.uk> wrote:

Please help this poor lecturer stay one step ahead of his students. :-)

I think he might have caught on to the trick - there's a Bingo post on
alt.comp.lang.p hp ;-)

--
Andy Hassall / <an**@andyh.co. uk> / <http://www.andyh.co.uk >
<http://www.andyhsoftwa re.co.uk/space> Space: disk usage analysis tool

[Michael Fesser]

.oO(Geoff Berrow)

The question I have is this. Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?

Another idea ...

It should be possible to set all numbers on all six cards in a way
similar to the eight-queens-problem.

There are some defined constraints on the rows and columns, which can be
easily checked:

* There are 18 rows, splitted into 6*3. Each row holds 5 numbers.
* There are 9 columnss, the first contains the numbers 1-9, the next
10-19 and so on, the last one contains 80-90. So you always know which
column a number belongs to, you just have to find a row that isn't
completed yet (has less than 5 numbers).

So consider all six 9*3 cards as one single 9*18 card, then it should be
as follows:

* Get a number.
* Determine its column.
* Put it in the first row that has less than 5 numbers.
* Move on to the next number.

If at some point a number can't be set because there's no free row
available for the required column, step back to the last set number and
change their position, then continue from there (and if the position
can't be changed anymore move back another step). This backtracking is
quite easy to do with recursive algorithms.

Just the basic idea ...

Micha