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($numbers);

// 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***********************@news.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**********@news.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.php ;-)

--
Andy Hassall / <an**@andyh.co.uk> / <http://www.andyh.co.uk>
<http://www.andyhsoftware.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

[Janwillem Borleffs]

Geoff Berrow wrote:

However, it also prints the same cards each time.

Actually it doesn't (try http://www.jwscripts.com/playground/bingo.php).

If you want the numbers more random than they currently are, use seeding as
described on:

http://www.php.net/manual/en/function.mt-srand.php
JW

[Pedro Graca]

Michael Fesser wrote:

.oO(Geoff Berrow)

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

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.

Without recursion my algorithm often (*) fails for the last few numbers

(*) I haven't had a run for the whole 90 numbers :-)

================================================
<?php
function row_ok($x, $number) {
if (count($x) == 5) return false;
$lo = (int)($number/10) * 10;
if ($lo == 90) $lo = 80;
$hi = $lo + 9;
if ($lo == 80) $hi = 90;
foreach ($x as $v) {
if (($lo <= $v) && ($v <= $hi)) {
return false;
}
}
return true;
}

function insert_number(&$c, $number) {
if (count($c[0]) + count($c[1]) + count($c[2]) == 15) {
return false; /* if card is full */
}
$initial_row = $row = rand(0, 2);
while (!row_ok($c[$row], $number)) {
++$row;
if ($row == 3) $row = 0;
if ($row == $initial_row) return false;
}
$c[$row][] = $number;
return true;
}

function print_cards(&$cards) {
print_r($cards); /* I'm lazy :-) */
}

$cards = array(
array(array(), array(), array()), /* ******************** */
array(array(), array(), array()), /* six cards */
array(array(), array(), array()), /* */
array(array(), array(), array()), /* with three rows each */
array(array(), array(), array()), /* */
array(array(), array(), array()), /* ******************** */
);

$numbers = range(1, 90);

foreach ($numbers as $n) {
$initial_card = $card = rand(0, 5);
while (!insert_number($cards[$card], $n)) {
++$card;
if ($card == 6) $card = 0;

/* without recursion this algorithm fails: stop it */
if ($card == $initial_card) {
echo 'last inserted number: ', $n-1, "\n";
print_cards($cards); exit();
}
}
}

print_cards($cards);
?>

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

[Geoff Berrow]

I noticed that Message-ID: <57********************************@4ax.com>
from Michael Fesser contained the following:

* Get a number.
* Determine its column.
* Put it in the first row that has less than 5 numbers.
* Move on to the next number.
That's what my solution does.
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.

Yes, I wondered if some backtracking might work, but my earlier versions
only failed on the last few numbers. Right now, if it fails I just run
the whole thing again. Since this works it is probably 'good enough'
but I'm just after something a bit more elegant.
--
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: <41***********************@news.euronet.nl>
from Janwillem Borleffs contained the following:

Geoff Berrow wrote:

However, it also prints the same cards each time.

Actually it doesn't (try http://www.jwscripts.com/playground/bingo.php).

No you are right, but it still doesn't comply with the other rules.

--
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: <ee********************************@4ax.com>
from Andy Hassall contained the following:

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.php ;-)

He has. <g>

--
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/

[CJ Llewellyn]

"Geoff Berrow" <bl******@ckdog.co.uk> wrote in message
news:ui********************************@4ax.com...
-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?
Certainly is

http://www.darrylcatchpole.net/bingo.phps

<pre>
<?php
class cRow {
var $aNumbers = array();
var $aBag = array();

function cRow($min, $max) {
mt_srand(mktime());
/*
place all numbers into a bag
*/
$this->aBag = range($min, $max);
/*
check the number of counters in bag as 1 - 9 is
lower the 10 - 19
*/
$counters = $max - $min;
for($i=$counters;$i>0;$i--)
{
/*
draw a random number out of the bag
*/
$n = mt_rand(0 , $i);
$this->aNumbers[] = $this->aBag[$n];
/*
remove from bag
*/
unset($this->aBag[$n]);
sort($this->aBag);
}
// add last number
$this->aNumbers[] = array_pop($this->aBag);
}
}

