Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SpotIt Stuff
#!/usr/bin/env python3
''' algorithmx_spotit
Generate small Spot-It decks by brute force searching for
the exact cover of pairs of cards which share a symbol.
Uses Knuth's Algorithm X for the exact cover problem.
The Algorithm X code, using dicts instead of doubly-linked
circular lists was written by Ali Assaf.
See http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt
Warning: this program can be slow when the repeat value > 3,
and it can consume *lots* of RAM.
This program can output multiple solutions. You can specify
the maximum number of solutions printed via the maxcount arg,
set maxcount to zero to print all solutions.
Written by PM 2Ring 2017.09.04
'''
import sys
from itertools import combinations
import spotit_tools as st
#Algorithm X functions
def solve(X, Y, solution, depth=0):
depth += 1
st.progress(depth, interval=100)
if X:
c = min(X, key=lambda c: len(X[c]))
for r in X[c]:
solution.append(r)
cols = select(X, Y, r)
yield from solve(X, Y, solution, depth)
deselect(X, Y, r, cols)
solution.pop()
else:
yield list(solution)
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
#Invert subset collection
def exact_cover(X, Y):
newX = {j: set() for j in X}
for i, row in Y.items():
for j in row:
newX[j].add(i)
return newX
#----------------------------------------------------------------------
def make_deck(d, r, c, s):
logfile = sys.stderr
print('Building...', file=logfile)
# The "set" that we want to find the exact covers of:
# all of the pairs of cards.
X = list(combinations(range(c), 2))
# The collection of subsets of X. Each symbol is shared by r cards. Each
# subset corresponds to one of the possible combinations of r cards and
# contains all pairs of cards from that combination. We reduce the size
# of Y a little by creating the first card manually.
first = tuple(range(r))
used = set(combinations(first, 2))
Y = {first: list(used)}
for cards in combinations(range(c), r):
t = list(combinations(cards, 2))
if not used.intersection(t):
Y[cards] = t
print('Using {} subsets'.format(len(Y)), file=logfile)
# Invert X
X = exact_cover(X, Y)
select(X, Y, first)
# Do it!
print('Placing symbols...', file=logfile)
for solution in solve(X, Y, [first]):
print(file=logfile)
# Reorganize the solution into an actual deck
cards = {}
for i, t in enumerate(solution):
for k in t:
cards.setdefault(k, []).append(i)
yield sorted(cards.values())
def main():
if len(sys.argv) < 3:
print('Algorithm X Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats [maxcount]' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:3])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
maxcount = int(sys.argv[3]) if len(sys.argv) > 3 else 1
for count, deck in enumerate(make_deck(d, r, c, s), 1):
print('Solution', count)
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if count == maxcount:
break
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' galois
A basic polynomial class, Poly, and Galois, a class which uses Poly
to perform finite field addition and multiplication
Written by PM 2Ring 2017.09.15
'''
from itertools import product
from functools import lru_cache
class Poly:
''' Create a polynomial from a numeric sequence of coefficients, with the
constant term in data[0], the x coefficient in data[1], etc.
Thus Poly([4, 5, 6, 7]) is equivalent to 4 + 5*x + 6*x**2 + 7*x**3
data may also be a simple scalar numeric value
'''
def __init__(self, data):
try:
self.data = list(data)
except TypeError:
#Hopefully, data is some kind of numeric type :)
self.data = [data]
self.norm()
def __getitem__(self, key): return self.data[key]
def __setitem__(self, key, value): self.data[key] = value
def __delitem__(self, key): del self.data[key]
def __len__(self): return len(self.data)
def __repr__(self): return 'Poly({!r})'.format(self.data)
@staticmethod
def fmt(n):
''' Format a signed coefficient; a helper function for __str__ '''
if n == 0:
return ''
nn, s = abs(n), '-+'[n>0]
return ' {} {}x'.format(s, nn != 1 and nn or '')
def __str__(self):
''' Display the polynomial in regular form.
Doesn't handle complex coefficients correctly
'''
fmt = self.fmt
z = ""
# Powers >=2 of x
for i in range(len(self)-1, 1, -1):
d = fmt(self[i])
if d:
z += "%s^%d" % (d, i)
# x term
if len(self)>1:
d = fmt(self[1])
if d:
z += "%s" % d
# Constant term
d = fmt(self[0])
if d:
z += d[:-1] + '1' if len(d) == 4 else d[:-1]
elif len(z) == 0:
return '0'
# Fix leading sign & spaces
return '-' + z[3:] if z[1] == '-' else z[3:]
def __format__(self, s): return format(str(self), s)
# Normalize, by eliminating trailing zero terms
def norm(self):
while len(self) > 1 and self[-1] == 0:
del self[-1]
if not self.data:
self.data = [0]
return self
def __add__(self, other):
if not isinstance(other, Poly):
other = Poly(other)
if len(self) > len(other):
a, b = self[:], other
else:
a, b = other[:], self
for i in range(len(b)):
a[i] += b[i]
return Poly(a)
def __neg__(self): return self.smul(-1)
def __sub__(self, other): return self + (-other)
# Scalar multiplication
def smul(self, n): return Poly([n*i for i in self] if n else 0)
# Scalar modulus reduction of coefficients
def smod(self, n): return Poly(i%n for i in self)
def __mul__(self, other):
if not isinstance(other, Poly):
return self.smul(other)
prod = Poly([0] * (len(self) + len(other) - 1))
a, b = (self, other) if len(self) > len(other) else (other, self)
mult = Poly(a)
for k in b:
if k != 0:
prod += mult.smul(k)
mult.data = [0] + mult.data
return prod
# Long division, with remainder
def __divmod__(self, den):
rem = Poly(self)
quot = zero = Poly(0)
#For Galois polynomial reduction, divisor will always be 1
divisor = den[-1]
if len(den) == 1:
return rem.smul(1. / divisor), zero
while not rem.almosteq(zero) and len(rem) >= len(den):
#t = rem[-1] / divisor if rem[-1] % divisor else rem[-1] // divisor
t = rem[-1] // divisor
mult = Poly([0] * (len(rem) - len(den)) + [t])
quot += mult
rem -= mult * den
return quot, rem
def __floordiv__(self, other):
q, r = self.__divmod__(other)
return q
def __mod__(self, other):
q, r = self.__divmod__(other)
return r
def __eq__(self, other):
self.norm()
return self.data == Poly(other).data
def almosteq(self, other, epsilon = 1e-12):
if len(self.norm()) != len(other.norm()):
return False
return all(-epsilon < u < epsilon for u in (self - other))
#Evaluate poly with arg x
def __call__(self, x):
y = self[-1]
for k in self[-2::-1]:
y = x * y + k
return y
class Galois:
''' A class for doing finite field addition & multiplication '''
def __init__(self, p, n, modpoly):
''' p is the prime, n is the power, modpoly is an irreducible
polynomial, either in the form of a Poly instance or as a
list or tuple.
'''
#Check that p is prime.
if p<2 or (p != 2 and p % 2 == 0) or any(p % i == 0
for i in range(3, 1 + int(p ** 0.5), 2)):
raise ValueError('{} is not prime'.format(p))
self.p = p
self.n = n
self.modpoly = modpoly if isinstance(modpoly, Poly) else Poly(modpoly)
self.polys = [Poly(t[::-1]) for t in product(range(p), repeat=n)]
def __repr__(self): return 'GF({}^{})'.format(self.p, self.n)
def __len__(self): return len(self.polys)
@lru_cache(None)
def add(self, i, j):
p = self.p
u, v = self.polys[i], self.polys[j]
poly = (u + v).smod(p)
return poly(p)
@lru_cache(None)
def mul(self, i, j):
p = self.p
u, v = self.polys[i], self.polys[j]
poly = ((u * v).smod(p) % self.modpoly).smod(p)
return poly(p)
def test_add(self, verbose=False):
q = len(self.polys)
r = range(q)
valid = set(r)
ok = True
for i in r:
a = [self.add(i, j) for j in r]
if set(a) != valid:
if verbose:
print('Addition table error:', i, a)
ok = False
return ok
def test_mul(self, verbose=False):
q = len(self.polys)
ok = True
error_message = 'Multiplication table error:'
a = [self.mul(0, i) for i in range(q)]
if any(a):
if verbose:
print(error_message, 0, a)
ok = False
a = [self.mul(i, 0) for i in range(q)]
if any(a):
if verbose:
print(error_message, 0, a)
ok = False
r = range(1, q)
valid = set(r)
for i in r:
a = [self.mul(i, j) for j in r]
if set(a) != valid:
if verbose:
print(error_message, i, a)
ok = False
return ok
if __name__ == "__main__":
# Test
p, n = 3, 4
modpoly = Poly([2, 1, 0, 0, 1])
gf = Galois(p, n, modpoly)
print('Testing Galois field arithmetic for', gf)
print('Addition', ('bad', 'good')[gf.test_add()])
print('Multiplication', ('bad', 'good')[gf.test_mul()])
#!/usr/bin/env python3
''' galois_spotit
Generate a Spot-It deck from a prime power finite field
Written by PM 2Ring 2017.09.08
'''
import sys
from ast import literal_eval
import spotit_tools as st
from galois import Poly, Galois
# Irreducible polynomials for p**n < 150
modpolys = {
(2, 2): [1, 1, 1], (2, 3): [1, 1, 0, 1],
(2, 4): [1, 1, 0, 0, 1], (2, 5): [1, 0, 1, 0, 0, 1],
(2, 6): [1, 1, 0, 0, 0, 0, 1], (2, 7): [1, 1, 0, 0, 0, 0, 0, 1],
(3, 2): [1, 0, 1], (3, 3): [1, 2, 0, 1], (3, 4): [2, 1, 0, 0, 1],
(5, 2): [2, 0, 1], (5, 3): [1, 1, 0, 1],
(7, 2): [1, 0, 1], (11, 2): [1, 0, 1],
}
def make_deck(gf):
q = len(gf)
r = range(q)
for i in r:
last = [q * q + 1 + i]
for j in r:
yield [k * q + (gf.add(j, gf.mul(i, k))) for k in r] + last
last = [q * q]
for i in r:
yield [i * q + j for j in r] + last
yield [q * q + i for i in range(q+1)]
def main():
if len(sys.argv) < 3:
print('Galois finite field Spot-It deck finder.\nUsage:\n'
'%s prime_modulus power [modpoly]' % sys.argv[0])
sys.exit()
p, n = map(int, sys.argv[1:3])
#Check that p is prime.
if p<2 or (p != 2 and p % 2 == 0) or any(p % i == 0
for i in range(3, 1 + int(p ** 0.5), 2)):
print('{} is not prime'.format(p))
sys.exit()
if len(sys.argv) > 3:
modpoly = Poly(literal_eval(sys.argv[3]))
# Basic check for validity of modpoly.
if not (len(modpoly) == n + 1
and all(modpoly(u) % p for u in range(p))):
print('modpoly is invalid')
sys.exit()
else:
modpoly = modpolys.get((p, n)) if n != 1 else [0, 1]
if not modpoly:
print("Sorry, I don't have a modpoly for ({}, {})".format(p, n))
sys.exit()
gf = Galois(p, n, modpoly)
q = len(gf)
d = r = q + 1
c = s = q*q + q + 1
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = sorted(make_deck(gf))
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
pass
# These functions are commented out because the tables
# they produce are very large unless q is small.
#st.incidence_matrix(deck, s)
#st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' grid_spotit
Generate Spot-It decks by recursive backtracking,
using a grid of symbols shared by card pairs.
Written by PM 2Ring 2017.09.12
'''
import sys
import spotit_tools as st
def mark_pairs(grid, symrow, card1, card2, sym):
grid[card1][card2] = grid[card2][card1] = sym
for k in symrow:
grid[k][card2] = grid[card2][k] = sym
def solve(c, s, rr, card1, card2, nextsym, grid, symlist, symdict):
''' Recursively fill grid, the 2D list of symbols shared by cards.
card1 & card2 are row & column grid indices, symlist is
the list of new symbols to use for card1, starting with nextsym.
symdict holds lists of card numbers, keyed by symbol.
'''
st.progress(nextsym, 100)
if symlist is None:
# This must be a new card, so we need to build a new symlist
# and clear the associated items in symdict
newcard = True
count = (sum(1 for u in grid[card1] if u is None) - 1) // rr
symlist = list(range(nextsym, nextsym + count))
for k in symlist:
symdict[k] = []
else:
newcard = False
# Look for an empty slot
for card2 in range(card2, c):
if grid[card1][card2] is None:
break
else:
# There are no empty slots, so we've reached the end of the card
nextsym = symlist[-1] + 1
if nextsym == s:
# This must be a solution!
return True
return solve(c, s, rr, card1 + 1, card1 + 2, nextsym, grid, None, symdict)
# Try to find a symbol to fill the slot
for sym in symlist:
# Get the list of cards that already have this symbol
symrow = symdict[sym]
# Check the symbol use count, and that the corresponding slots are free
if len(symrow) < rr and all(grid[card2][k] is None for k in symrow):
# Place the symbol in the slots
mark_pairs(grid, symrow, card1, card2, sym)
symrow.append(card2)
# Recurse to fill the next slot
if solve(c, s, rr, card1, card2 + 1, nextsym, grid, symlist, symdict):
return True
else:
# The recursion failed, so we need to undo this symbol
del symrow[-1]
mark_pairs(grid, symrow, card1, card2, None)
if newcard:
# There's no point trying other symbols in the first
# empty slot of a new card
break
return False
def make_deck(d, r, c, s):
grid = [[None] * c for _ in range(c)]
symdict = {k: [] for k in range(s)}
solve(c, s, r - 1, 0, 1, 0, grid, None, symdict)
print(file=sys.stderr)
return [sorted(set(row) - {None}) for row in grid]
def main():
if len(sys.argv) != 3:
print('Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = make_deck(d, r, c, s)
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' Search for minimal irreducible polynomials over primes
This is slow unless n is small
Written by PM 2Ring 2017.09.15
'''
import sys
from itertools import product
from galois import Poly, Galois
primes = (2, 3, 5, 7, 11)
# A slow brute-force test
def test_modpoly_old(p, n, modpoly):
if all(modpoly(u) % p for u in range(p)):
gf = Galois(p, n, modpoly)
return all(gf.mul(i, j) for i, u in enumerate(gf.polys[1:], 1)
for j, v in enumerate(gf.polys[i:], i))
return False
def make_bigpoly(w):
a = [0] * w + [1]
a[1] = -1
return Poly(a)
def test_modpoly(p, n, modpoly):
''' Rabin's Test of Irreducibility '''
# First make sure there are no linear factors.
# This isn't necessary, but it can speed things up
if not all(modpoly(u) % p for u in range(p)):
return False
bigpoly = make_bigpoly(p ** n)
if (bigpoly % modpoly).smod(p) != 0:
return False
for u in primes:
if u >= n:
break
quo, rem = divmod(n, u)
if rem == 0:
bigpoly = make_bigpoly(p ** quo)
g = poly_gcd(bigpoly, modpoly, p)
if len(g) > 1:
return False
return True
# Polynomial Greatest Common Divisor
def poly_gcd(a, b, p):
a, b = a.smod(p), b.smod(p)
if len(b) > len(a):
a, b = b, a
zero = Poly(0)
while b != zero:
a, b = b, (a % b).smod(p)
return a
def make_modpoly(p, n):
count = 0
for u, v in product(product(range(p), repeat=n-1), range(1, p)):
count += 1
print(' {}'.format(count), end='\r', file=sys.stderr)
modpoly = Poly([1, *u, v][::-1])
if test_modpoly(p, n, modpoly):
return modpoly
d = {}
for p in primes:
for n in range(2, 8):
q = p ** n
if q > 150:
break
modpoly = make_modpoly(p, n)
print('{}^{} = {} : {}'.format(p, n, q, modpoly))
d[p, n] = modpoly.data
# Print in dictionary form
print()
for k in sorted(d):
v = d[k]
print('{}: {},'.format(k, v))
#!/usr/bin/env python3
''' paircombo_spotit
Generate Spot-It decks by recursive backtracking
The target set X is the set of pairs of cards. We use the list Y
to iterate over the r-length groups of cards, build a set of pairs
from the group and if it's in X, we add the group to the solution,
remove the pairs from X, and recurse.
Written by PM 2Ring 2017.09.06
'''
import sys
from itertools import combinations
import spotit_tools as st
def next_combo(seq, n):
''' Mutate the combination in seq to the next combination in
lexicographic order. Returns False when we've reached the end.
The items in seq are integers in range(n)
'''
i = k = len(seq) - 1
hi = n - k
while True:
seq[i] += 1
if seq[i] == (hi + i):
i -= 1
if i < 0:
return False
else:
break
v = seq[i] + 1
seq[i+1:] = range(v, v + k - i)
return True
def solve(X, Y, c, solution):
if not X:
return solution
n = len(solution)
ok = True
while ok:
st.progress(n, 10000)
group = list(Y)
pairs = set(combinations(group, 2))
ok = next_combo(Y, c)
if X.issuperset(pairs):
result = solve(X - pairs, list(Y), c, solution + [group])
if result:
return result
def make_deck(d, r, c, s):
X = set(combinations(range(c), 2))
Y = list(range(r))
print('Using {} subsets'.format(st.nCr(c, r)))
solution = solve(X, Y, c, [])
print(file=sys.stderr)
# Reorganize the solution into an actual deck
cards = {}
for i, t in enumerate(solution):
for k in t:
cards.setdefault(k, []).append(i)
return sorted(cards.values())
def main():
if len(sys.argv) != 3:
print('Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = make_deck(d, r, c, s)
for i, k in enumerate(deck):
print(i, k)
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' prime_spotit
Generate a Spot-It deck from a prime finite field
Written by PM 2Ring 2017.09.08
'''
import sys
import spotit_tools as st
def make_cards_prime(q):
r = range(q)
for i in r:
last = [q * q + 1 + i]
for j in r:
yield [k * q + (j + i * k) % q for k in r] + last
last = [q * q]
for i in r:
yield [i * q + j for j in r] + last
yield [q * q + i for i in range(q+1)]
def main():
if len(sys.argv) != 2:
print('Prime finite field Spot-It deck finder.\nUsage:\n'
'%s prime_modulus' % sys.argv[0])
sys.exit()
q = int(sys.argv[1])
#Crude check that q is prime. The algorithm also works for 0 & 1.
if q<2 or (q != 2 and q % 2 == 0) or any(q % i == 0
for i in range(3, 1 + int(q ** 0.5), 2)):
print('{} is not prime'.format(q))
sys.exit()
d = r = q + 1
c = s = q*q + q + 1
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = sorted(make_cards_prime(q))
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' random_spotit
Generate Spot-It decks by recursive backtracking, using
random card generation.
Written by PM 2Ring 2017.09.04
'''
import sys
from random import seed, choice, shuffle
import spotit_tools as st
#seed(42)
def solve(d, pool, deck):
if not pool:
return deck
count = 0
while True:
count += 1
card = set()
while len(card) < d:
card.add(choice(pool))
if all(len(card & u) == 1 for u in deck):
for sym in card:
pool.remove(sym)
result = solve(d, pool, deck + [card])
if result is None:
# We couldn't complete the deck, so we reject this
# card and return its symbols to the pool.
pool.extend(card)
#shuffle(pool)
else:
return result
if count % 1000 == 0:
print(' {} : {} '.format(len(deck), count), end='\r', flush=True)
if count >= len(deck) * 5000:
# Maybe its not possible to complete the deck with the curren
# choices, so we return None to signal failure. Change the
# multiplier to less than 5000 to speed up searching, or
# increase it to make the search more thorough.
break
def make_deck(d, r, c, s):
pool = list(range(s)) * r
deck = solve(d, pool, [])
print()
return deck
def main():
if len(sys.argv) != 3:
print('Random Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = make_deck(d, r, c, s)
for i, k in enumerate(deck):
print(i, k)
if st.check_size(deck, c) and st.check_counts(deck, r, s):
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' simple_spotit
Generate simple Spot-It decks
The simplest Spot-It decks have each symbol repeated twice, so the
number of cards is one more than the number of symbols per card.
Written by PM 2Ring 2017.09.04
'''
import sys
from itertools import combinations
import spotit_tools as st
def make_deck(c):
deck = [[] for _ in range(c)]
# Assign a unique symbol to each pair of cards
for sym, (u, v) in enumerate(combinations(range(c), 2)):
deck[u].append(sym)
deck[v].append(sym)
return deck
def main():
if len(sys.argv) != 2:
print('Simple Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card' % sys.argv[0])
sys.exit()
d, r = int(sys.argv[1]), 2
c, s = st.cards_and_symbols(d, r)
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = make_deck(c)
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
# We don't really need to call check_size or check_counts...
if st.check_size(deck, c) and st.check_counts(deck, r, s):
deck = [set(u) for u in deck]
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
SpotIt README
About
-----
This is a collection of Python 3 scripts that generate SpotIt-like
card decks, using various strategies.
These programs use integers to represent the cards' symbols.
The programs print lists of the symbols on each card; an incidence
matrix, that shows which symbols are used on which cards; and a pair
matrix, that shows which symbol is shared by each pair of cards.
Most of the programs are general-purpose solvers that accept any valid
combination of symbols_per_card and repeats input parameters, but some
of them are special-purpose solvers that only accept a single input
parameter. You can run a script without command-line args to get a brief
usage message.
The special-purpose programs run quite quickly; the general-purpose
solvers can run for a long time, and may not actually find a solution
(assuming one exists), but they print relevant progress info while
they're searching.
Written by PM 2Ring, September 2017.
Contents
--------
The deck generation programs:
algorithmx_spotit.py
galois_spotit.py
grid_spotit.py
paircombo_spotit.py
prime_spotit.py
random_spotit.py
simple_spotit.py
symcombo_limited_spotit.py
symcombo_spotit.py
symcount_spotit.py
Helper modules:
spotit_tools.py
galois.py
Miscellaneous:
minimal_modpoly.py
All of the deck generation programs import spotit_tools.py,
galois.py is only imported by galois_spotit.py and minimal_modpoly.py.
Brief descriptions of the deck generation programs
--------------------------------------------------
simple_spotit.py - a special solver
Generate a Spot-It deck with each symbol repeated twice; the number of
cards is one more than the number of symbols per card. These are the
simplest possible Spot-It decks, so they're very easy to produce.
- - - - -
prime_spotit.py - a special solver
Generate a Spot-It deck from a prime finite field. It takes a single arg,
prime_modulus, which is one less than the number of symbols per card. As
you might guess, prime_modulus MUST be a prime number. The number of cards
generated is (prime_modulus**2 + prime_modulus + 1).
- - - - -
galois_spotit.py - a special solver
Generate a Spot-It deck from a prime power finite field. It takes up to
3 args: prime_modulus and power, which are mandatory, and an optional
modpoly, which is an irreducible polynomial for the finite field.
Let q = prime_modulus**power. q is one less than the number of symbols
per card, and the number of cards generated is (q**2 + q + 1).
The program has a built-in table of minimal modpolys for various small
primes and powers, for all q < 150. This program can accept a power arg
of 1, but it's more efficient to use prime_spotit.py.
This program contains the code to print the incidence and pair matrices,
but it's commented out because these tables are huge unless q is small.
- - - - -
algorithmx_spotit.py
Generate small Spot-It decks by brute force searching for the exact
cover of pairs of cards which share a symbol. Uses Knuth's Algorithm X
for the exact cover problem. This program can output multiple solutions.
Warning: this program can be slow when the repeat value > 3, and it can
consume *lots* of RAM.
This is the best general-purpose solver, and its usually faster than the
other general-purpose solvers. It's guaranteed to find a solution (or all
solutions), if a solution exists, but it should only be used on smallish
input arguments unless you have a huge amount of RAM.
- - - - -
The remaining deck generation programs use recursive backtracking to
search for solutions, as does algorithmx_spotit.py. They are generally
slower than algorithmx_spotit.py, and may run for a long time before
finding a solution (if they find one at all), but they generally use far
less RAM than algorithmx_spotit.py does, so they may be worth trying on
input args that are too big for algorithmx_spotit.py.
grid_spotit.py
Generate a Spot-It deck using a grid of symbols shared by card pairs.
This program is fairly fast for smallish repeat values.
- - - - -
paircombo_spotit.py
Generate a Spot-It deck by searching for combinations of pairs of cards
taken from all of the r-length groups of cards, where r is the repeat
count. This is a similar strategy to that used by algorithmx_spotit.py,
but it uses far less RAM, so it's generally much slower.
- - - - -
random_spotit.py
Generate a Spot-It deck by random card generation. This program
generates random cards from a pool of symbols. You can tweak the
searching process by modifying the hard-coded bailout parameter from
5000 (to another multiple of 1000), but 5000 seems to give reasonable
results in my tests.
- - - - -
symcombo_spotit.py
Generate a Spot-It deck by searching over all combinations of symbols
that can make up a card. This algorithm can waste a lot of time testing
cards that duplicate too many symbols of previous cards.
- - - - -
symcombo_limited_spotit.py
An improved version of symcombo_spotit.py. It reduces the number of
tests because it makes each card by reusing one symbol from each card
already in the deck and then append combinations from symbols that
haven't been used yet.
- - - - -
symcount_spotit.py
Generate a Spot-It deck by using symbol counts. We scan the list of
cards, searching for a card that won't put any of the current symbol
counts over the limit. When we find such a card we add it to the deck
and eliminate all remaining cards that don't have exactly one matching
symbol with the current card and then recurse to find the subsequent
cards.
- - - - -
Brief descriptions of the other modules
---------------------------------------
spotit_tools.py
Contains various functions used by all the deck generation programs.
It's designed to be imported, but if you run it from the command line
it prints a small Spot-It parameter table.
galois.py
A basic polynomial class, Poly, and Galois, a class which uses Poly
to perform finite field addition and multiplication. This module is
used by galois_spotit.py. You can run it from the command line to do
a brute-force test of a finite field.
minimal_modpoly.py
Search for minimal irreducible polynomials over primes. This process can
be quite slow, so galois_spotit.py has a built-in table of minimal
irreducible polynomials.
#!/usr/bin/env python3
''' spotit_tools
Helper functions for Spot-It / Dobble deck construction.
This module is designed to be imported, but you can run
it to print a Spot-It parameter table.
Functions defined here:
cards_and_symbols(d, r)
nCr(n, r)
check_size(deck, c)
check_counts(deck, r, s)
test_matches(deck)
incidence_matrix(deck, s)
pair_matrix(deck)
progress(n, interval=1000)
spotit_table(num=11)
d: Number of symbols per card
r: Number of times each symbol is repeated through the deck
c: Number of cards in the deck
s: Number of distinct symbols
deck is a collection of cards (eg a list). Each card in a deck
is a collection of symbol numbers (integers in range(s)). The
functions test_matches, incidence_matrix, and pair_matrix require
that each card be a set, check_size and check_counts aren't fussy.
Written by PM 2Ring 2017.09.12
'''
import sys
def cards_and_symbols(d, r):
''' Calculate c the number of cards, and s the number of different symbols
for a Spot-It deck, given d the number of symbols per card, and r the
number of times each symbol is repeated throughout the deck. r <= d,
and r must divide d * (d - 1), otherwise None is returned.
'''
if 2 <= r <= d and d * (d - 1) % r == 0:
c = 1 + d * (r - 1)
s = c * d // r
return c, s
def nCr(n, r):
''' Binomial coefficients: the total number of
combinations of n items taken r at a time.
'''
if not 0 <= r <= n:
return 0
p = 1
r = min(r, n - r)
for i in range(1, r+1):
p *= n
p //= i
n -= 1
return p
def check_size(deck, c):
''' Check that the deck size is correct '''
decklen = len(deck)
ok = decklen == c
if not ok:
print('Bad deck size:', decklen)
return ok
def check_counts(deck, r, s):
''' Check that we have the right numbers of symbols '''
ok = True
syms = {u: [] for u in range(s)}
for i, card in enumerate(deck):
for u in card:
try:
syms[u].append(i)
except KeyError as e:
print('Unexpected symbol!:', e)
ok = False
fmt = 'Bad sym count. sym: {} len: {} cards: {}'
for u in range(s):
l = len(syms[u])
if l != r:
ok = False
print(fmt.format(u, l, syms[u]))
if ok:
print('Sym count ok')
return ok
def test_matches(deck):
''' Test that a Spot-It deck works, i.e., that each card
shares exactly one symbol with every other card
'''
ok = True
for i, u in enumerate(deck):
for j, v in enumerate(deck[i+1:], i+1):
l = len(u & v)
if l != 1:
print(i, u, j, v, l)
ok = False
print(('Bad matches found', 'All cards match correctly')[ok], '\n')
return ok
def incidence_matrix(deck, s):
''' Print the card / symbol incidence matrix '''
range_s = range(s)
if s > 10:
print(' ', ' '.join([str(u//10) if u>9 else ' ' for u in range_s]))
print(' ', ' '.join([str(u%10) for u in range_s]))
for i, row in enumerate(deck):
print('{:2}'.format(i), '|'.join([' X'[u in row] for u in range_s]))
print()
def pair_matrix(deck):
''' Print the matrix of symbols shared by each pair of cards '''
c = len(deck)
a = ' '.join(['{:2}'.format(i) for i in range(c)])
print(' ', a)
print(' ', '-' * len(a))
for i, u in enumerate(deck):
row = ' '.join(['{:2}'.format((u & v).pop()) if i != j else ' -'
for j, v in enumerate(deck)])
print('{:2}'.format(i), '|' + row)
print()
def progress(n, interval=1000):
''' Display progress to stderr on a single line. '''
progress.count += 1
if progress.count % interval == 0:
print(' {:2} : {}'.format(n, progress.count), end='\r',
file=sys.stderr)
progress.count = 0
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
''' Potential Spot-It deck parameters
Any valid (non-trivial) deck corresponds to a parameter set
of this form, but some of these sets have no solutions.
Table format
------------
d: Number of symbols per card
r: Number of times each symbol is repeated through the deck
c: Number of cards in the deck
s: Number of distinct symbols
The core formula is c = 1 + d * (r - 1)
Note that c * d == r * s; also, c * (c - 1) = s * r * (r -1).
It can be shown that r divides d * (d - 1)
For non-trivial decks, 2 <= r <= d
Each row corresponds to a d, each column corresponds to an r.
Each table entry is c,s with --- for invalid d,r combinations.
rows=d, cols=r, table item=c,s
d/r 2 3 4 5 6 7 8 9 10
2: 3, 3
3: 4, 6 7, 7
4: 5,10 9,12 13,13
5: 6,15 --- 16,20 21,21
6: 7,21 13,26 --- 25,30 31,31
7: 8,28 15,35 --- --- 36,42 43,43
8: 9,36 --- 25,50 --- --- 49,56 57,57
9: 10,45 19,57 28,63 --- 46,69 --- 64,72 73,73
10: 11,55 21,70 --- 41,82 51,85 --- --- 81,90 91,91
'''
def spotit_table(num=11):
''' Print a table of parameters that may lead to valid Spot-It decks. '''
print('d/r', ' '.join(['{:5}'.format(u) for u in range(2, num)]))
for d in range(2, num):
row = ['{:2}:'.format(d)]
dd = d * (d - 1)
for r in range(2, d + 1):
if dd % r:
item = ' --- '
else:
item = '{:2},{:2}'.format(*cards_and_symbols(d, r))
row.append(item)
print(' '.join(row))
if __name__ == "__main__":
spotit_table()
#!/usr/bin/env python3
''' symcombo_limited_spotit
Generate Spot-It decks by recursive backtracking
Make each card by reusing one symbol from each card already in the deck
and then append combinations from symbols that haven't been used yet.
Not very fast.
Written by PM 2Ring 2017.09.15
'''
import sys
from itertools import combinations, product
from collections import Counter
import spotit_tools as st
def solve(d, r, c, syms, counts, deck):
n = len(deck)
if n == c:
return deck
pools = [[u for u in card if counts[u] < r] for card in deck]
for head in product(*pools):
head = set(head)
headlen = len(head)
if headlen > d:
continue
st.progress(n, 100)
for tail in combinations(syms, d - headlen):
card = head.union(tail)
if all(len(card & u) == 1 for u in deck):
counts.update(card)
result = solve(d, r, c, syms - card, counts, deck + [card])
counts.subtract(card)
if result:
return result
def make_deck(d, r, c, s):
syms = set(range(s))
counts = Counter()
deck = solve(d, r, c, syms, counts, [])
print(file=sys.stderr)
return deck
def main():
if len(sys.argv) != 3:
print('Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
print('Combinations to test={}'.format(st.nCr(s, d)))
deck = make_deck(d, r, c, s)
if deck is None:
print('No solution found')
sys.exit()
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' symcombo_spotit
Generate Spot-It decks by recursive backtracking, using searches
over all combinations of symbols that can make up a card.
There should be a way of jumping over combinations that won't be
valid because they match too many entries of the previous card(s)
Written by PM 2Ring 2017.09.15
'''
import sys
from itertools import combinations
import spotit_tools as st
def solve(d, syms, deck):
if not syms:
return deck
n = len(deck)
for card in combinations(set(syms), d):
st.progress(n, 10000)
card = set(card)
if all(len(card & u) == 1 for u in deck):
newsyms = list(syms)
for sym in card:
newsyms.remove(sym)
result = solve(d, newsyms, deck + [card])
if result:
return result
def make_deck(d, r, c, s):
deck = solve(d, list(range(s)) * r, [])
print(file=sys.stderr)
return deck
def main():
if len(sys.argv) != 3:
print('Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
print('Combinations to test={}'.format(st.nCr(s, d)))
deck = make_deck(d, r, c, s)
if deck is None:
print('No solution found')
sys.exit()
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
#!/usr/bin/env python3
''' symcount_spotit
Generate Spot-It decks by recursive backtracking, using symbol counts
We scan the list of cards (d-length groups of symbols), searching for a
card that won't put any of the current symbol counts over the limit.
When we find such a card we add it to the deck and eliminate all
remaining cards that don't have exactly one matching symbol with
the current card and then recurse to find the subsequent cards.
We initialise the deck with the card `set(range(d))`, this also
reduces the size of the initial card list.
Written by PM 2Ring 2017.09.09
'''
import sys
from itertools import combinations, product
from collections import Counter
import spotit_tools as st
def solve(r, c, X, counts, deck):
dlen = len(deck)
if dlen == c:
return deck
used = {u for u, v in counts.items() if v == r}
for card in X:
st.progress(dlen)
if not card & used:
counts.update(card)
newX = [u for u in X if len(u & card) == 1]
result = solve(r, c, newX, counts, deck + [card])
if result:
return result
counts.subtract(card)
def make_deck(d, r, c, s):
card = set(range(d))
deck = [card]
k = ({u} for u in range(d))
X = [u.union(v) for u, v in product(k, combinations(range(d, s), d - 1))]
print('Initial set size:', len(X))
counts = Counter(card)
deck = solve(r, c, X, counts, deck)
print(file=sys.stderr)
return deck
def main():
if len(sys.argv) != 3:
print('Spot-It deck finder.\nUsage:\n'
'%s symbols_per_card repeats' % sys.argv[0])
sys.exit()
d, r = map(int, sys.argv[1:])
result = st.cards_and_symbols(d, r)
if result is None:
print('Invalid args, aborting', file=sys.stderr)
sys.exit()
c, s = result
print('Cards={}, Spots={}, Symbols={}, Repeats={}'.format(c, d, s, r))
deck = make_deck(d, r, c, s)
for i, k in enumerate(deck):
print('{:2}: {}'.format(i, k))
if st.check_size(deck, c) and st.check_counts(deck, r, s):
if st.test_matches(deck):
st.incidence_matrix(deck, s)
st.pair_matrix(deck)
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.