#!/usr/bin/python -utt
# vim:et

'''
Parameters: M, REQUIRED: number of symbols per card;
            N, REQUIRED: number of symbols in alphabet.

Determine number of cards in a "spot it" deck, if
each card has exactly M symbols out of an alphabet of N.

------------------------------------------------------------------------
    Copyright (C) 2013 Collin Park

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    For a copy of the GNU General Public License, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
------------------------------------------------------------------------

Originally I thought this program would be a general-purpose
one, whereby one could try various values of M and N in an
effort to find the "optimum" value of M given N or vice versa.

But two things happened: First, I figured out that the "optimum"
value of N for a given M is M(M-1)+1 -- at least when M-1 is prime;
second, I realized that the algorithm doesn't always work for values
of M>5.

Now, if you specify numbers such that N=M(M-1)+1. and M-1 is prime,
the code rapidly calculates a list of which symbols could be on each
card in the case.  If these conditions are not both met, then the 
program may or may not work.'''

import sys

DEBUG = False

myletters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
alphabet = list(myletters)


def main(M, N):
    '''Find a maximal(?) set of "cards", where each "card" in
    the deck has M symbols out of a set of N possible.'''
    deck = list()
    # Internally, use numbers 0..(N-1) for symbols.
    # Use alphabet when displaying for human eyes.
    if (M >= N):
        usage("M=%d, N=%d but M must be strictly less than N" % (M, N))

    # Ensure alphabet is long enough
    global alphabet
    for one in myletters:
        if len(alphabet) >= N:
            break
        alphabet += [one + X for X in myletters]

    # Put first card into the deck, then add the rest
    deck.append(range(M))      # first card

    # BUT FIRST though decide whether we can do the optimal thing.
    for afactor in range(2, M-1):
        if (M-1) % afactor == 0:
            p_is_prime = False
            break
    else:
        p_is_prime = True

    # NOW we can add the rest of the cards in the deck
    for first in range(N-M+1):
        do_next([first], M, N, deck, p_is_prime)

    # Done!
    dump_cards(deck)
    sys.exit(0)

def card_2_str(acard):
    '''Give a string representation of a card.'''
    return ', '.join([alphabet[X] for X in acard])

def dump_cards(deck):
    '''Print the list of cards using /alphabet/'''
    print "%d cards total" % len(deck)
    for acard in deck:
        print card_2_str(acard)

def do_next(pref, M, N, deck, p_is_prime):
    '''Given a partly-filled in card with symbols /pref/ (short for "prefix"),
    fill in the rest of the symbols on that card and append to /deck/.
    If /p_is_prime/ (i.e., M-1 is prime) and N=M(M-1)+1 then use the
    optimal algorithm, which runs really fast and actually works.
    Otherwise, use a simple algorithm, which works up to 5,21.
    Beyond that, it doesn't work and NEEDS TO BE FIXED.'''

    num_left = M - len(pref)
    if pref[0] > 1 and len(pref) == 2 and p_is_prime and N == M * (M-1) + 1:
        # Fill in the rest of this card ASS-U-ME-ing we're Optimal :)
        do_optimal(pref, M, deck)
        return

    # Not using optimal algorithm, so instead try each possible next symbol
    # This algorithm doesn't always work :(
    for next_sym in range(pref[-1]+1, N-num_left+1):
        poss = pref + [next_sym]
        for acard in deck:
            n_over = overlaps(acard, poss)
            if n_over > 1:
                break
            if n_over == 0 and num_left == 1:
                # Shouldn't ever happen
                if DEBUG:
                    print "DBG: no overlap:", acard, poss
                break
        else:
            # Success!  At least so far.
            if num_left == 1:
                # Real success.  Append a card and we're done!
                if DEBUG:
                    print "DBG: appending", poss
                deck.append(poss)
                return
            else:
                if DEBUG:
                    print "DBG: trying", poss
                do_next(poss, M, N, deck, p_is_prime)


def do_optimal(pref, M, deck):
    '''If N=M(M-1)+1 and M-1 is prime, and pref[0] is "C" or greater
    and /pref/ has exactly two symbols, just fill in the rest of
    this card.'''
    poss = list(pref)                   # I want to say pref[:]
    p = M - 1
    delta = p + (pref[0] - 1)           # e.g. p for B-x-..., p+1 for C-x-x...
    max_here = 2 * p                    # for this sym I'm adding
    for s_num in range(2, M):
        it = poss[-1] + delta
        max_here += p
        if it > max_here:               # i.e., if fell off right-hand edge
            it -= p
        poss.append(it)
    # Sanity check
    for acard in deck:
        if overlaps(acard, poss) != 1:
            print "WHOA: overlap wrong:\n\t%s\n\t%s" % \
                    tuple([card_2_str(X) for X in [acard, poss]])
            print "ABORTING"
            dump_cards(deck)
            sys.exit(1)
    deck.append(poss)

def overlaps(c1, c2):
    '''number of syms in common between c1 and c2.
    Initial implementation is simple; fix only if performance issue arises.'''
    return len([X for X in c1 if X in c2])

def usage(msg=None):
    if msg is not None:
        print "\n*** %s\n" % msg
    print "Usage: %s M N" % sys.argv[0]
    print __doc__
    sys.exit(1)

if __name__ == '__main__':
    try:
        if sys.argv[1] == '-d':
            DEBUG = True
            sys.argv.pop(1)
        [M, N] = [int(X) for X in sys.argv[1:]]
    except:
        usage("You must supply exactly two numbers.")
    main(M, N)
    sys.exit(0)