Skip to content

Instantly share code, notes, and snippets.

@zeeshansayyed
Last active October 27, 2017 22:18
Show Gist options
  • Save zeeshansayyed/f421ad08989d54fa7f5e3a59f1af093c to your computer and use it in GitHub Desktop.
Save zeeshansayyed/f421ad08989d54fa7f5e3a59f1af093c to your computer and use it in GitHub Desktop.
A simply 3 x 3 bingo simulator!
# -*- coding: utf-8 -*-
"""
Zeeshan Ali Sayyed
Oct 27, 2017
Challenge: Create a 3x3 bingo board using integers in [1,20]. You may use the same integer more than once.
We will then play bingo as follows:
In each turn of the game, we will roll two six sided dice and add the results. We will mark one square on your
bingo board if you have at least one unmarked square that is a multiple of the total rolled (if more than one unmarked
square is a multiple of the total, we will pick one at random). We will take turns until at least one board has
bingo (3 marks in a row, horizontal, vertical, or diagonal). Each player whose board has bingo gets a share of the win
(if n players get bingo, then each gets 1/n wins). We will simulate 10,000 games using all the bingo boards submitted.
The goal is to get the most wins out of all contestants.
Submit your answer as an integer vector of length 9 - where the first element is placed in the top left box on the bingo
board and then reading left to right across the top row and then left to right across the middle row and then left to
right across the bottom row. Also submit a very brief description of how you arrived at your answer and why you think your
board will win. We are interested in your thought process and how you considered different angles to the game as much as
how well your submission does compared with other contestants.
"""
import numpy as np
from pandas import Series
from scipy.stats import rv_discrete
from collections import Counter
import cPickle as pickle
def factors(n):
return set(reduce(list.__add__,
([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
def generate_die_distribution(dice_low=1, dice_high=6, n_dice=2):
"""
Generates probability distribution of the total value when 'n_dice' die
are thrown. dice_low is the lowest value on the dice and dice_high is
the highest value on the dice. All the numbers in between are assumed
to be present on the dice
"""
die_range = np.arange(dice_low * n_dice, dice_high * n_dice + 1)
dist = Series(data=np.zeros_like(die_range), index=die_range)
for i in range(100000):
dice_total = np.sum(np.random.randint(dice_low, dice_high+1, size=n_dice))
dist[dice_total] += 1
dist /= np.linalg.norm(dist, ord=1)
return dist
def generate_bingo_distribution(bingo_low=1, bingo_high=20):
"""
Generates the probability distribution of all the valid numbers
in a given bingo board. 'low' is the lowest number allowed in the
bingo board and 'high' is the highest number allowed on the
bingo board. It is assumed that all numbers in between are also
valid
"""
bingo_range = range(bingo_low, bingo_high + 1)
die_dist = generate_die_distribution()
bingo_dist = Series(data=np.zeros_like(bingo_range), index=bingo_range,
dtype='float64')
for i in bingo_dist.keys():
a = list(factors(i))
for j in a:
if j in die_dist:
bingo_dist[i] += die_dist[j]
bingo_dist /= np.linalg.norm(bingo_dist, ord=1)
return bingo_dist
# Simulation code begins here.
# We will have a dictionary called boards = {}. Keys will be board IDs and
# values will be actually 3 x 3 numpy arrays representing numbers
# We will have another dictionary called marked_boards={}. The keys will be
# the same as those of boards. The values are also 3 x 3 numpy array. But instead
# of numbers on a bingo board, they will only have 1's and 0's denoting whether
# a number was marked or not.
def generate_random_boards(low=1, high=20, board_size=9, dist='custom', n=100):
"""
This is an ongoing implementation. For now it genrates 'n' number of random
boards. These boards have the specified low and high values and the
board size. Finally, currently the boards aren't generated randomly.
But they are generated according to the probability distrubtion
returned by `generate_bingo_distribution`
params dict has 3 keys:
'b' -> boards dictionary
'mb' -> marked_boards dictionary
's' -> scores dictionary
"""
boards = {}
marked_boards = {}
scores = {}
if dist == 'custom':
dist = generate_bingo_distribution(bingo_low=low, bingo_high=high)
xk = range(1, 21)
pk1 = (0, 0.01, 0.019, 0.038, 0.038, 0.075, 0.057, 0.083, 0.056, 0.074, 0.019,
0.112, 0, 0.066, 0.056, 0.083, 0, 0.112, 0, 0.102)
pk2 = [1/16.] * 20
pk2[0], pk2[12], pk2[16], pk2[18] = [0.0] * 4
generator = rv_discrete(name='custom', values=(xk, pk2))
for i in range(n):
boards[i] = generator.rvs(size=board_size)
marked_boards[i] = np.zeros(board_size)
scores[i] = 0.0
params = {}
params['b'] = boards
params['mb'] = marked_boards
params['s'] = scores
return params
def add_custom_board(a, params):
"""
Once you have a set of boards generated for simulation, you can add your
own board to the set. Just pass in a python list in a and the params
dictionary containing the generated boards
for e.g. add_custom_board([1, 2, 3, 4, 5, 6, 7, 8, 9], my_params)
The function returns the ID of your board. Note it down to see results
"""
i = len(params['b'])
params['b'][i] = np.array(a)
params['mb'][i] = np.zeros(len(params['mb'][0]))
params['s'][i] = 0.0
return i
def reset_params(params, what='marks'):
"""
This function takes in a dictionary called params, which itself contains
3 more dictionaries: boards, marked_boards and scores. It keeps all the
indices and boards, same as before. It only resets all marked_boards
and scores to zeros again ! Then returns the params
"""
b = params['b']
board_size = len(b[0])
mb = params['mb']
s = params['s']
for i in b.keys():
if what == 'marks':
mb[i] = np.zeros(board_size)
elif what == 'scores':
s[i] = 0.0
elif 'both':
mb[i] = np.zeros(board_size)
s[i] = 0.0
def check_board(board_marks):
"""
This function checks whether the passes array has achieved bingo!
It takes a numpy array of shape (9,). I know this is a weird shape.
But if you generate something without specifying a complete shape,
this is what you get. for e.g. np.zeros(9) or
np.random.randint(0, 2, size=9)
"""
assert(board_marks.shape == (9,))
board_marks = board_marks.reshape(3, 3)
if 3 in np.sum(board_marks, axis=0):
return True
elif 3 in np.sum(board_marks, axis=1):
return True
elif np.trace(board_marks) == 3:
return True
elif np.trace(np.fliplr(board_marks)) == 3:
return True
else:
return False
def check_bingo(marked_boards):
"""
This function checks all the marked_boards in the the dictionary
which is input and returns a list of all the indices which have reached
Bingo! If none of the boards has reached bingo, it will return an
an empty list
"""
bingo_boards = []
for index in marked_boards.keys():
if check_board(marked_boards[index]):
bingo_boards.append(index)
return bingo_boards
def simulate_turn(boards, marked_boards, dice_score):
"""
# Given a 1x9 numpy array this method
# will roll 2 dice and mark an index as 1
# board will be board[i]
# marked_board will be marked_board[i]
"""
for i in boards:
choices = []
for j in range(len(boards[i])):
if boards[i][j] % dice_score == 0:
choices.append(j)
if len(choices) > 0:
choice = np.random.choice(choices)
marked_boards[i][choice] = 1
def simulate_game(params, dice_low=1, dice_high=6, n_dice=2):
boards = params['b']
marked_boards = params['mb']
scores = params['s']
bingo_boards = []
while len(bingo_boards) == 0:
dice_total = np.sum(np.random.randint(dice_low, dice_high+1, size=n_dice))
simulate_turn(boards, marked_boards, dice_total)
bingo_boards = check_bingo(marked_boards)
update = 1./len(bingo_boards)
for i in bingo_boards:
scores[i] += update
return scores
def run_simulation(params, nrounds=10, verbose=False):
reset_params(params, what='scores')
for i in range(nrounds):
if verbose:
if i % 100 == 0:
print i,
current_scores = simulate_game(params)
reset_params(params, what='marks')
return params['s']
def print_results(params, top=10):
"""
Prints results i.e. ID, board and scores of the 'top' boards
"""
winners = Counter(params['s']).most_common(top)
for i in winners:
print i, params['b'][i[0]]
def test():
p = generate_random_boards(n=5)
return run_simulation(p)
# Out[453]:
# Counter({0: 21.333333333333332,
# 1: 6.5,
# 2: 35.0,
# 3: 27.499999999999996,
# 4: 9.666666666666668})
# The following will be moved onto the main method later on
if __name__ == "__main__":
all_params = []
for i in range(3):
print "Simulation number:",str(i), "-> ",
params = generate_random_boards(n=100)
add_custom_board([12] * 9, params)
add_custom_board([18] * 9, params)
add_custom_board([6,12,14,10,18,8,7,20,16], params)
run_simulation(params, nrounds=10000, verbose=True)
all_params.append(params)
print ""
@zeeshansayyed
Copy link
Author

print_results(p1)
(45, 216.94266289266213) [20 3 5 18 14 15 8 7 12]
(59, 208.36725635475568) [10 14 14 11 15 18 4 5 16]
(20, 201.48861555111552) [14 6 11 8 14 6 12 3 20]
(55, 198.00392883260508) [14 14 16 20 12 11 4 18 9]
(23, 197.14629953379918) [15 6 18 20 7 18 8 16 12]
(8, 196.77758352758292) [ 9 7 10 20 18 14 8 12 8]
(33, 196.72906578715398) [11 8 2 20 9 12 5 14 3]
(102, 194.35566418875197) [ 6 12 14 10 18 8 7 20 16]
(87, 188.51435549744343) [15 7 12 18 8 12 11 15 14]
(6, 186.93929722238525) [ 9 15 12 11 15 14 8 8 6]

print_results(all_params[1])
(65, 330.27185910494677) [16 9 18 12 20 11 14 3 10]
(41, 282.5223137973133) [11 7 8 3 9 6 8 7 10]
(54, 250.85656288156284) [16 8 11 6 12 7 10 9 10]
(64, 236.70412504162476) [ 9 11 8 6 7 18 10 18 10]
(25, 233.9058746808747) [11 20 14 16 9 12 12 3 2]
(102, 232.15322177822165) [ 6 12 14 10 18 8 7 20 16]
(81, 202.93526514335284) [14 20 18 16 8 14 11 3 16]
(26, 202.4422188922188) [ 5 11 14 12 20 8 2 14 5]
(11, 191.29030691530693) [15 12 18 16 11 8 14 2 15]
(90, 184.35274627333416) [14 10 12 8 18 2 12 4 14]

print_results(all_params[2])
(16, 284.8392102780256) [ 7 14 18 6 16 11 18 4 10]
(19, 252.5251539095575) [10 12 9 8 11 14 16 7 14]
(88, 231.4567071817065) [10 18 18 16 18 11 7 18 6]
(25, 218.97254222385777) [ 3 7 12 2 14 16 7 7 20]
(102, 208.34714631773443) [ 6 12 14 10 18 8 7 20 16]
(61, 198.3003653209527) [16 15 5 10 14 18 11 11 12]
(23, 193.39920773670744) [ 7 9 11 12 11 11 8 20 20]
(94, 191.70930180930145) [ 8 6 3 8 18 14 10 11 5]
(73, 191.34558497058484) [ 3 8 6 7 20 20 11 18 2]
(98, 183.49528567837348) [12 11 10 4 12 9 4 11 14]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment