Thiago Cafe - Programming is fun !
Created by thiago on 2017-02-24 07:50:11

Bingo - shuffling the balls

This christmas was way different than the previous christmas. I moved from Brasil to Canada and for the first time I was away from my family, but with some very good friends.

Some of those friends play Bingo during x-mas night, instead of exchanging gifts and we played - my daughters loved! So, today out of nowhere, she came up with the idea of playing bingo. She built some bingo cards and she wanted me to play the numbers.

hum... We don't have balls, but we have a computer. So I decided to write a python script to shuffle the balls.

It should shuffle them, but with some interesting requirements.

How to shuffle

We have a set of balls, from 1 to 75, and we need to shuffle them all. I have some choices

Use some random algorithm and compare the number with a set of balls already played

Terrible idea ! This will go crazy when my set gets close to the total number of balls.

Imagine - Please don't do it !

rnd_num = randint()
while rnd_num not in my_set:
    rnd_num = randint()

As I said, terrible idea. Let's move to the next.

Find closest available numbers

Let me introduce the worldwide famous Thinaso algorithm! (Thiago naive shuffling algorithm)

It looks much more interesting. Steps:

  1. Create a vector of available balls
  2. Randomly pick positions and get the ball number
  3. If the position is used, go to the next available
  4. If the next available is used, go to previous available
  5. If is used, continue to next/previous
  6. If all vector of balls is used, return 0
  7. Otherwise, mark the position value as 0

Writing the algorithm

First, let's write the seeking function. It will find the closest available position.

Searching, seek and destroy

It gets a number from the vector if position is valid

def get_single_number(nums, pos):
  if pos >= 0 and pos < len(nums):
    return nums[pos]
  return 0

Now, let's write the method that gets the number from the vector

def get_number(nums, pos):

First we try to get the number in the provided position and if the value is not available (marked as 0), we go to the right and to the left.

pr = pos+1
pl = pos-1
while get_single_number(nums, pos) == 0:
  pos = pr
  pr += 1
  if get_single_number(nums, pos) == 0:
    pos = pl
    pl -= 1

If when running to the right and left we found something, let's mark the position as used and return the value

n = nums[pos]
if n != 0:
  nums[pos] = 0
return n

Shuffling the numbers

The complex part has gone already. Now we need to get all the balls in random order.

def shuffle_numbers(nums):
  import random
  random.seed()
  ret = []
  total = len(nums)
  for i in range(0, total):
    pos = random.randint(0, total-1)
    n = get_number(nums, pos)
    ret.append(n)
  
  return ret

IMPORTANT !

Here if we have duplicated results from randint, as I am getting the closest positions, to each random I generate, I will have a different number from my sequenced vector and add the resulting number incrementally to my results.

Does it work ? Show me !

Using is very simple.

print shuffle_numbers(range(1, 76)) #[)

There is something interesting is this algorithm. I can shuffle the numbers inside my set.

print shuffle_numbers([2, 4, 6, 8, 10, 12]) #custom list
print shuffle_numbers(range(1, 5) + range(6, 10)) #list without 5

...

I hope you enjoyed reading as much as I enjoyed writing this very famous algorithm !

Source code: sorting/thinaso.py

Any comments or questions, compliments ?

Reach me on twitter - @thiedri

...

Other comments

No comments !