Instantly share code, notes, and snippets.

# PM2Ring/algorithmx_spotit.py Created Sep 27, 2017

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_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()