Welcome, guest | Sign In | My Account | Store | Cart

How to build dobble as a Mixed Integer program. (Python recipe) by alexander baker
ActiveState Code (http://code.activestate.com/recipes/580641/)

A simple script to replicate the cards and symbols for the dobble game.

Python, 100 lines
Download
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
"""

Example script to try and replicate the Dobble game.

1. setup our decision variables, all symbols can potentially be allocated
to each card.

Card_0_Symbol_0_Card_1 = 0 (symbol is not the card 0)
Card_0_Symbol_0_Card_0 = 1 (symbol is on the card)

Author: Alexander Baker April 2016

"""
from collections import OrderedDict

# import PuLp modeler functions
from pulp import *

def check(card0, card1):
	return int(card0.split('_')[1]) != int(card1.split('_')[1])

#Create a prob variable to contain the problem data
prob = LpProblem('Dobble Card Game', LpMinimize)

# Set the number of symbols to 50
m = 50
# Set the number of cards to 55
n = 57
# Set the number of symbols per card
z = 8

Symbol = ['Symbol_%d'%(i) for i in xrange(0, m)]

# Setup Card list
Card = ['Card_%d'%(i) for i in xrange(0, n)]

card_symbol = []
for card0 in Card:
	for s in Symbol:
		for card1 in Card:
			if check(card0, card1):
				card_symbol.append('%s_%s_%s'%(card0,s,card1)) 

symbol_card_var = LpVariable.dicts("CardSymbolCard", \
                                card_symbol, \
                                lowBound=0, \
                                upBound=1, \
                                cat='Integer')

for c0 in Card:
	prob += lpSum([symbol_card_var['%s_%s_%s'%(c0, s, c1)] \
				for s in Symbol \
					for c1 in Card \
						if check(c0, c1)]) == z

for c0 in Card:
	for s in Symbol: \
		prob += lpSum([symbol_card_var['%s_%s_%s'%(c0, s, c1)] \
				for c1 in Card \
						if check(c0, c1)]) <= 1
						
for c0 in Card:
	#print c0
	for c1 in Card:
		#print s
		prob += lpSum([symbol_card_var['%s_%s_%s'%(c0, s, c1)] \
				 for s in Symbol\
					if check(c0, c1)]) <= 1
for c0 in Card:
	for s in Symbol:
		for c1 in Card:
			if check(c0, c1):
				y = LpVariable('dummy_%s_%s_%s'%(c0,s,c1),0,1,cat='Integer')
				prob += 1 <= symbol_card_var['%s_%s_%s'%(c0,s,c1)] + 10*y
		 		prob += symbol_card_var['%s_%s_%s'%(c1,s,c0)] <= 0 + 10*(1-y)

prob.writeLP('dobble.lp')
prob += 0, "Arbitrary Objective Function"
status = prob.solve()
print LpStatus[status]
results = OrderedDict()
for v in prob.variables():
		if 'dummy' in v.name:
			continue
		f = v.name.split('_')
		card0 = f[2]
		symbol = f[4]
		card1 = f[6]
		if v.varValue == 1:
			if 'C%s'%(card0) in results:
				if not 'S%s'%(symbol) in results['C%s'%(card0)]:
					results['C%s'%(card0)].append('%s(Card %s)'%(symbol, card1))
			else:
				results['C%s'%(card0)] = ['%s(Card %s)'%(symbol, card1)]
		
for k,v in results.items():
	print k, v

print prob.objective
print value(prob.objective)

Example Dobble card: C(n) denotes the unique name of each card.

The list of symbols on each card also show the match symbol.

['<ITEM 1>(Card m)', '<ITEM 2>(Card m)' ]

C0 ['anchor(Card 25)', 'baby~bottle(Card 45)', 'bird(Card 49)', 'candle(Card 53)', 'carrot(Card 4)', 'clown~face(Card 48)', 'orange~man(Card 35)', 'yin~yang~sign(Card 12)']

C10 ['apple(Card 25)', 'baby~bottle(Card 50)', 'bird(Card 17)', 'carrot(Card 45)', 'chess~horse(Card 5)', 'green~turtle(Card 3)', 'question~mark(Card 54)', 'snow~man(Card 49)'] C11 ['anchor(Card 36)', 'apple(Card 39)', 'baby~bottle(Card 6)', 'bomb(Card 49)', 'candle(Card 4)', 'clown~face(Card 54)', 'question~mark(Card 35)', 'red~leaf(Card 7)'] C12 ['anchor(Card 48)', 'apple(Card 6)', 'bird(Card 40)', 'chess~horse(Card 49)', 'daises(Card 53)', 'exclamation~mark(Card 54)', 'snow~man(Card 29)', 'yin~yang~sign(Card 0)'] C13 ['anchor(Card 49)', 'apple(Card 3)', 'baby~bottle(Card 54)', 'bomb(Card 38)', 'carrot(Card 17)', 'orange~car(Card 48)', 'sun(Card 46)', 'sunglasses(Card 26)'] C14 ['anchor(Card 51)', 'apple(Card 20)', 'candle(Card 36)', 'igloo(Card 1)', 'key(Card 54)', 'light~bulb(Card 45)', 'orange~man(Card 9)', 'paint~stripper(Card 29)'] C15 ['anchor(Card 39)', 'bomb(Card 5)', 'fire(Card 51)', 'lips(Card 6)', 'music~note(Card 20)', 'pirate~scull(Card 30)', 'tree(Card 29)', 'zebra(Card 53)'] C16 ['apple(Card 54)', 'bird(Card 6)', 'bomb(Card 46)', 'cheese(Card 53)', 'clover(Card 3)', 'ice~cube(Card 40)', 'scissors(Card 52)', 'sunglasses(Card 48)'] C17 ['anchor(Card 35)', 'baby~bottle(Card 40)', 'bird(Card 10)', 'carrot(Card 13)', 'ghost(Card 1)', 'green~turtle(Card 29)', 'sider(Card 21)', 'zebra(Card 5)'] C18 ['apple(Card 5)', 'baby~bottle(Card 1)', 'catis(Card 48)', 'daises(Card 46)', 'exclamation~mark(Card 8)', 'question~mark(Card 44)', 'rain~drop(Card 40)', 'sun(Card 52)'] C19 ['apple(Card 35)', 'chess~horse(Card 21)', 'clock(Card 20)', 'daises(Card 45)', 'ice~cube(Card 51)', 'orange~man(Card 37)', 'question~mark(Card 7)', 'tree(Card 6)'] C1 ['anchor(Card 7)', 'baby~bottle(Card 18)', 'cat(Card 50)', 'ghost(Card 17)', 'igloo(Card 14)', 'key(Card 51)', 'paint~stripper(Card 53)', 'scissors(Card 35)'] C20 ['anchor(Card 53)', 'apple(Card 14)', 'candle(Card 26)', 'clock(Card 19)', 'clover(Card 30)', 'heart(Card 52)', 'music~note(Card 15)', 'pirate~scull(Card 44)'] C21 ['chess~horse(Card 19)', 'clown~face(Card 52)', 'dart~target(Card 50)', 'lighting~bolt(Card 31)', 'question~mark(Card 27)', 'rain~drop(Card 22)', 'scissors(Card 25)', 'sider(Card 17)'] C22 ['bird(Card 24)', 'carrot(Card 31)', 'eye(Card 2)', 'ghost(Card 52)', 'green~spots(Card 25)', 'music~note(Card 38)', 'rain~drop(Card 21)', 'red~leaf(Card 32)'] C23 ['apple(Card 24)', 'baby~bottle(Card 3)', 'bird(Card 27)', 'bomb(Card 34)', 'clover(Card 28)', 'no~entry~sign(Card 49)', 'red~leaf(Card 33)', 'tree(Card 25)'] C24 ['apple(Card 23)', 'baby~bottle(Card 25)', 'bird(Card 22)', 'bomb(Card 27)', 'candle(Card 2)', 'eye(Card 8)', 'ladybird(Card 50)', 'scissors(Card 26)'] C25 ['anchor(Card 0)', 'apple(Card 10)', 'baby~bottle(Card 24)', 'bomb(Card 2)', 'green~spots(Card 22)', 'scissors(Card 21)', 'snow~flake(Card 34)', 'tree(Card 23)'] C26 ['bird(Card 44)', 'candle(Card 20)', 'igloo(Card 4)', 'pirate~scull(Card 8)', 'scissors(Card 24)', 'sunglasses(Card 13)', 'tree(Card 34)', 't~rex(Card 5)'] C27 ['anchor(Card 32)', 'bird(Card 23)', 'bomb(Card 24)', 'daises(Card 30)', 'exclamation~mark(Card 51)', 'green~spots(Card 52)', 'question~mark(Card 21)', 'tree(Card 8)'] C28 ['anchor(Card 9)', 'bomb(Card 6)', 'clover(Card 23)', 'dobble~hand(Card 43)', 'key(Card 29)', 'ladybird(Card 33)', 'orange~car(Card 32)', 'zebra(Card 2)'] C29 ['dobble~hand(Card 51)', 'green~turtle(Card 17)', 'key(Card 28)', 'ladybird(Card 31)', 'paint~stripper(Card 14)', 'red~leaf(Card 9)', 'snow~man(Card 12)', 'tree(Card 15)'] C2 ['anchor(Card 50)', 'apple(Card 37)', 'bomb(Card 25)', 'candle(Card 24)', 'clover(Card 33)', 'eye(Card 22)', 'snow~man(Card 38)', 'zebra(Card 28)'] C30 ['anchor(Card 40)', 'candle(Card 3)', 'clock(Card 53)', 'clover(Card 20)', 'daises(Card 27)', 'lips(Card 49)', 'paddlock(Card 51)', 'pirate~scull(Card 15)'] C31 ['bird(Card 46)', 'bomb(Card 32)', 'carrot(Card 22)', 'ghost(Card 39)', 'ladybird(Card 29)', 'lighting~bolt(Card 21)', 'scissors(Card 33)', 'zebra(Card 4)'] C32 ['anchor(Card 27)', 'apple(Card 52)', 'bird(Card 50)', 'bomb(Card 31)', 'heart(Card 5)', 'ladybird(Card 34)', 'orange~car(Card 28)', 'red~leaf(Card 22)'] C33 ['baby~bottle(Card 41)', 'chess~horse(Card 50)', 'clover(Card 2)', 'ladybird(Card 28)', 'purple~dragon(Card 48)', 'red~leaf(Card 23)', 'scissors(Card 31)', 'zebra(Card 39)'] C34 ['bomb(Card 23)', 'cheese(Card 41)', 'clown~face(Card 5)', 'ladybird(Card 32)', 'no~entry~sign(Card 4)', 'snow~flake(Card 25)', 'tree(Card 26)', 't~rex(Card 42)'] C35 ['anchor(Card 17)', 'apple(Card 19)', 'ghost(Card 36)', 'ladybird(Card 39)', 'orange~man(Card 0)', 'paddlock(Card 38)', 'question~mark(Card 11)', 'scissors(Card 1)'] C36 ['anchor(Card 11)', 'apple(Card 42)', 'baby~bottle(Card 47)', 'candle(Card 14)', 'ghost(Card 35)', 'green~spots(Card 40)', 'rain~drop(Card 45)', 'sider(Card 41)'] C37 ['apple(Card 2)', 'chess~horse(Card 47)', 'daises(Card 43)', 'dart~target(Card 42)', 'eye(Card 39)', 'green~spots(Card 48)', 'orange~man(Card 19)', 'pirate~scull(Card 41)'] C38 ['apple(Card 51)', 'bomb(Card 13)', 'dart~target(Card 44)', 'music~note(Card 22)', 'paddlock(Card 35)', 'question~mark(Card 48)', 'scissors(Card 8)', 'snow~man(Card 2)'] C39 ['anchor(Card 15)', 'apple(Card 11)', 'cat(Card 47)', 'dart~target(Card 4)', 'eye(Card 37)', 'ghost(Card 31)', 'ladybird(Card 35)', 'zebra(Card 33)'] C3 ['anchor(Card 5)', 'apple(Card 13)', 'baby~bottle(Card 23)', 'candle(Card 30)', 'cheese(Card 47)', 'chess~horse(Card 4)', 'clover(Card 16)', 'green~turtle(Card 10)'] C40 ['anchor(Card 30)', 'baby~bottle(Card 17)', 'bird(Card 12)', 'green~spots(Card 36)', 'ice~cube(Card 16)', 'igloo(Card 47)', 'question~mark(Card 6)', 'rain~drop(Card 18)'] C41 ['anchor(Card 44)', 'baby~bottle(Card 33)', 'catis(Card 43)', 'cheese(Card 34)', 'clock(Card 42)', 'orange~man(Card 54)', 'pirate~scull(Card 37)', 'sider(Card 36)'] C42 ['anchor(Card 45)', 'apple(Card 36)', 'baby~bottle(Card 52)', 'clock(Card 41)', 'dart~target(Card 37)', 'no~entry~sign(Card 47)', 'scissors(Card 43)', 't~rex(Card 34)'] C43 ['baby~bottle(Card 7)', 'bird(Card 47)', 'cat(Card 45)', 'catis(Card 41)', 'daises(Card 37)', 'dobble~hand(Card 28)', 'ladybird(Card 46)', 'scissors(Card 42)'] C44 ['anchor(Card 41)', 'baby~bottle(Card 9)', 'bird(Card 26)', 'candle(Card 46)', 'cat(Card 49)', 'dart~target(Card 38)', 'pirate~scull(Card 20)', 'question~mark(Card 18)'] C45 ['anchor(Card 42)', 'baby~bottle(Card 0)', 'carrot(Card 10)', 'cat(Card 43)', 'daises(Card 19)', 'key(Card 7)', 'light~bulb(Card 14)', 'rain~drop(Card 36)'] C46 ['anchor(Card 8)', 'bird(Card 31)', 'bomb(Card 16)', 'candle(Card 44)', 'daises(Card 18)', 'ice~cube(Card 7)', 'ladybird(Card 43)', 'sun(Card 13)'] C47 ['anchor(Card 6)', 'baby~bottle(Card 36)', 'bird(Card 43)', 'cat(Card 39)', 'cheese(Card 3)', 'chess~horse(Card 37)', 'igloo(Card 40)', 'no~entry~sign(Card 42)'] C48 ['anchor(Card 12)', 'catis(Card 18)', 'clown~face(Card 0)', 'green~spots(Card 37)', 'orange~car(Card 13)', 'purple~dragon(Card 33)', 'question~mark(Card 38)', 'sunglasses(Card 16)'] C49 ['anchor(Card 13)', 'bird(Card 0)', 'bomb(Card 11)', 'cat(Card 44)', 'chess~horse(Card 12)', 'lips(Card 30)', 'no~entry~sign(Card 23)', 'snow~man(Card 10)'] C4 ['bird(Card 9)', 'candle(Card 11)', 'carrot(Card 0)', 'chess~horse(Card 3)', 'dart~target(Card 39)', 'igloo(Card 26)', 'no~entry~sign(Card 34)', 'zebra(Card 31)'] C50 ['anchor(Card 2)', 'baby~bottle(Card 10)', 'bird(Card 32)', 'cat(Card 1)', 'chess~horse(Card 33)', 'dart~target(Card 21)', 'ladybird(Card 24)', 'sunglasses(Card 7)'] C51 ['anchor(Card 14)', 'apple(Card 38)', 'dobble~hand(Card 29)', 'exclamation~mark(Card 27)', 'fire(Card 15)', 'ice~cube(Card 19)', 'key(Card 1)', 'paddlock(Card 30)'] C52 ['apple(Card 32)', 'baby~bottle(Card 42)', 'clown~face(Card 21)', 'ghost(Card 22)', 'green~spots(Card 27)', 'heart(Card 20)', 'scissors(Card 16)', 'sun(Card 18)'] C53 ['anchor(Card 20)', 'apple(Card 9)', 'candle(Card 0)', 'cheese(Card 16)', 'clock(Card 30)', 'daises(Card 12)', 'paint~stripper(Card 1)', 'zebra(Card 15)'] C54 ['apple(Card 16)', 'baby~bottle(Card 13)', 'clown~face(Card 11)', 'exclamation~mark(Card 12)', 'key(Card 14)', 'orange~man(Card 41)', 'pencil(Card 9)', 'question~mark(Card 10)'] C5 ['anchor(Card 3)', 'apple(Card 18)', 'bomb(Card 15)', 'chess~horse(Card 10)', 'clown~face(Card 34)', 'heart(Card 32)', 't~rex(Card 26)', 'zebra(Card 17)'] C6 ['anchor(Card 47)', 'apple(Card 12)', 'baby~bottle(Card 11)', 'bird(Card 16)', 'bomb(Card 28)', 'lips(Card 15)', 'question~mark(Card 40)', 'tree(Card 19)'] C7 ['anchor(Card 1)', 'apple(Card 8)', 'baby~bottle(Card 43)', 'ice~cube(Card 46)', 'key(Card 45)', 'question~mark(Card 19)', 'red~leaf(Card 11)', 'sunglasses(Card 50)'] C8 ['anchor(Card 46)', 'apple(Card 7)', 'exclamation~mark(Card 18)', 'eye(Card 24)', 'paint~stripper(Card 9)', 'pirate~scull(Card 26)', 'scissors(Card 38)', 'tree(Card 27)'] C9 ['anchor(Card 28)', 'apple(Card 53)', 'baby~bottle(Card 44)', 'bird(Card 4)', 'orange~man(Card 14)', 'paint~stripper(Card 8)', 'pencil(Card 54)', 'red~leaf(Card 29)']

Tags: integer, interface, mixed, program