$aCard = array(
new cRow(1 , 9),
new cRow(10 , 19),
new cRow(20 , 29),
new cRow(30 , 39),
new cRow(40 , 49),
new cRow(50 , 59),
new cRow(60 , 69),
new cRow(70 , 79),
new cRow(80 , 89)
);

print_r($aCard);

?>
</pre>
Please help this poor lecturer stay one step ahead of his students. :-)

np :)

[Geoff Berrow]

I noticed that Message-ID: <cq**********@slavica.ukpost.com> from CJ
Llewellyn 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?

Certainly is

Sorry CJ, but unless I'm missing something, you haven't got a handle on
the problem.
See www.ckdog.co.uk/php/test/bingo.php

Each card has 9 columns and 3 rows
Each row contains 5 numbers and 4 spaces
Each column can contain 0-3 numbers
Numbers are ordered on the cards Column 1 contains 1-9 col2 10-19 ...
col8 70-79, col8 80-90
There are six cards
All numbers from 1-90 must be used just once.


--
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/

[CJ Llewellyn]

"Geoff Berrow" <bl******@ckdog.co.uk> wrote in message
news:bf********************************@4ax.com...

I noticed that Message-ID: <cq**********@slavica.ukpost.com> from CJ
Llewellyn 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?

Certainly is

Sorry CJ, but unless I'm missing something, you haven't got a handle on
the problem.

I've got a perfect handle on the problem. You asked for an algorythm that
would randomise 90 numbers into a matrix without using brute force.

All numbers from 1 to 90 are stored in seperate arrays all in random order.

All I have not done is written code to extract them into six cards which I
shall leave to the reader who should be capable of doing so. ;-)

[R. Rajesh Jeba Anbiah]

Geoff Berrow wrote:
<snip>

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 <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?

Without brute-force collision detection...

<?php
for($i=0; $i<9 ; ++$i)
{
$rand_tbl[$i] = range($i*10 + 1, $i*10 + 9);
shuffle($rand_tbl[$i]);
}
//print_r($rand_tbl);
for($row=0; $row<3; ++$row)
{
$card_arr[$row] = array_fill(0, 9, '');
$handle = range(0, 8);
shuffle($handle);
for($col=0; $col<5; ++$col)
$card_arr[$row][$handle[$col]] =
array_pop($rand_tbl[$handle[$col]]);
}
//print_r($card_arr);
echo '<pre>'."\n";
for($row=0; $row<3; ++$row)
{
for($col=0; $col<9; ++$col)
echo str_pad($card_arr[$row][$col], 4, ' ', STR_PAD_LEFT);
echo "\n";
}
echo '</pre>'."\n";
?>

Obviously, there must be some better algorithms.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[R. Rajesh Jeba Anbiah]

R. Rajesh Jeba Anbiah wrote:

Geoff Berrow wrote:
<snip>

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

<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?

Without brute-force collision detection...

<snip previous inaccurate code that didn't account 10,20,30..80>
Fixed...

<?php
$rand_tbl[0] = range(1, 9);
shuffle($rand_tbl[0]);
for($i=1; $i<9 ; ++$i)
{
$rand_tbl[$i] = range($i*10, $i*10 + 9);
shuffle($rand_tbl[$i]);
}
//print_r($rand_tbl);
for($row=0; $row<3; ++$row)
{
$card_arr[$row] = array_fill(0, 9, '');
$handle = range(0, 8);
shuffle($handle);
for($col=0; $col<5; ++$col)
$card_arr[$row][$handle[$col]] =
array_pop($rand_tbl[$handle[$col]]);
}
//print_r($card_arr);
echo '<pre>'."\n";
for($row=0; $row<3; ++$row)
{
for($col=0; $col<9; ++$col)
echo str_pad($card_arr[$row][$col], 4, ' ', STR_PAD_LEFT);
echo "\n";
}
echo '</pre>'."\n";
?>

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[R. Rajesh Jeba Anbiah]

Geoff Berrow wrote:
<snip>

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 <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?

Without brute-force collision detection...

