Slightlly OT - Bingo problem

**Dani CS** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:[color=blue]
> 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.[/color]

I guess you mean three rows and nine columns (so that 5 numbers in each
row sum up to 15 numbers per card).
[color=blue]
>
> 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.
>[/color]

<snip>
[color=blue]
>
> 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?[/color]

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?
[color=blue]
>
> Please help this poor lecturer stay one step ahead of his students. :-)
>
>[/color]

**Michael Fesser** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

.oO(Geoff Berrow)
[color=blue]
>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?[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:[color=blue]
> 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?
>[/color]

Something like this?

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

JW

**Michael Fesser** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

.oO(Michael Fesser)
[color=blue]
>A quick 'n dirty hack:
>[...][/color]

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

Micha

**Geoff Berrow** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <41c4101a$0$742 60$ee9da40f@new s.euronet.nl>
from Janwillem Borleffs contained the following:
[color=blue][color=green]
>> 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?
>>[/color]
>
>Something like this?
>
>http://www.jwscripts.com/playground/bingo.phps[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <cq131r$uq4$1@n ews.ya.com> from Dani CS
contained the following:
[color=blue]
>I guess you mean three rows and nine columns (so that 5 numbers in each
>row sum up to 15 numbers per card).
>[/color]
Doh! Yes of course. I've been working on this too long...[color=blue][color=green]
>>
>> 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.
>>[/color]
>
><snip>
>[color=green]
>>
>> 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?[/color]
>
>This solution seems trivial to me, so it must be wrong:[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <slm8s09kdkqli9 kisv32l38mmv00m h44ka@4ax.com>
from Geoff Berrow contained the following:
[color=blue][color=green]
>>Something like this?
>>
>>http://www.jwscripts.com/playground/bingo.phps[/color]
>
>Nice but I forgot to give you all some information.[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

On Sat, 18 Dec 2004 09:57:50 +0000, Geoff Berrow <blthecat@ckdog .co.uk> wrote:
[color=blue]
>Please help this poor lecturer stay one step ahead of his students. :-)[/color]

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

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

**Michael Fesser** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

.oO(Geoff Berrow)
[color=blue]
>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?[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:[color=blue]
> However, it also prints the same cards each time.[/color]

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:

PHP: mt_srand - Manual

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

Seeds the Mersenne Twister Random Number Generator

JW

**Pedro Graca** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

Michael Fesser wrote:[color=blue]
> .oO(Geoff Berrow)[color=green]
>>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?[/color]
>
> 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.[/color]

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(&$c ards) {
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($ca rds); exit();
}
}
}

print_cards($ca rds);
?>

--
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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <57b9s0dlt64jlh ijdb6sh7ggab7ml g1elb@4ax.com>
from Michael Fesser contained the following:
[color=blue]
>* Get a number.
>* Determine its column.
>* Put it in the first row that has less than 5 numbers.
>* Move on to the next number.[/color]

That's what my solution does.[color=blue]
>
>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.[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <41c4b67f$0$566 22$1b2cd167@new s.euronet.nl>
from Janwillem Borleffs contained the following:
[color=blue]
>Geoff Berrow wrote:[color=green]
>> However, it also prints the same cards each time.[/color]
>
>Actually it doesn't (try http://www.jwscripts.com/playground/bingo.php).[/color]

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** · Jul 17 '05, 10:05 AM

Re: Slightlly OT - Bingo problem

I noticed that Message-ID: <eec9s0tl8u49h9 gnd14kfhi8eeob8 5drsg@4ax.com>
from Andy Hassall contained the following:
[color=blue][color=green]
>>Please help this poor lecturer stay one step ahead of his students. :-)[/color]
>
> I think he might have caught on to the trick - there's a Bingo post on
>alt.comp.lang. php ;-)[/color]

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/

Slightlly OT - Bingo problem

Slightlly OT - Bingo problem

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment