SpotIt Stuff

algorithmx_spotit.py

#!/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()

galois.py

#!/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()])

galois_spotit.py

#!/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()

grid_spotit.py

#!/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()

minimal_modpoly.py

#!/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))

paircombo_spotit.py

#!/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()

prime_spotit.py

#!/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()

random_spotit.py

#!/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()

simple_spotit.py

#!/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.txt

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.

spotit_tools.py

#!/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()

symcombo_limited_spotit.py

#!/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()

symcombo_spotit.py

#!/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()

symcount_spotit.py

#!/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()

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.

Galois poly finder using Sage.