<?php
for($i=0; $i<9 ; ++$i)
{
$rand_tbl[$i] = range($i*10 + 1, $i*10 + 9);
shuffle($rand_tbl[$i]);
}
//print_r($rand_tbl);
for($row=0; $row<3; ++$row)
{
$card_arr[$row] = array_fill(0, 9, '');
$handle = range(0, 8);
shuffle($handle);
for($col=0; $col<5; ++$col)
$card_arr[$row][$handle[$col]] =
array_pop($rand_tbl[$handle[$col]]);
}
//print_r($card_arr);
echo '<pre>'."\n";
for($row=0; $row<3; ++$row)
{
for($col=0; $col<9; ++$col)
echo str_pad($card_arr[$row][$col], 4, ' ', STR_PAD_LEFT);
echo "\n";
}
echo '</pre>'."\n";
?>

Obviously, there must be some better algorithms.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[R. Rajesh Jeba Anbiah]

Geoff Berrow wrote:
<snip>

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 <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?

Without brute-force collision detection...

<?php
for($i=0; $i<9 ; ++$i)
{
$rand_tbl[$i] = range($i*10 + 1, $i*10 + 9);
shuffle($rand_tbl[$i]);
}
//print_r($rand_tbl);
for($row=0; $row<3; ++$row)
{
$card_arr[$row] = array_fill(0, 9, '');
$handle = range(0, 8);
shuffle($handle);
for($col=0; $col<5; ++$col)
$card_arr[$row][$handle[$col]] =
array_pop($rand_tbl[$handle[$col]]);
}
//print_r($card_arr);
echo '<pre>'."\n";
for($row=0; $row<3; ++$row)
{
for($col=0; $col<9; ++$col)
echo str_pad($card_arr[$row][$col], 4, ' ', STR_PAD_LEFT);
echo "\n";
}
echo '</pre>'."\n";
?>

Obviously, there must be some better algorithms.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[R. Rajesh Jeba Anbiah]

R. Rajesh Jeba Anbiah wrote:

Geoff Berrow wrote:
<snip>

<snip triple post>

Apologies for the triple post. Stupid GG beta was keep on timouting
the posts but finally posted them.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[Michael Fesser]

.oO(Geoff Berrow)

Yes, I wondered if some backtracking might work
I tried, and it failed impressingly. ;)

I underestimated the complexity of setting 90 slots on a 9*18 card, so
that each row contains 5 and each column 10 (except for the first and
last) slots.
but my earlier versions
only failed on the last few numbers. Right now, if it fails I just run
the whole thing again. Since this works it is probably 'good enough'
but I'm just after something a bit more elegant.

Currently I think your trial-and-error method will lead faster to a
result than a more systematic and deterministic approach.

Micha

[Pedro Graca]

Michael Fesser wrote:

.oO(Geoff Berrow)

Yes, I wondered if some backtracking might work

I tried, and it failed impressingly. ;)

hehe, me too -- but I haven't given up, not just yet.
Just to make matters more difficult, can a card have 0 (zero) or three
numbers in a range? According to the original post, it can -- but do
*real* bingo cards have empty or full columns?

example:

-- 12 23 -- -- 56 61 -- 82
03 16 28 31 -- -- -- 78 --
07 17 -- 36 -- -- 64 -- 90
^^ ^^
(full) (empty)
And (for printing only) are the numbers in each column ordered?

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

[Geoff Berrow]

I noticed that Message-ID:
<sl*******************@ID-203069.user.uni-berlin.de> from Pedro Graca
contained the following:

I tried, and it failed impressingly. ;)

hehe, me too -- but I haven't given up, not just yet.
Just to make matters more difficult, can a card have 0 (zero) or three
numbers in a range? According to the original post, it can -- but do
*real* bingo cards have empty or full columns?

example:

-- 12 23 -- -- 56 61 -- 82
03 16 28 31 -- -- -- 78 --
07 17 -- 36 -- -- 64 -- 90

As I understand it, yes. I'll try to get a real card later and check.

--
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/

[Pedro Graca]

Pedro Graca wrote:

but I haven't given up, not just yet.

Latest code finds cards taking between
an instant and /a long time/ on my 500MHz PC:

Sample run:

