Created
September 27, 2017 11:12
-
-
Save PM2Ring/c758d5ba782f3e6b5eeddb49432dc71b to your computer and use it in GitHub Desktop.
SpotIt Stuff
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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()]) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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)) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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
There's a bug in minimal_modpoly.py. Fortunately, it doesn't affect any of the pre-computed primitive polynomials. So if you want to run galois_spoitit.py with q>150 you'll need to get a poly from elsewhere. Eg, Wolfram Alpha
primitive polynomial GF(169)
gives x²+x+2, which is [2, 1, 1] in my notation.