Logo by LAR2 - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. October 28, 2020, 09:35:26 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: 90 number bingo ticket algorithm?  (Read 5874 times)
Description: Anyone work out a good way to do this?
0 Members and 1 Guest are viewing this topic.
simon.snake
Fractal Bachius
*
Posts: 640


Experienced Fractal eXtreme plugin crasher!


simon.fez SimonSideBurns
« on: January 23, 2013, 05:30:48 PM »

Hi

I wrote a BBC BASIC program to generate UK style 90 number bingo tickets.

For those of you who don't know what these look like, here's a description.

On one page are 6 grids, one above the next with a gap between.  Each grid is 9 cells wide by 3 cells deep.

The numbers 1 to 90 are used once only.  In the first column are the numbers 1 to 9, the second column has numbers 10 to 19, etc, all the way to the 9th column which has numbers 80 to 90 in it.

Now there are some constraints, and these are the bit where it becomes almost impossible to fill the grid in one pass without having to swap some cells or starting again.

I've tried to draw up some grids with a pen and paper and fill them manually but it gets quite difficult near the end.

The constraints are:

1) Every row must have exactly 5 numbers in it.
2) The 3 cell high column in each ticket must have between 1-3 numbers in it but never zero numbers.
3) In each 3 cell high column, the numbers are sorted with lower numbers higher than larger numbers.
4) All the numbers 1 to 90 are used only once in each set of 6 tickets.

The method I have tried is as follows:

1) Loop 9 times through:
2) Pick a column randomly that hasn't been completed already.
3) Fill random positions in the whole set of 6 tickets within that column with the numbers that are in that column, checking that there are not already 5 numbers in that row.
4) After placing all numbers, check there are no tickets with zero numbers in that column.
5) A few other space checks
6) If there are any errors we delete the numbers placed and go back to step 3.
7) Mark column as completed.
cool Until all columns are completed.

This is quite quick, but is using a brute force approach to achieve the goal. I'd like to re-think the algorithm to make sure it is guaranteed that it completes first time every time without having to erase numbers and try again, but I just can't think how this would be achieved.

Anyone fancy a non-fractal related challenge of trying to do better.  It doesn't need to be written in BASIC, essentially any language is fair game.

I have a suspicion that even APL would have been able to do this, but I have only ever scratched the surface of examining this language.

Simon
Logged

To anyone viewing my posts and finding missing/broken links to a website called www.needanother.co.uk, I still own the domain but recently cancelled my server (saving ú30/month) so even though the domain address exists, it points nowhere.  I hope to one day sort something out but for now - sorry!
simon.snake
Fractal Bachius
*
Posts: 640


Experienced Fractal eXtreme plugin crasher!


simon.fez SimonSideBurns
« Reply #1 on: January 23, 2013, 07:39:51 PM »

I forgot to mention (but it was covered by constraint 1) that each ticket has exactly 15 numbers on it.
Logged

To anyone viewing my posts and finding missing/broken links to a website called www.needanother.co.uk, I still own the domain but recently cancelled my server (saving ú30/month) so even though the domain address exists, it points nowhere.  I hope to one day sort something out but for now - sorry!
Mark Henderson
Forums Newbie
*
Posts: 1


« Reply #2 on: June 27, 2013, 07:27:19 PM »

Wound up working on this same problem and didn't see any decent solutions online.  Posting the one I came up with for posterity:

the algorithm is split into 2 parts.

First, generate 6 valid sets of 15 numbers
Second, distribute a set of 15 numbers into a card.


for the first part:

1) assign one number from each of the 9 columns into each of the 6 cards.
after that, you'll have 3 numbers left in the first column, 5 in the last column, and 4 in every other column.

2) assign one of the numbers in the last column to a random card.

3) now make 4 passes over the remaining columns.  In each pass, assign 1 of the remaining numbers for that column to a random card, skipping cards that are already full or have 3 numbers from that column.
  In the first three passes, I'm maxing out at 2 numbers per column instead of 3.  This prevents it from running into a corner case where it can't finish successfully, but reduces the chance of having a full column.

This satisfies the below requirements:
1) at least 1 number in each column on each card
2) at most 3 numbers in each column on each card
3) 15 numbers per card
4) all 90 numbers are used


part two of the algorithm is to distribute a valid set of 15 numbers to a card.

I do this in three passes.  on each pass, I construct one row.
First I check for a column that has to fit (3 numbers left on 1st row, 2 left on 2nd row, 1 left on last row).
Then I just fill the card randomly from the remaining numbers (checking to make sure I'm not repeating a column)

 
Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Number 1st Annual Fractal Art Competition 2008 (Completed) fractalwizz 2 2082 Last post April 09, 2008, 02:47:22 AM
by fractalwizz
Something Number 1 Mandelbulb 3d blob 5 1773 Last post July 04, 2010, 11:23:11 PM
by kram1032
Something Number 2 Mandelbulb 3d blob 0 1172 Last post April 29, 2010, 08:43:12 PM
by blob
Something Number 3 Mandelbulb 3d blob 0 1006 Last post April 29, 2010, 08:47:03 PM
by blob
Three number lines Images Showcase (Rate My Fractal) Eric B 0 628 Last post May 27, 2012, 06:36:00 PM
by Eric B

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.112 seconds with 28 queries. (Pretty URLs adds 0.006s, 2q)