* bingo$ php bingo.php
* 07 17 24 37 47 -- -- -- --
* -- 12 27 -- -- -- 63 73 80
* 05 13 26 -- 43 -- -- 72 --
*
*
* -- 16 23 35 -- 53 -- 76 --
* 08 -- 21 38 -- 55 -- -- 83
* -- 19 22 31 -- 54 -- -- 81
*
*
* -- -- -- -- 44 51 68 79 86
* -- -- 20 -- 45 -- 66 75 88
* 01 18 -- -- -- 50 62 -- 87
*
*
* -- -- -- 39 -- 57 60 70 85
* -- -- 25 -- -- 58 64 77 84
* 02 14 29 -- 48 52 -- -- --
*
*
* 03 -- -- 30 49 -- 61 -- 90
* -- 11 -- 34 42 59 67 -- --
* 04 -- -- -- 46 -- 65 78 89
*
*
* 09 10 28 33 41 -- -- -- --
* 06 15 -- 32 -- 56 -- 71 --
* -- -- -- 36 40 -- 69 74 82

== bingo.php =========================================

<?php
header('Content-Type: text/plain');
define('STOP_NUMBER', 90);

function can_insert_at_row(&$row, $n) {
if (count($row) == 5) return false;
$lo = ((int)($n/10)) * 10;
if ($lo == 90) $lo = 80;
$hi = $lo + 9;
if ($lo == 80) $hi = 90;
$cnt = 0;
foreach ($row as $v) {
if (($lo <= $v) && ($v <= $hi)) ++$cnt;
}
return ($cnt == 0);
}

function can_insert_at_card(&$card, $n) {
if (count($card[0]) + count($card[1]) + count($card[2]) == 15) return false;
$lo = ((int)($n/10)) * 10;
if ($lo == 90) $lo = 80;
$hi = $lo + 9;
if ($lo == 80) $hi = 90;
$cnt = 0;
foreach ($card as $row) {
foreach ($row as $v) {
if (($lo <= $v) && ($v <= $hi)) ++$cnt;
}
}
return ($cnt < 3);
}

function insert_number_R(&$cards, $n) {
/* for all cards, in random order */
$ini = mt_rand(0, 5);
$end = $ini + 6;

for ($i = $ini; $i < $end; ++$i) {
$ii = $i%6;
if (can_insert_at_card($cards[$ii], $n)) {
/* for all rows, in random order */
$ini_r = mt_rand(0, 2);
$end_r = $ini_r + 3;

for ($j = $ini_r; $j < $end_r; ++$j) {
$jj = $j%3;
if (can_insert_at_row($cards[$ii][$jj], $n)) {
/* insert it */
$insert_index = count($cards[$ii][$jj]);
$cards[$ii][$jj][$insert_index] = $n;

if ($n == STOP_NUMBER) return true;

/* and recurse for 1 + $n */
/* returning (with true) if recursive call returned true */
if (insert_number_R($cards, 1 + $n)) return true;

/* remove $n */
unset($cards[$ii][$jj][$insert_index]);

/* backtrack to the previous x9 number */
if ($n == 89) return false;
if ($n % 10 != 9) return false;
}
}
}
}
/* and return false (to backtrack) if all cards have been tried */
return false;
}

function print_cards(&$cards) {
foreach ($cards as $card) {
foreach ($card as $row) {
$last = 0;
foreach ($row as $n) {
$group = (int)($n/10);
if ($group == 9) $group = 8;
while ($last < $group) { echo "-- "; ++$last; }
printf("%02d ", $n);
$last = $group+1;
}
while ($last++ < 9) echo "-- ";
echo "\n";
}
echo "\n\n";
}
}

$cards = array(
array(array(), array(), array()), /* ******************** */
array(array(), array(), array()), /* six cards */
array(array(), array(), array()), /* */
array(array(), array(), array()), /* with three rows each */
array(array(), array(), array()), /* */
array(array(), array(), array()), /* ******************** */
);

if (!insert_number_R($cards, 1)) echo "Could not do it. Sorry!\n\n";
else print_cards($cards);
?>

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

[R. Rajesh Jeba Anbiah]

Pedro Graca wrote:

Pedro Graca wrote:

but I haven't given up, not just yet.

Latest code finds cards taking between
an instant and /a long time/ on my 500MHz PC:

Sample run:

<snip>

Is it about creating 6 cards or just 1 card? Anyway, I don't find it
to be difficult if you use shuffle-pick-remove logic.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

[Geoff Berrow]

I noticed that Message-ID:
<11**********************@c13g2000cwb.googlegroups .com> from R. Rajesh
Jeba Anbiah contained the following:

