# Slightlly OT - Bingo problem - Page 2

•  Subject
• Author
• Posted on

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
Jeba Anbiah contained the following:

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 /

## Re: Slightlly OT - Bingo 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:-

<?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);
}
\$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 = 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[\$col][\$row]))
\$row = 2;
}
elseif(\$row > 3 && \$row < 7)
{
\$row = 2;
if(isset(\$card[\$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[\$col][\$row]))
\$card[\$col][2] = \$card[\$col][\$row];

}
// we can now assign the value to it's pidgeon hole
\$card[\$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[\$col][\$row]))
\$val = \$card[\$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) . "\n\n";
}

?>
</table>

## Re: Slightlly OT - Bingo problem

Llewellyn contained the following:

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 /

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

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

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 /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
contained the following:

Well that certainly works.  Do you think it is faster than my version?
--
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 /

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

bingo\$ time for((id=0; id<100; ++id)); do php GB.php > /dev/null; done

real    0m13.691s
user    0m12.710s
sys     0m0.950s

bingo2.php is my version

bingo\$ time for((id=0; id<100; ++id)); do php bingo2.php > /dev/null; done

real    0m6.509s
user    0m5.510s
sys     0m1.000s

Of course these times are not trustworthy, but they "confirm" the
feeling I had when running your browser version against my CLI version.

I had the same results for the few times I run the test. So it appears
my version is twice as fast as yours.

Can't verify Rajesh's version now -- will do later, when I get home.

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

.oO(R. Rajesh Jeba Anbiah)

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

## Re: Slightlly OT - Bingo problem

Michael Fesser wrote:

slots
Easy.

Thanks, now only I understood the question clearly. Yes, it's really
hard to get 6 random cards without collision detection and overflow
checking.

I somehow managed to solve it with kind of "pseudo" random cards. It
seems to be matching Professor's conditions (I took 0 to 89 for
brevity). For "real" random cards, I think collision detection is
unavoidable unless we find the distribution.

<?php
for(\$i = 0; \$i < 9 ; ++\$i)
{
\$rand_tbl[\$i] = range(\$i * 10, \$i * 10 + 9);
shuffle(\$rand_tbl[\$i]);
}
// print_r(\$rand_tbl);
\$row_handle = range(0, 17); //18-1
shuffle(\$row_handle);
// print_r(\$row_handle);
for(\$i = 0; \$i < 18; ++\$i)
\$card_arr[\$i] = array_fill(0, 9, '');
// print_r(\$card_arr);
for(\$col = 0; \$col < 9; ++\$col)
{
for(\$r = 0; \$r < 10; ++\$r)
{
\$row = array_shift(\$row_handle);
\$row_handle[] = \$row;
// echo \$row."\n";
// print_r(\$row_handle);
\$card_arr[\$row][\$col] = array_pop(\$rand_tbl[\$col]);
}
}
// print_r(\$card_arr);
echo '<pre>' . "\n";
for(\$row = 0; \$row < 18; ++\$row)
{
for(\$col = 0; \$col < 9; ++\$col)
printf(" %2s ", \$card_arr[\$row][\$col]);
echo "\n";
if (\$row % 3 == 2)
echo "\n";
}
echo '</pre>' . "\n";
// print_r(\$rand_tbl);
?>

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

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
Jeba Anbiah contained the following:

I get the same distribution when I refresh. Is that supposed to happen?

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

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:
<snip>

happen?