Is it about creating 6 cards or just 1 card? Anyway, I don't find it
to be difficult if you use shuffle-pick-remove logic.

Six, and I couldn't get your version to work.

It's getting the numbers to fit on the cards that poses the problem.

--
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/

[Michael Fesser]

.oO(R. Rajesh Jeba Anbiah)

Is it about creating 6 cards or just 1 card? Anyway, I don't find it
to be difficult if you use shuffle-pick-remove logic.

Generating random cards is trivial, you just have to put 5 random slots
into each row and fill them with numbers according to the column
constraints (first column 1..9, second 10..19, ..., last 80..90). Easy.

But the problem is to find 6 cards so that each number 1..90 is used
exactly once. Or in other words: To place 90 slots on a 9*18 card, so
that all row and column constraints are met (filling the slots with
numbers then is as easy as for a single card).

Micha

[CJ Llewellyn]

"Geoff Berrow" <bl******@ckdog.co.uk> wrote in message
news:7b********************************@4ax.com...

I noticed that Message-ID:
<11**********************@c13g2000cwb.googlegroups .com> from R. Rajesh
Jeba Anbiah contained the following:

Is it about creating 6 cards or just 1 card? Anyway, I don't find it
to be difficult if you use shuffle-pick-remove logic.

Six, and I couldn't get your version to work.

It's getting the numbers to fit on the cards that poses the problem.

Take my previous example as the starting point.

Your 90 numbers should be stored into the columns that they will appear on
the card, and just ordered randomly in those columns.

They then should be distributed in sequence into the 6 cards, so each card
will have an equal number of numbers, with either 1 or 2 numbers from each
column.

You then work out the rough co-ordinates for each number, and then detect
any conflict between numbers that are close together, i.e. 19 and 20 can't
both share column 2 row 3, 19 has to be moved to column 2 row 2.

As no column will have more than two numbers you can be assured that column
2 row 2 will be empty, so no recursive checking is nessecary.

Then you just output your card by column and row.

http://www.darrylcatchpole.net/bingo2.phps

http://www.darrylcatchpole.net/bingo2.php

For prosperity:-

<table border=1 bordercolor="#00000" cellpadding=1 cellspacing=1>
<?php

mt_srand(mktime());
class cRow {
var $aNumbers = array();
var $aBag = array();

function cRow($min, $max) {
/*
place all numbers into a bag
*/
$this->aBag = range($min, $max);
$counters = $max - $min;
for($i=$counters;$i>0;$i--)
{
/*
draw a random number out of the bag
*/
$n = mt_rand(0 , $i);
$this->aNumbers[] = $this->aBag[$n];
/*
remove from bag
*/
unset($this->aBag[$n]);
sort($this->aBag);
}
// add last number
$this->aNumbers[] = array_pop($this->aBag);
/*
the above code is actually unnessecary as array_shuffle will
pretty much achive the same results with a lot less coding
-- however knowing how to do this type of algorythmn is
important
*/

}
}

/*
get numbers 1 to 90 into an array of arrays in random order
*/
$aRows = array(
new cRow(1 , 10),
new cRow(11 , 20),
new cRow(21 , 30),
new cRow(31 , 40),
new cRow(41 , 50),
new cRow(51 , 60),
new cRow(61 , 70),
new cRow(71 , 80),
new cRow(81 , 90)
);

// print_r($aCard);

/*
create 6 cards to hold the numbers for each card
*/
$cards = array();
for($i=0;$i<6;$i++)
{
$cards[$i] = array();
}

/*
this could be a random number between 0 and 5
if you wish to change which cards get 1 or 2 numbers
in the first column
*/
$i = 0;
foreach($aRows AS $k => $oRow)
{
foreach($oRow->aNumbers AS $v)
{
/*
assign each of the numbers to the player's card
*/
array_push($cards[$i] , $v);
// move to the next card with automatic loop back
$i = ($i+1) % 6;
}
}

/*
process the cards into the pidgeon holes
*/
for($i=0;$i<6;$i++)
{
/*
numbers on the cards are in random order,
we need them in numberical order to be able
to pidgeon hole them
*/
sort($cards[$i]);
/*
create a 2 dimensional array that holds
our numbers as per a bingo playing card
i.e. $card1, $card2, $card3

can't be bothered to use a 3 dimensional boo-hoo I suck ;-)
*/
$card{$i} = array();
// take each card of numbers in turn
foreach($cards[$i] AS $v)
{
// get the value and work out the rough co-ordinates of each number
$val = sprintf('%02d' , $v);
$col = (int)substr($val, 0, 1);
$row = (int)substr($val, 1, 1);
if($row> 0 && $row < 4)
{
$row = 1;
/*
check to see if we have two numbers in the row
i.e. 11, 12 can't both go in the same
row/col, the latter one must go in the next row
*/
if(isset($card{$i}[$col][$row]))
$row = 2;
}
elseif($row > 3 && $row < 7)
{
$row = 2;
if(isset($card{$i}[$col][$row]))
$row = 3;
}
else
{
// ensure 10, 20, 30 end up in the right columns
if($col == 9)
$col--;
elseif($row == 0 && $col>0)
$col--;

$row = 3;
/*
check to see if we have two high numbers
in this col i.e. 18,19
if so, move the first one to the previous
row
*/
if(isset($card{$i}[$col][$row]))
$card{$i}[$col][2] = $card{$i}[$col][$row];

}
// we can now assign the value to it's pidgeon hole
$card{$i}[$col][$row] = $v;
}
/*
ok, time to output our card
*/
for($row = 1; $row<4; $row++)
{
print "<tr>\n";
for($col = 0; $col<9; $col++)
{
if(isset($card{$i}[$col][$row]))
$val = $card{$i}[$col][$row];
else
$val = '&nbsp;';
printf("<td>%s</td>\n" , $val);;
}
print "</tr>\n";
}
print "<tr><td colspan=9>&nbsp;</td></tr>\n";
// print_r($card{$i}) . "\n\n";
}

?>
</table>

[Geoff Berrow]

I noticed that Message-ID: <cq**********@slavica.ukpost.com> from CJ
Llewellyn contained the following:

Take my previous example as the starting point.

Your 90 numbers should be stored into the columns that they will appear on
the card, and just ordered randomly in those columns.

They then should be distributed in sequence into the 6 cards, so each card
will have an equal number of numbers, with either 1 or 2 numbers from each
column.

That's not quite right. You can have three numbers in a column but not
more than five in a row.

Take a look at my example.
www.ckdog.co.uk/php/test/bingo2.php
www.ckdog.co.uk/php/test/bingo2.phps

My solution works, but only by discarding failed attempts. I've put a
counter on there so you can see how many.

I've a gut feeling that there is a simple, elegant solution to this.
Just wish I knew what it was...

--
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/

[Pedro Graca]

Geoff Berrow wrote:

I've a gut feeling that there is a simple, elegant solution to this.
Just wish I knew what it was...

What about this other approach?
Randomly put the 90 numbers into their respective columns, not caring
whether the line gets filled or not.
After that, change random numbers from overfilled lines to underfilled
ones until all lines have five numbers.

================
<?php
header('Content-Type: text/plain');

function print_cards(&$card) {
$k = 0;
foreach ($card as $row) {
$last = 0;
foreach ($row as $n) {
if ($n) {
$group = (int)($n/10);
if ($group == 9) $group = 8;
while ($last < $group) { echo "-- "; ++$last; }
printf("%02d ", $n);
$last = $group+1;
}
}
while ($last++ < 9) echo "-- ";
echo "\n";
if ($k%3 == 2) echo "\n";
++$k;
}
echo "\n\n";
}

/* insert $n at row $index.
* return false if already occupied
*/
function insert(&$row, $index, $n) {
$col = (int)($n/10);
if ($col == 9) $col = 8;
if ($row[$index][$col]) return false;
$row[$index][$col] = $n;
return true;
}

function all_rows_have_five_elements(&$x) {
foreach ($x as $v) if ($v != 5) return false;
return true;
}

function rowcol_has_number(&$x, $r, $c) {
return ($x[$r][$c] != 0);
}

function elems(&$arr) {
$num = 0;
foreach ($arr as $x) {
if ($x) ++$num;
}
return $num;
}

/* initialize $row structure
*/
for ($i=0; $i<18; ++$i) $row[$i] = array_fill(0, 9, 0);