Not sure, what do you mean by distribution here; in one sense, it is
same (can be seen when commenting out shuffle statements). Since,
shuffle plays a major role here, it is hard to guess the logic behind
(I hope). In your case, it may a browser cache problem? Not to mention,
for me, it is generating random cards (as per your conditions(?)). Let
me add some samples: (Tried to fool GG by prepending "-" so that it
won't mess up formatting. But, still not sure about GG).
One:
-     10      34      53      73  83
-  6      27  38      57      79
-     15      37      52  66      82

-  5      26      40      69  76
-  7      23      47      67      89
-  0  16      32      58      78

-     19      30      50      71  88
-     12  20      44      61      80
-     14  28      45      64      87

-     17      31  43      60      86
-  4      29      42      65      81
-  3      22      46  54      70

-     18      33  49      63      84
-  8      21      48      62  77
-     11      35      55  68      85

-  9      25  36      59      72
-  1  13      39      51      75
-  2      24      41  56      74

-------
Two:

-  7  19      30      53      77
-  2      29      41      67  76
-  5      28      42      60  73

-  1      27      40  54      70
-  3  16      32      52      79
-     18      39      58  64      84

-     12      34  49      65      81
-     15  21      43      62      89
-  8      26  31      55      74

-  9      24  33      56      78
-     17  25      44      63      86
-     10      36      51      75  80

-     11      35      50      72  87
-  0      20      46      61      85
-  6      23      45      69      88

-     13      38      59  66      82
-  4      22      47  57      71
-     14      37  48      68      83

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

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
Jeba Anbiah contained the following:

It's this local setup.  I don't know why.  I'm running php 4.3
Works fine here http://www.ckdog.co.uk/php/test/bingo_raj2.php
--
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 /

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

Rajesh
behind
mention,

Probably any museum version that requires seed
<http://in.php.net/shuffle

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

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

Rajesh
behind
mention,

Probably any museum version that requires seed
<http://in.php.net/shuffle

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

## Re: Slightlly OT - Bingo problem

R. Rajesh Jeba Anbiah wrote:
<snip double post>

Damn! Even though I didn't do anything GG posted it twice.

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

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
Jeba Anbiah contained the following:

Well even running the example code[1], it doesn't seem to work very
well.  Here is the output of five refreshes

17 3 19 2 20 14 18 10 6 13 5 9 4 15 7 11 1 16 8 12
18 3 17 2 20 14 19 10 6 13 5 9 4 15 7 11 1 16 8 12
17 3 19 2 20 14 18 10 6 13 5 9 4 15 7 11 1 16 8 12
18 3 17 2 20 14 19 10 6 13 5 9 4 15 7 11 1 16 8 12
18 3 17 2 20 14 19 10 6 13 5 9 4 15 7 11 1 16 8 12

[1]
<?php
\$numbers = range(1, 20);
srand((float)microtime() * 1000000);
shuffle(\$numbers);
while (list(, \$number) = each(\$numbers)) {
echo "\$number ";
}
?>

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

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

Rajesh
<snip>

Then, perhaps you may need to consider some custom versions like
<http://in.php.net/shuffle#46853

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

## Re: Slightlly OT - Bingo problem

R. Rajesh Jeba Anbiah wrote:

Nice simmetric solution!
Pity the problem isn't simmetric :-)

My first hack to make it go from 1 to 90 failed miserably:

<?php
for (\$i=0; \$i<9; ++\$i) {
\$rand_tbl[\$i] = range(\$i*10+((\$i==0)?(1):(0)), \$i*10+9+((\$i==8)?(1):(0)));
/* no more changes */

The timings for your original (broken) version:

bingo\$ time for((id=0; id<100; ++id)); do php RRJ2.php > /dev/null; done

real    0m5.861s
user    0m4.930s
sys     0m0.930s

So, your (broken [SCNR]) version is about 11% faster than mine (if you
chose to trust the timings).

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

Pedro Graca wrote:

It

Unfortunately, it is symmetric and obviously broken. Without testing
collision and overflow, I don't think it will be possible to get "real"
random cards as you generated.

\$i*10+9+((\$i==8)?(1):(0)));

To make it work for 1 to 90 kind of pattern, it requires more hacks.
Your hack will leave one row with just 4 elements. It's obvious as the
random hash table length becomes uneven (9, 10, 10...11).

Here is fixed version for 1 to 90.

<?php
\$rand_tbl[0] = range(1, 9);
shuffle(\$rand_tbl[0]);
for(\$i = 1; \$i < 8 ; ++\$i)
{
\$rand_tbl[\$i] = range(\$i * 10, \$i * 10 + 9);
shuffle(\$rand_tbl[\$i]);
}
\$rand_tbl[8] = range(80, 90);
shuffle(\$rand_tbl[8]);
// print_r(\$rand_tbl);
\$orig_rand_tbl = \$rand_tbl;
\$row_handle = range(0, 17); //18-1
shuffle(\$row_handle);
// print_r(\$row_handle);
for(\$i = 0; \$i < 18; ++\$i)
\$card_arr[\$i] = array_fill(0, 9, '');
// print_r(\$card_arr);
for(\$col = 0; \$col < 9; ++\$col)
{
for(\$r = 0, \$r_max = count(\$orig_rand_tbl[\$col]); \$r < \$r_max;
++\$r)
{
\$row = array_shift(\$row_handle);
\$row_handle[] = \$row;
\$card_arr[\$row][\$col] = array_pop(\$rand_tbl[\$col]);
}
}
// print_r(\$card_arr);
echo '<pre>' . "\n";
for(\$row = 0; \$row < 18; ++\$row)
{
for(\$col = 0; \$col < 9; ++\$col)
printf(" %2s ", \$card_arr[\$row][\$col]);
echo "\n";
if (\$row % 3 == 2)
echo "\n";
}
echo '</pre>' . "\n";
//print_r(\$rand_tbl);
?>

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

## Re: Slightlly OT - Bingo problem

R. Rajesh Jeba Anbiah wrote:

I only "studied" your version after trying that stupid hack.

Runs at about the same speed as the previous version. Well done! :-)

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

Pedro Graca wrote:
<snip>

Thanks :-)

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