/* distribute number to columns
* without caring about 5 numbers per row
*/
$number = range(1, 90);
while (!empty($number)) {
$i = array_pop($number);
$index_row = rand(0, 17);
while (!insert($row, $index_row, $i)) {
++$index_row;
if ($index_row == 18) $index_row = 0;
}
}

# /* debugging */
# echo "First pass:\n\n";
# print_cards($row);

/* calculate how many numbers are in each row
*/
for ($i=0; $i<18; ++$i) {
$row_size[$i] = elems($row[$i]);
}

/* redistribute numbers
*/
while (!all_rows_have_five_elements($row_size)) {
/* pick a row with 6 or more elements */
$source = rand(0, 17);
while ($row_size[$source] < 6) {
++$source;
if ($source == 18) $source = 0;
}

/* pick a row with 4 or less elements */
$destin = rand(0, 17);
while ($row_size[$destin] > 4) {
++$destin;
if ($destin == 18) $destin = 0;
}

/* pick a column from source that is empty on destin */
$col = rand(0, 8);
while (!((rowcol_has_number($row, $source, $col)) && (!rowcol_has_number($row, $destin, $col)))) {
++$col;
if ($col == 9) $col = 0;
}

/* swap them */
$row[$destin][$col] = $row[$source][$col];
$row[$source][$col] = 0;
++$row_size[$destin];
--$row_size[$source];
}

print_cards($row);
?>
--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

[Jerry Stuckle]

I know this thread is old - but I don't get over here much, and this
presented an interesting challange.

It is possible to get random cards with no collision or overflow
detection if you shuffle properly. Try this code (sorry for any word
wrap):

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd"><HEAD>
<title>Bingo Card</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css">
table {margin: 10px auto; border: 2px solid black }
caption { margin: 0 auto }
td { width: 30px; text-align: center; border: 1px solid black }
</style>
</HEAD>

<body>
<?

srand((float)microtime() * 1000000);

// Create and fill the initial array of numbers
$numbers = range(1, 90);
for ($i = 0; $i < 90; $i++)
$numbers[$i] = $i+1;
shuffle($numbers);

// Create the bingo card
//$card = array(array(), array(), array()); // 3 rows
$cards = array( array(array(), array(), array()), // 3 rows per card
array(array(), array(), array()),
array(array(), array(), array()),
array(array(), array(), array()),
array(array(), array(), array()),
array(array(), array(), array()) ); // 6 cards

for ($card = 0; $card < 6; $card++) { // For each card
for ($row = 0; $row < 3; $row++) { // Each row in a card
for ($cell = 0; $cell < 5; $cell++) // First 5 boxes in each row
$cards[$card][$row][$cell] = array_pop($numbers);

for ($cell = 5; $cell < 9; $cell++)
$cards[$card][$row][$cell] = '&nbsp;'; // Empty the rest of each
row

shuffle($cards[$card][$row]); // Shuffle the row contents

for ($cell1 = 0; $cell1 < 9; $cell1++) // Finally sort the numbers
in the row
for ($cell2 = $cell1+1; $cell2 < 9; $cell2++) // Use a simple
swap sort since it's a small array
if (is_numeric($cards[$card][$row][$cell1]) &&
is_numeric($cards[$card][$row][$cell2])) // Ignore blank boxes
if ($cards[$card][$row][$cell1] > $cards[$card][$row][$cell2])
{
$temp = $cards[$card][$row][$cell1];
$cards[$card][$row][$cell1] = $cards[$card][$row][$cell2];
$cards[$card][$row][$cell2] = $temp;
}
}
}
// Now display the cards
for ($card = 0; $card < 6; $card++) {
echo "<table>\n" .
'<caption>Bingo Card ' . ($card+1) . "</caption>\n";
for ($row = 0; $row < 3; $row++) {
echo "<tr>\n";
for ($cell = 0; $cell < 9; $cell++)
echo '<td>' . $cards[$card][$row][$cell] . "</td>\n";
echo "</tr>\n";
}
echo "</table>\n";
}
?>

</body>
</html>

--

To reply, delete the 'x' from my email
Jerry Stuckle,
JDS Computer Training Corp.
js*******@attglobal.net
Member of Independent Computer Consultants Association - www.icca.org