#!/usr/bin/env python
#================================================================
# kkck: A solver for Kriss Kross puzzles.  For documentation, see
#   http://www.nmt.edu/tcc/help/lang/python/examples/kkck/kkck.html
#================================================================
PROGRAM_NAME = "kkck"
EXTERNAL_VERSION = "0.0"
VERBOSE = False        # For logorrheic output
#================================================================
# Imports
#----------------------------------------------------------------

import sys
from collections import defaultdict
UNK_CELL = '#'
COMMENT_CHAR = '!'
#================================================================
# Functions and classes
#----------------------------------------------------------------


# - - -   m a i n

def main():
    '''Kriss Kross puzzle solver, main procedure.

      [ sys.argv names one readable, valid Kriss Kross puzzle file ->
          sys.stdout  +:=  (solution(s) to the puzzle, if any) +
                           (number of solutions)
        else ->
          sys.stderr  +:=  error message(s) ]
    '''
    print "===== %s %s =====" % (PROGRAM_NAME, EXTERNAL_VERSION)

    #-- 1 --
    # [ if sys.argv names one readable file ->
    #     inFile  :=  that file, opened for reading
    #   else ->
    #     sys.stderr  +:=  error message(s)
    #     stop execution ]
    argList = sys.argv[1:]
    if len(argList) == 1:
        try:
            inFileName = argList[0]
            inFile = file ( inFileName )
        except IOError, detail:
            fatal ( "Couldn't open input file '%s': %s" %
                    (inFileName, detail) )
    else:
        usage () 
    #-- 2 --
    # [ if inFile contains a valid puzzle file ->
    #     puzzle  :=  a Puzzle instance representing that file
    #   else ->
    #     sys.stderr  +:=  error message(s)
    #     stop execution ]
    try:
        puzzle = Puzzle ( inFile )
    except SyntaxError, detail:
        fatal ( "Terminated due to puzzle syntax errors: %s" %
                detail )
    print "=== Initial state"
    print puzzle.show()
    #-- 3 --
    nSolutions  =  0

    #-- 4 --
    # [ nSolutions  +:=  number of solutions of puzzle, if any
    #   sys.stdout  +:=  solutions of puzzle, if any ]
    for solution in puzzle.genSolutions():
        nSolutions += 1
        print "\n=== Solution #%d" % nSolutions
        print solution.show()

    #-- 5 --
    # [ sys.stdout  +:=  nSolutions ]
    print "=== Total number of solutions: %d" % nSolutions
# - - -   u s a g e

def usage():
    '''Display correct command line argument usage

      [ sys.stderr  +:=  error message showing command line usage
        stop execution ]
    '''
    fatal ( "Takes one argument, the name of the puzzle file." )
# - - -   f a t a l

def fatal ( *L ):
    '''Write an error message and stop.

      [ L is a list of strings ->
          sys.stderr  +:=  concatenated elements of L
          stop execution ]
    '''
    print >>sys.stderr, "*** Error: %s" % (''.join(L))
    sys.exit(1)
# - - -   s h o w I s V

def showIsV(isV):
    '''Translate an orientation code

      [ if isV == 0 ->
          return 'H'
        else ->
          return 'V' ]
    '''
    return "HV"[isV]
# - - -   p e r p e n d i c u l a r

def perpendicular ( isV ):
    '''Invert an 'isV' flag.

      [ if isV is 0 ->
          return 1
        if isV is 1 ->
          return 0 ]
    '''
    return 1-isV

# - - - - -   c l a s s   P u z z l e

class Puzzle(object):
    '''Represents a Kriss Kross puzzle and solving mechanism.

      Exports:
        Puzzle ( inFile ):
          [ inFile is a readable file ->
              if inFile contains a valid puzzle file ->
                return a new Puzzle instance representing that file
              else ->
                raise SyntaxError ]
        .inFile:   [ as passed to constructor, read-only ]
        .size:
          [ the count of rows and columns in the puzzle, as a
            Coords instance ]
        .show():
          [ return the current state of the puzzle, in the same
            format as the input framework, as a multi-line string ]
        .whatCell ( coord ):
          [ coord is a Coord instance ->
              if there is a cell at coord ->
                return the Cell instance at that location
              else -> return None ]
        .genCells(): [ generate the cells in self, in ascending order ]
        .whatSlots ( coord ):
          [ coord is a Coord instance ->
              generate all the slots that contain coord, as
              Slot instances, if any ]
        .scan ( j, isV ):
          [ (isV is 0 for horizontal, 1 for vertical) and
            (j is a valid index for dimension isV) ->
              generate the coordinates of row or column j as
              a sequence of Coord instances ]
        .nSlots():
          [ returns the number of slots in self ]
        .genSolutions():
          [ generate a sequence of Puzzle instances representing
            the solutions to self, if any ]
      State/Invariants:
        .__wordBank:
          [ a WordBank instance representing the word list and
            the state of solution ]
        .__cellMap:
          [ a dictionary whose keys are (row, column) tuples
            representing the coordinates in self where characters
            can go, and the associated value is a Cell instance
            representing what is at that coordinate ]
        .__slotMap:
          [ a dictionary whose keys are (row, column, isV),
            where (row, column) is the location of the first position
            in a slot in self and isV is 0 for horizontal, 1 for
            vertical, and the associated value is a Slots
            instance representing a slot with that origin and
            orientation ]
        .__firstSlot:
          [ the first slot in self ]
        .__slotSuccessor:
          [ a dictionary whose keys are all the slots in self,
            and each related value is the successor of that slot
            in the sequence, or None for the last slot ]
    '''
# - - -   P u z z l e . _ _ i n i t _ _

    def __init__ ( self, inFile ):
        '''Read and initialize the puzzle.
        '''
        #-- 1 --
        self.inFile = inFile
        self.size = Coord ( 0, 0 )
        self.__cellMap = {}
        self.__slotMap = {}
        #-- 2 --
        # [ if inFile contains a valid puzzle file ->
        #     inFile  :=  inFile advanced to end of file
        #     self.size[0]  :=  max ( self.size[0], number of
        #         rows in the framework part of inFile )
        #     self.size[1]  :=  max ( size[1], length of
        #         longest row in the framework part of inFile )
        #     self.__cellMap  +:=  entries mapping cell
        #         coordinates from inFile to new Cell instances
        #     self.__slotMap  +:=  entries mapping slot
        #         coordinates from inFile to new Slot instances
        #     self.__wordBank  :=  a new WordBank instance
        #         representing the word list from inFile, with
        #         no initial slot choices
        #   else -> raise SyntaxError ]
        self.__input ( inFile )
        inFile.close()
        #-- 3 --
        # [ self.__wordBank  +:=  choices for slots in
        #       self.__slotMap that are consistent with any
        #       clues in self.__cellMap ]
        self.__buildChoices()
# - - -   P u z z l e . _ _ i n p u t

    def __input ( self, inFile ):
        '''Read the puzzle, set up the empty skeleton.

          [ inFile is a readable file ->
              if inFile contains a valid puzzle file ->
                inFile  :=  inFile advanced to end of file
                self.size[0]  :=  max ( self.size[0], number of
                    rows in the framework part of inFile )
                self.size[1]  :=  max ( self.size[1], length of
                    longest row in the framework part of inFile )
                self.__cellMap  +:=  entries mapping cell
                    coordinates from inFile to new Cell instances
                self.__slotMap  +:=  entries mapping slot
                    coordinates from inFile to new Slot instances
                self.__wordBank  :=  a new WordBank instance
                    representing the word list from inFile, with
                    no initial slot choices
              else -> raise SyntaxError ]
        '''
        #-- 1 --
        # [ if inFile contains at least one blank line ->
        #     inFile  :=  inFile advanced to end of file
        #     rawGrid  :=  lines from inFile up to the first
        #         blank line
        #     rawWords  :=  lines following the first blank line,
        #         newlines and comments removed
        #   else -> raise SyntaxError ]
        rawGrid, rawWords = self.__readFile ( inFile )

        #-- 2 --
        # [ if rawGrid is a valid framework section ->
        #     self.size[0]  :=  max ( self.size[0], number of
        #         rows in rawGrid )
        #     self.size[1]  :=  max ( size[1], length of
        #         longest row in rawGrid )
        #     self.__cellMap  +:=  entries for the cells in rawGrid        
        #     self.__slotMap  +:=  entries for the slots in rawGrid
        #   else -> raise SyntaxError ]
        self.__digestGrid ( rawGrid )

        #-- 3 --
        # [ if (rawWords is a valid word list) and
        #   (the counts and lengths of the word list match the
        #   counts and lengths of slots in self.__slotMap) ->
        #     self.__wordBank  :=  a WordBank instance representing
        #         the words in rawWords
        #   else -> raise SyntaxError ]
        self.__digestWords ( rawWords )
# - - -   P u z z l e . _ _ r e a d F i l e

    def __readFile ( self, inFile ):
        '''Split the file into framework and word list portions.

          [ inFile is a readable file ->
              if inFile contains at least one blank line ->
                inFile  :=  inFile advanced to end of file
                return ((list of non-comment lines from inFile up
                to the first blank line), (list of lines after the
                first blank line))
              else -> raise SyntaxError ]
        '''
        #-- 1 --
        # [ inFile  :=  inFile advanced to end of file
        #   lineList := lines from inFile as strings with
        #       trailing whitespace trimmed, ignoring lines
        #       that start with COMMENT_CHAR ]
        lineList = [ line.rstrip()
                     for line in inFile
                     if ( (len(line) == 0) or
                          (line[0] != COMMENT_CHAR) ) ]

        #-- 2 --
        # [ if lineList contains any empty strings ->
        #     terminus  :=  the index of the first such string
        #   else -> raise SyntaxError ]
        try:
            terminus = lineList.index('')
        except ValueError:
            raise SyntaxError ( "There must be a blank line between"
                                "frame and word list." )

        #-- 3 --
        return (lineList[:terminus], lineList[terminus+1:])
# - - -   P u z z l e . _ _ d i g e s t G r i d

    def __digestGrid ( self, rawGrid ):
        '''Parse the framework section of the puzzle file.

          [ rawGrid is a list of nonempty strings ->
              if rawGrid is a valid framework section ->
                self.size[0]  :=  max ( self.size[0], number of
                    rows in rawGrid )
                self.size[1]  :=  max ( size[1], length of
                    longest row in rawGrid )
                self.__cellMap  +:=  entries for the cells in rawGrid
                self.__slotMap  +:=  entries for the slots in rawGrid
              else -> raise SyntaxError ]
        '''
        #-- 1 --
        # [ self.__cellMap  +:=  entries for nonblank characters
        #       in rawGrid
        #   self.size[1]  :=  max ( self.size[1], longest line
        #       in rawGrid )
        #   self.size[0]  +:=  number of lines in rawGrid ]
        for line in rawGrid:
            #-- 1 body --
            # [ self.__cellMap  +:=  entries for nonblank
            #       characters in line for row self.size[0]
            #       and the same columns as line
            #   self.size[0]  +:= 1
            #   self.size[1]  :=  max ( self.size[1], len(line) ) ]
            self.__gridLine ( line )

        #-- 2 --
        if self.size[0] == 0:
            raise SyntaxError ( "Empty puzzle frame." )
        print ( "=== Puzzle size: %d rows, %d columns." %
                (self.size[0], self.size[1]) )
        #-- 3 --
        # [ self.__slotMap  +:=  entries for the slots in
        #       self.__cellMap ]
        self.__findSlots()
# - - -   P u z z l e . _ _ g r i d L i n e

    def __gridLine ( self, line ):
        '''Scan one line of the framework.

          [ line is a nonempty string ->
             self.__cellMap  +:=  entries for nonblank
                 characters in line for row self.size[0]
                 and the same columns as line
             self.size[0]  +:= 1
             self.size[1]  :=  max ( self.size[1], len(line) ) ]
        '''
        #-- 1 --
        # [ self.__cellMap  +:=  entries for nonblank
        #       characters in line for row self.size[0]
        #       and the same columns as line ]
        for colx in range(len(line)):
            #-- 1 body --
            # [ if line[colx] is nonblank ->
            #     self.__cellMap[self.size[0], colx]  :=
            #         a new Cell instance at (self.size[0], colx)
            #         with text line[colx]
            #   else -> I ]
            text = line[colx]
            if text != ' ':
                rowx = self.size[0]
                coord = Coord ( rowx, colx )
                self.__cellMap[(rowx, colx)] = Cell ( coord, text )
        #-- 2 --
        self.size[0] += 1
        self.size[1] = max ( self.size[1], len(line) )
# - - -   P u z z l e . _ _ f i n d S l o t s

    def __findSlots ( self ):
        '''Find all horizontal and vertical slots

          [ self.__cellMap contains a set of Cells ->
              self.__slotMap  +:=  entries for the slots in
                  self.__cellMap ]
        '''
        #-- 1 --
        for rowx in range(self.size[0]):
            #-- 1 body --
            # [ self  :=  self with any horizontal slots in
            #       row (rowx) added ]
            for start, length in self.__genClumps ( rowx, 0 ):
                #-- 1.1 body --
                # [ (start is the starting coordinate of a slot) and
                #   (length is the length of a slot) ->
                #      self  :=  self with a horizontal slot added in
                #          columns [start:start+length] ]
                self.__addSlot ( 0, Coord(rowx, start), length )

        #-- 2 --
        for colx in range(self.size[1]):
            #-- 2 body --
            # [ self  :=  self with any vertical slots in
            #       column (colx) added ]
            for start, length in self.__genClumps ( colx, 1 ):
                #-- 2.1 body --
                # [ (start is the starting coordinate of a slot) and
                #   (length is the length of a slot) ->
                #      self  :=  self with a vertical slot added in
                #          columns [start:start+length] ]
                self.__addSlot ( 1, Coord(start, colx), length )
        #-- 3 --
        # [ self.__firstSlot  :=  as invariant
        #   self.__slotSuccessor  :=  as invariant ]
        slotList = self.__slotMap.values()
        slotList.sort()
        self.__firstSlot = slotList[0]
        self.__slotSuccessor = {}
        for i in range(len(slotList)-1):
            self.__slotSuccessor[slotList[i]] = slotList[i+1]
        self.__slotSuccessor[slotList[-1]] = None
# - - -   P u z z l e . _ _ g e n C l u m p s

    def __genClumps ( self, j, isV ):
        '''Generate multi-cell clumps in a row or column.

          [ (isV is 0 for horizontal, 1 for vertical) and
            (j is a valid row or column index for that
            orientation) ->
              generate (start, length) tuples for all contiguous
              groups of two or more cells in that orientation
              from self.__cellMap ]
        '''
        #-- 1 --
        # [ mask  :=  a list containing 1s where row or column j
        #       has cells, 0s where it has no cells, with one
        #       extra 0 appended ]
        mask = [ self.whatCell ( coord ) is not None
                 for coord in self.scan ( j, isV ) ]
        mask.append ( 0 )

        #-- 2 --
        # [ generate (start, length) tuples for consecutive
        #   groups of two or more 1s in mask ]
        start = None
        for i in range(len(mask)):
            if mask[i]:
                if start is None:
                    start = i
            else:
                if start is not None:
                    if (i-start) > 1:
                        yield (start, i-start)
                start = None

        #-- 3 --
        raise StopIteration
# - - -   P u z z l e . _ _ a d d S l o t

    def __addSlot ( self, isV, start, length ):
        '''Add a new slot to self.

          [ (isV is 0 for horizontal, 1 for vertical) and
            (start is the starting coordinate of a slot as a
            Coord instance) and
            (length is the length of the slot) ->
              self  :=  self with a slot added starting at start
                  and extending in direction isV for length cells ]
        '''
        #-- 1 --
        # [ slot  :=  a new Slot instance with origin (start),
        #       length (length), and orientation (isV) ]
        slot = Slot ( start, length, isV )
        if VERBOSE:
            print ( "=== Creating %s" % slot )

        #-- 2 --
        self.__slotMap[(start[0], start[1], isV)]  =  slot
        
        #-- 3 --
        # [ self  :=  self with all cells that are part of slot
        #       linked to slot ]
        for coord in slot.genCoords():
            cell = self.whatCell ( coord )
            cell.addSlot ( slot )
# - - -   P u z z l e . _ _ d i g e s t W o r d s

    def __digestWords ( self, rawWords ):
        '''Feed the word list to the WordBank instance.

          [ rawWords is a list of strings ->
              if (rawWords is a valid word list) and
              (the counts and lengths of the word list match the
              counts and lengths of slots in self.__slotMap) ->
                self.__wordBank  :=  a WordBank instance representing
                    the words in rawWords
              else -> raise SyntaxError ]
        '''
        #-- 1 --
        # [ self.__wordBank  :=  a new, empty WordBank instance
        #       using self's geometry ]
        self.__wordBank = WordBank ( self )
        #-- 2 --
        # [ if rawWords contains the UNK_CELL character ->
        #     raise SyntaxError
        #   else ->
        #     self.__wordBank  +:=  whitespace-separated words
        #         from rawWords ]
        for line in rawWords:
            wordList = line.split()
            for word in wordList:
                if UNK_CELL in word:
                    raise SyntaxError ( "Words may not contain the "
                        "'%d' symbol; that denotes an unsolved "
                        "letter." % UNK_CELL )
                if len(word) < 2:
                    raise SyntaxError ( "One-letter words such as "
                        "'%s' are not allowed." % word )
                self.__wordBank.addWord ( word )
        #-- 3 --
        # [ if (the counts of slots of each length in self.__slotMap
        #   do not exactly match the counts of words of each length
        #   in self.__wordBank) ->
        #     raise SyntaxError
        #   else -> I ]
        self.__matchLengths()
# - - -   P u z z l e . _ _ m a t c h L e n g t h s

    def __matchLengths ( self ):
        '''See if the word lengths match the slot lengths.

          [ (self.__slotMap contains a set of slots) and
            (self.__wordMap contains a set of words) ->
              if (the counts of slots of each length in self.__slotMap
              do not exactly match the counts of words of each length
              in self.__wordBank) ->
                raise SyntaxError
              else -> I ]
        '''
        #-- 1 --
        # [ if the number of words in self is the same as the 
        #   number of slots in self ->
        #     I
        #   else -> raise SyntaxError ]
        if len(self.__slotMap) != len(self.__wordBank):
            raise SyntaxError ( "This puzzle has %d slots but "
                "%d words to go in them." %
                (len(self.__slotMap), len(self.__wordBank)) )
        #-- 2 --
        # [ countByLen  :=  a dictionary whose keys are the
        #       unique lengths of slots in self, and each
        #       corresponding value is the number of slots in
        #       self that have that length ]
        countByLen = defaultdict(int)
        for slot in self.__slotMap.values():
            countByLen[len(slot)] += 1
        #-- 3 --
        # [ if the counts of slots of each length in countByLen
        #   correspond exactly to the counts of words of each
        #   length in self.__wordBank ->
        #     I
        #   else -> raise SyntaxError ]
        for length in range(2, 1+self.__wordBank.maxLen):
            nWords = self.__wordBank.wordsOfLen ( length )
            nSlots = countByLen[length]
            if nWords != nSlots:
                raise SyntaxError ( "There are %d words of length %d, "
                    "but there are %d slots of that length." %
                    (nWords, length, nSlots) )
# - - -   b u i l d C h o i c e s

    def __buildChoices ( self ):
        '''Define the initial word choices for each slot.

          [ self.__cellMap and self.__slotMap are as invariants ->
              self.__wordBank  +:=  choices for slots in
                  self.__slotMap that are consistent with any
                  clues in self.__cellMap ]
        '''
        #-- 1 --
        # [ slotList  :=  slots in self, sorted ]
        slotList = self.__slotMap.values()
        slotList.sort()

        #-- 2 --
        for slot in self.__slotMap.values():
            #-- 2 body --
            # [ self.__wordBank  +:=  choices for slot that are
            #       consistent with any clues in self.__cellMap ]
            self.__buildSlotChoices ( slot )
# - - -   P u z z l e . _ _ b u i l d S l o t C h o i c e s

    def __buildSlotChoices ( self, slot ):
        '''Populate a slot with all its initial choices.

          [ slot is a Slot in self ->
              self.__wordBank  +:=  choices for slot that are
                  consistent with any clues in self.__cellMap ]
        '''
        #-- 1 --
        # [ choiceList  :=  all the words from self.__wordBank
        #       of length len(slot), as a set of Word instances ]
        choiceList  =  set ( [ word
            for word in self.__wordBank.genCandidates(len(slot)) ] )
        #-- 2 --
        # [ choiceList  :=  choiceList - (any choices that
        #       conflict with clues that may exist in any of the
        #       Cell instances lying within slot) ]
        for k in range(len(slot)):
            #-- 2 body --
            # [ if the cell at slot[k] contains a clue letter ->
            #     choiceList  :=  choiceList - (any word not
            #         having that letter at position [k])
            #   else -> I ]
            self.__clueCheck ( choiceList, slot, k )
        #-- 3 --
        for choice in choiceList:
            self.__wordBank.mayBe ( slot, choice )

        if VERBOSE:
            print "    = %s: " % slot,
            for choice in sorted(list(choiceList)):
                print choice,
            print
# - - -   P u z z l e . _ _ c l u e C h e c k

    def __clueCheck ( self, choiceList, slot, k ):
        '''Eliminate choices inconsistent with clue at position k.

          [ (choiceList is a set of Word instances) and
            (slot is a Slot instance) and
            (k is a position within slot) ->
                if the cell at slot[k] contains a clue letter ->
                    choiceList  :=  choiceList - (any word not
                        having that letter at position [k])
                    else -> I ]
        '''
        #-- 1 --
        # [ coord  :=  the Coord instance in self corresponding to
        #       index [k] in slot ]
        coord = slot[k]

        #-- 2 --
        # [ cell  :=  the Cell instance in self at coord ]
        cell = self.whatCell ( coord )
        #-- 3 --
        if cell.text == UNK_CELL:
            return
        else:
            clueLetter = cell.text
        #-- 4 --
        # [ choiceList  :=  choiceList - (elements that do
        #      not have (clueLetter) in position [k]) ]
        for choice in list(choiceList):
            if choice[k] != clueLetter:
                choiceList.remove ( choice )
# - - -   P u z z l e . s h o w

    def show ( self ):
        '''Return the puzzle state as a multi-line string.
        '''
        #-- 1 --
        rowList = []

        #-- 2 --
        # [ rowList  +:=  (tens digit line) + (units digit line)
        #                 (frame line), all sized for self.size ]
        self.__showColHeads ( rowList )
        self.__showRule ( rowList )

        #-- 3 --
        for rowx in range(self.size[0]):
            #-- 3 body --
            # [ rowx is a row index in self ->
            #     rowList  +:=  row labels + frame + (puzzle state
            #                   for row (rowx)) + frame ]
            self.__showRow ( rowList, rowx )

        #-- 4 --
        # [ rowList  +:=  (frame line) ]
        self.__showRule ( rowList )

        #-- 5 --
        if VERBOSE:
            self.showAllChoices()
        return '\n'.join ( rowList )
# - - -   P u z z l e . _ _ s h o w C o l H e a d s

    def __showColHeads ( self, rowList ):
        '''Add column headings to .show() output
        '''
        #-- 1 --
        # [ rowList  +:=  tens-digit line ]
        L = [ ' '*3 ]
        tensCount = (self.size[1]/10)+1
        for tens in range(tensCount):
            L.append ( "%d%s" % (tens, ' '*19) )
        rowList.append ( ''.join(L).rstrip() )

        #-- 2 --
        # [ rowList  +:=  units-digit line ]
        L = [ ' '*3 ]
        for colx in range(self.size[1]):
            L.append ( str(colx%10) )
            L.append ( ' ' )
        rowList.append ( ''.join(L) )
# - - -   P u z z l e . _ _ s h o w R u l e

    def __showRule ( self, rowList ):
        '''Add the line that appears above and below the puzzle body.
        '''
        rowList.append ( "%s+%s+" %
                         (' '*2, '-'*(self.size[1]*2-1)) )
# - - -   P u z z l e . _ _ s h o w R o w

    def __showRow ( self, rowList, rowx ):
        '''Display the [rowx]th row of the puzzle's state
        '''
        #-- 1 --
        # [ L  :=  a list containing the row label ]
        L = [ '%02d|' % rowx ]

        #-- 2 --
        # [ L  +:=  characters illustrating the puzzle's state
        #           in row (rowx) ]
        for colx in range(self.size[1]):
            #-- 2 body --
            # [ if puzzle is empty at (rowx, colx) ->
            #     L  +:=  one space
            #   else if puzzle has a single choice at (rowx, colx) ->
            #     L  +:=  that character
            #   else ->
            #     L  +:=  UNK_CELL ]
            textSet = self.__wordBank.cellChoices ( Coord(rowx, colx) )
            text = ''.join(list(textSet))
            if len(text) == 1:
                L.append ( text )
            else:
                L.append ( UNK_CELL )
            L.append (' ')

        #-- 3 --
        L.pop()
        L.append ( "|")

        #-- 4 --
        rowList.append ( ''.join(L) )
# - - -   P u z z l e . s h o w A l l C h o i c e s

    def showAllChoices ( self ):
        '''Display all slots and their current choices.
        '''
        slotList = self.__slotMap.values()
        slotList.sort()
        for slot in slotList:
            print "  == Choices for %s" % slot
            wordList = [ slot
                for slot in self.__wordBank.genSlotChoices ( slot ) ]
            wordList.sort()
            for word in wordList:
                print word,
            print
# - - -   P u z z l e . w h a t C e l l

    def whatCell ( self, coord ):
        '''Is there a cell at a given location?
        '''
        #-- 1 --
        try:
            return self.__cellMap[(coord[0], coord[1])]
        except KeyError:
            return None
# - - -   g e n C e l l s

    def genCells ( self ):
        '''Generate self's cells, in sorted order
        '''
        for cell in sorted ( self.__cellMap.values() ):
            yield cell
        raise StopIteration
# - - -   P u z z l e . w h a t S l o t s

    def whatSlots ( self, coord ):
        '''Generate the slots that include a given location.
        '''
        #-- 1 --
        # [ if self has a cell at location (coord) ->
        #     cell  :=  that cell as a Cell instance
        #   else ->
        #     raise StopIteration ]
        cell = self.whatCell ( coord )
        if cell is None:
            raise StopIteration

        #-- 2 --
        for slot in cell.genSlots():
            yield slot

        #-- 3 --
        raise StopIteration
# - - -   P u z z l e . s c a n

    def scan ( self, k, isV ):
        '''Scan across row k (isV==0) or down column k (isV==1)
        '''
        #-- 1 --
        # [ if isV is 0 ->
        #     opp  :=  1
        #     limit  :=  self.size[1]
        #   else ->
        #     opp  :=  0
        #     limit  :=  self.size[0] ]
        opp = perpendicular ( isV )
        limit = self.size[opp]
        #-- 2 --
        # [ if isV is 0 ->
        #     start  :=  row k, column 0, as a Coord
        #     step  :=  step 0 rows, 1 column
        #   else ->
        #     start  :=  row 0, column k, as a Coord
        #     step  :=  step 1 rows, 0 columns ]
        start = Coord ( opp*k, isV*k )
        step = Coord ( isV, opp )

        #-- 3 --
        # [ generate values start, start+step, start+step*2, ...,
        #   limit-1 ]
        for i in range(limit):
            yield start
            start += step
# - - -   P u z z l e . n S l o t s

    def nSlots ( self ):
        '''Return the number of slots in self.
        '''
        return len(self.__slotMap)
# - - -   P u z z l e . g e n S o l u t i o n s

    def genSolutions ( self ):
        '''Generate the solution(s) to self, if any.
        '''
        #-- 1 --
        # [ if cyclic reduction solves self ->
        #     self  :=  self in solved state
        #     yield self in solved state
        #     raise StopIteration
        #   else -> I ]
        if VERBOSE: print "=== Cyclic reduction phase"
        if self.__cyclicReduction():
            yield self
            raise StopIteration
        #-- 2 --
        # [ generate solutions to self starting with self's
        #   current state ]
        if VERBOSE: print "=== Recursive solution phase"
        for solution in self.__recurSolver ( self.__firstSlot ):
            yield solution

        #-- 3 --
        raise StopIteration
# - - -   P u z z l e . _ _ c y c l i c R e d u c t i o n

    def __cyclicReduction ( self ):
        '''Eliminate choices wherever two slots intersect.
        
          [ if cyclic reduction solves self ->
              self  :=  self in solved state
              return True
            else -> return False ]
        '''
        #-- 1 --
        while 1:
            #-- 1 body --
            # [ if comparison of all intersecting slots does not
            #   reduce the total set of choices in self.__wordBank ->
            #     return False
            #   else if removing those choices solves the puzzle ->
            #     return True
            #   else -> I ]
            #-- 1.1 --
            beforeCount = self.__wordBank.totalChoices()

            #-- 1.2 --
            # [ self.__wordBank  :=  self.__wordBank - (choices
            #       eliminated at slot intersections, if any) ]
            self.__reduceCycle()
            if VERBOSE:
                print self.show()

            #-- 1.3 --
            # [ if the total number of slot choices equals the
            #   number of slots ->
            #     return True
            #   else -> I ]
            totalChoices = self.__wordBank.totalChoices()
            print ( "=== Cyclic reduction: %d choices for %d slots" %
                    (totalChoices, self.nSlots()) )
            if totalChoices == self.nSlots():
                return True

            #-- 1.4 --
            if beforeCount <= totalChoices:
                return False
# - - -   P u z z l e . _ _ r e d u c e C y c l e

    def __reduceCycle ( self ):
        '''One cycle of cyclic reduction.

          [ self.__wordBank  :=  self.__wordBank - (choices
                eliminated at slot intersections, if any) ]
        '''
        #-- 1 --
        if VERBOSE: print "=== Reduction cycle"
        for cell in self.genCells():
            #-- 1 body --
            # [ if cell is related to two slots ->
            #       self.__wordBank  :=  self.__wordBank -
            #           (choices for those slots that have letters at
            #           cell's position not found in the intersecting
            #           slot)
            #   else -> I ]
            self.__reduceCell ( cell )
        #-- 2 --
        for slot in self.__slotMap.values():
            #-- 2 body --
            # [ if slot has only one choice ->
            #     remove that choice from all other slots
            #   else -> I ]
            self.__uniqueWordTest ( slot )
        #-- 3 --
        for word in self.__wordBank.genAllWords():
            #-- 3 body --
            # [ if word occurs in only one slot's choices ->
            #      self.__wordBank  :=  self.__wordBank - (choices
            #          for slot other than word) - (choices for
            #          that word in all slots)
            #   else -> I ]
            self.__uniqueSlotTest ( word )
# - - -   P u z z l e . _ _ r e d u c e C e l l

    def __reduceCell ( self, cell ):
        '''Eliminate any choices not common to two intersecting slots.

          [ cell is a Cell in self ->
              if cell is related to two slots ->
                  self.__wordBank  :=  self.__wordBank -
                      (choices for those slots that have letters at
                      cell's position not found in the intersecting
                      slot)
              else -> I ]
        '''
        if VERBOSE:
            print "=== Reduce cell %s" % cell.coord
        #-- 1 --
        # [ if two slots intersect at cell ->
        #     slotSet  :=  a list containing those two slots as
        #                  Slot instances
        #   else -> return ]
        slotSet = [ slot
                    for slot in cell.genSlots() ]
        if len(slotSet) < 2:
            return
        #-- 2 --
        #     letterSet  :=  a set of one-character strings representing
        #         possible choices at cell ]
        letterSet = self.__wordBank.cellChoices ( cell.coord )
        if len(letterSet) == 0:
            print "@@@ Empty choices at %s" % cell.coord
            self.showAllChoices()
            fatal("No choices during Puzzle-reduceSlot")
        if VERBOSE: print "=== Choices:", ''.join(list(letterSet))
        #-- 3 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for
        #       slots in slotSet whose characters at cell's position
        #       are not in letterSet ]
        for slot in slotSet:
            #-- 3 body --
            # [ self.__wordBank  :=  self.__wordBank - (choices for
            #       slot whose characters at cell's position
            #       are not in letterSet ]
            self.__reduceSlot ( cell, slot, letterSet )
# - - -   P u z z l e . _ _ r e d u c e S l o t

    def __reduceSlot ( self, cell, slot, letterSet ):
        '''Remove choices for a slot that don't have given letters.

          [ (cell is a Cell in self) and
            (slot is a Slot in self that contains cell) and
            (letterSet is a set of one-character strings) ->
              self.__wordBank  :=  self.__wordBank - (choices for
                  slots whose characters at cell's position
                  are not in letterSet ]
        '''
        #-- 1 --
        # [ wordList  :=  list of word choices in self.__wordBank
        #       for slot, as a list of Word instances
        #   cellx  :=  position of cell relative to slot ]
        wordList = [ word
                     for word in
                     self.__wordBank.genSlotChoices ( slot ) ]
        cellx = slot.findCoord ( cell.coord )
        #-- 2 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for slot
        #       that have letters in position cellx that are not in
        #       letterSet ]
        for word in wordList:
            #-- 2 body --
            # [ if word[cellx] is not in letterSet ->
            #     self.__wordBank  :=  self.__wordBank - (choice
            #         of word for slot)
            if word[cellx] not in letterSet:
                if VERBOSE:
                    print ( "*** Removing %s from %s because "
                        "word [%d] is not in %r." %
                        (word, slot, cellx, ''.join(list(letterSet))) )
                self.__wordBank.isNot ( slot, word )
# - - -   P u z z l e . _ _ u n i q u e W o r d T e s t

    def __uniqueWordTest ( self, slot ):
        '''Find slots with one choice, and remove that choice from others

          [ slot is a Slot in self ->
              if slot has only one choice ->
                remove that choice from all other slots
              else -> I ]
        '''
        #-- 1 --
        # [ slotChoiceList  :=  list of all current choices for slot ]
        slotChoiceList = [ word
            for word in self.__wordBank.genSlotChoices(slot) ]
        #-- 2 --
        if len(slotChoiceList) != 1:
            return
        else:
            word = slotChoiceList[0]

        #-- 3 --
        # [ otherSlotList  :=  list of slots that use word,
        #       minus slot ]
        otherSlotList = self.__wordBank.wordToSlots ( word )
        otherSlotList.remove ( slot )

        #-- 4 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for
        #      slots in otherSlotList that equal word ]
        for otherSlot in otherSlotList:
            if VERBOSE:
                print ( "*** Removing %s from %s because it goes in "
                    "%s." % (word, otherSlot, slot) )
            self.__wordBank.isNot ( otherSlot, word )
# - - -   P u z z l e . _ _ u n i q u e S l o t T e s t

    def __uniqueSlotTest ( self, word ):
        '''Find cases where only one slot can be a given word.

          [ word is a Word in self.__wordBank ->
              if word occurs in only one slot's choices ->
                 self.__wordBank  :=  self.__wordBank - (choices
                     for slot other than word) - (choices for
                     that word in all slots)
              else -> I ]
        '''
        #-- 1 --
        # [ slotList  :=  list of all slots for which word is
        #       currently a choice ]
        slotList = self.__wordBank.wordToSlots ( word )

        #-- 2 --
        if len(slotList) != 1:
            return
        else:
            slot = slotList[0]
        #-- 3 --
        # [ otherWordList  :=  choices for slot from self.__wordBank ]
        otherWordList = [ word
            for otherWord in self.__wordBank.genSlotChoices ( slot ) ]

        #-- 4 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for slot
        #       in otherWordList that do not equal word) ]
        for otherWord in otherWordList:
            if otherWord != word:
                self.__wordBank.isNot ( slot, otherWord )
        #-- 5 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for
        #       slots other than (slot) that equal (word) ]
        for otherSlot in self.__slotMap.values():
            if otherSlot is not slot:
                self.__wordBank.isNot ( otherSlot, word )
# - - -   P u z z l e . _ _ r e c u r S o l v e r

    def __recurSolver ( self, slot ):
        '''Recursively solve the puzzle, starting at slot.

          [ slot is a Slot in self ->
              generate solutions to self starting with self's
              current state ]
        '''
        #-- 1 --
        # [ choiceList  :=  choices for slot in self.__wordBank,
        #       sorted
        #   nextSlot  :=  successor to slot in self, or None if
        #       slot is the last in self ]
        choiceList = [ choice
                       for choice in
                       self.__wordBank.genSlotChoices ( slot ) ]
        choiceList.sort()
        nextSlot = self.__slotSuccessor[slot]

        #-- 2 --
        # [ if nextSlot is None ->
        #       if len(choiceList) == 1 ->
        #           yield self
        #           raiseStopIteration
        #       else ->
        #           sys.stderr  +:=  error message
        #           stop execution
        #   else if len(choiceList) is 0 ->
        #       raise StopIteration
        #   else -> I ]
        if nextSlot is None:
            if len(choiceList) == 1:
                yield self
            raise StopIteration
        elif len(choiceList) == 0:
            raise StopIteration
        #-- 3 --
        # [ self.__wordBank  :=  self.__wordBank - (choices for slot
        #       from choiceList ]
        for choice in choiceList:
            self.__wordBank.isNot ( slot, choice )
        #-- 4 --
        # [ generate solutions for slot containing each choice
        #   from choiceList that fits the current choices in
        #   self.__wordBank, starting with nextSlot ]
        for choice in choiceList:
            #-- 4 body --
            # [ if choice in slot fits the rest of the puzzle
            #   according to self.__wordBank ->
            #     generate solutions to self assuming slot==choice
            #   else -> I ]
            if self.__choiceFits ( slot, choice ):
                #-- 4.1 --
                # [generate solutions to self assuming slot==choice ]
                for solution in self.__assumeChoice ( slot,
                    choice, nextSlot ):
                    yield solution
        #-- 5 --
        # [ self.__wordBank  :=  self.__wordBank + (choices for slot
        #       from choiceList ]
        for choice in choiceList:
            self.__wordBank.mayBe ( slot, choice )

        #-- 6 --
        raise StopIteration
# - - -   P u z z l e . _ _ c h o i c e F i t s

    def __choiceFits ( self, thisSlot, choice ):
        '''Does choice in thisSlot work with its context?

          [ (thisSlot is a slot in self) and
            (choice is a Word that has the same length as thisSlot) ->
              if choice in thisSlot fits the rest of the puzzle
              according to self.__wordBank ->
                return True
              else -> return False ]
        '''
        #-- 1 --
        # [ coordList  :=  list of thisSlot's coordinates in order ]
        coordList = [ coord
                      for coord in thisSlot.genCoords() ]
        #-- 2 --
        # [ if (any Coord in coordList is the intersection of two
        #   slots) and (no choices of the crossing slot match the
        #   corresponding letter of (choice) ->
        #     return False
        #   else -> I ]
        for charx, coord in enumerate(coordList):
            #-- 2 body --
            # [ if (coord is the intersection of two slots in self)
            #   and (no choices for the slot crossing thisSlot have
            #   choice[charx] in coord's position) ->
            #     return False
            #   else -> I ]
            if self.__crossingClash ( coord, thisSlot, choice[charx] ):
                return False

        #-- 3 --
        return True
# - - -   P u z z l e . _ _ c r o s s i n g C l a s h

    def __crossingClash ( self, coord, thisSlot, char ):
        '''Do the choices for a slot crossing thisSlot clash with char?

          [ (coord is a Coord in self) and
            (thisSlot is a slot in self containing coord) and
            (char is a one-character string, uppercased) ->
              if (coord is the intersection of two slots in self)
              and (no choices for the slot crossing thisSlot have
              choice[charx] in coord's position) ->
                return True
              else -> return False ]
        '''
        #-- 1 --
        # [ slotList  :=  list of slots intersecting coord other
        #       than thisSlot ]
        slotList = [ slot
                     for slot in self.whatSlots ( coord )
                     if slot is not thisSlot ]

        #-- 2 --
        if len(slotList) == 0:
            return False
        else:
            otherSlot = slotList[0]
        #-- 3 --
        # [ otherCharx  :=  index in otherSlot of coord ]
        otherCharx = otherSlot.findCoord ( coord )

        #-- 4 --
        # [ if any choice for otherSlot in self.__wordBank has a
        #   character in position [otherCharx] that matches char ->
        #     return False
        #   else -> I ]
        for otherChoice in self.__wordBank.genSlotChoices ( otherSlot ):
            if otherChoice[otherCharx] == char:
                return False
        #-- 5 --
        return True
# - - -   P u z z l e . _ _ a s s u m e C h o i c e

    def __assumeChoice ( self, thisSlot, choice, nextSlot ):
        '''Generate solutions assuming thisSlot==choice

          [ (thisSlot is a slot in self) and
            (nextSlot is the successor of thisSlot) and
            (choice is a Word that is NOT a choice for thisSlot in
            self.__wordBank) and
            (all slots preceding thisSlot have a single choice) ->
              generate solutions to self assuming thisSlot==choice ]
        '''
        #-- 1 --
        # [ otherSlotList  :=  slots in self for which self.__wordBank
        #       shows (choice) as one of their choices ]
        otherSlotList = self.__wordBank.wordToSlots ( choice )

        #-- 2 --
        # [ self.__wordBank  :=  self.__wordBank + (choice (choice)
        #       for thisSlot) - (choice (choice) for all slots in
        #       otherSlotList ]
        self.__wordBank.mayBe ( thisSlot, choice )
        for otherSlot in otherSlotList:
            self.__wordBank.isNot ( otherSlot, choice )

        #-- 3 --
        # [ generate solutions assuming slots preceding nextSlot
        #   are unchanged ]
        for solution in self.__recurSolver ( nextSlot ):
            yield solution

        #-- 4 --
        # [ self.__wordBank  :=  self.__wordBank - (choice (choice)
        #       for thisSlot) + (choice (choice) for all slots in
        #       otherSlotList ]
        for otherSlot in otherSlotList:
            self.__wordBank.mayBe ( otherSlot, choice )
        self.__wordBank.isNot ( thisSlot, choice )

# - - - - -   c l a s s   C e l l

class Cell(object):
    '''Represents one character position of the puzzle.

      Exports:
        Cell ( coord, text ):
          [ (coord is a cell location as a Coord instance) and
            (text is a clue character, or UNK_CELL if the content
            of this cell is not initially known) ->
              return a new Cell instance with that location and
              text, and no associated slots ]
        .coord:      [ as passed to constructor, read-only ]
        .text:       [ as passed to constructor, read-only, uppercased ]
        .addSlot ( slot ):
          [ slot is a Slot instance that intersects self ->
              self  :=  self with slot added to its list of
                  associated slots ]
        .genSlots():
          [ generate the slots associated with self as a sequence
            of Slot instances, if any ]

      State/Invariants:
        .__slotList:
          [ a list of the Slot instances that intersect self,
            if any ]
    '''
# - - -   C e l l . _ _ i n i t _ _

    def __init__ ( self, coord, text ):
        '''Constructor
        '''
        self.coord = coord
        self.text = text.upper()
        self.__slotList = []
# - - -   C e l l . a d d S l o t

    def addSlot ( self, slot ):
        '''Add an intersecting slot to self.
        '''
        self.__slotList.append ( slot )
# - - -   C e l l . g e n S l o t s

    def genSlots ( self ):
        '''Generate all the slots intersecting self.
        '''
        return iter ( self.__slotList )


# - - - - -   c l a s s   S l o t

class Slot(object):
    '''Represents one location for a word in the puzzle.

      Exports:
        Slot ( origin, length, isV ):
          [ (origin is the location of the first cell of the slot
            as a Coord instance) and
            (length is the length as a positive int) and
            (isV is 0 for horizontal, 1 for vertical) ->
              return a new Slot instance representing these values ]
        .origin:  [ as passed to constructor, read-only ]
        .length:  [ as passed to constructor, read-only ]
        .isV:     [ as passed to constructor, read-only ]
        .__str__(self): [ return a string repr. of self ]
        .__len__(self): [ returns self.length ]
        .__getitem__(self, k):
          [ return the location of the (k)th character of self
            as a Coord instance ]
        .__cmp__(self, other):
          [ usual comparison function, with self.origin as
            the primary key and self.isV the secondary key ]
        .genCoords():
          [ generate the coordinates of cells in self in
            ascending order by index, as Coord instances ]
        .findCoord ( coord ):
          [ if coord is within self ->
              return the position of that coord relative to self's
              origin
            else -> raise IndexError ]
    '''
# - - -   S l o t . _ _ i n i t _ _

    def __init__ ( self, origin, length, isV ):
        '''Constructor
        '''
        self.origin = origin
        self.length = length
        self.isV = isV
# - - -   S l o t . _ _ s t r _ _

    def __str__ (self):
        '''Return self as a string
        '''
        return ( "%s%d%s" %
                 (showIsV(self.isV), self.length, self.origin) )
# - - -   S l o t . _ _ l e n _ _

    def __len__ ( self ):
        '''Return the length of the slot.
        '''
        return self.length
# - - -   S l o t . _ _ g e t i t e m _ _

    def __getitem__ ( self, k ):
        '''Return the coord of the [k]th character of this slot.
        '''
        #-- 1 --
        # [ if self.isV is 0 ->
        #     return Coord ( self.origin[0]+k, self.origin[1] )
        #   else if self.isV is 1 ->
        #     return Coord ( self.origin[0], self.origin[1]+k ) ]
        return Coord ( self.origin[0] + k*self.isV,
                       self.origin[1] + k*perpendicular(self.isV) )
# - - -   S l o t . _ _ c m p _ _

    def __cmp__ ( self, other ):
        '''Compare two slots by position.
        '''
        return cmp ( (self.origin, self.isV),
                     (other.origin, other.isV) )
# - - -   S l o t . g e n C o o r d s

    def genCoords ( self ):
        '''Generate the coordinates in self.
        '''
        #-- 1 --
        if self.isV:    # Vertical case, step through rows
            for rowx in range(self.origin[0],
                              self.origin[0]+self.length):
                yield Coord(rowx, self.origin[1])
        else:           # Horizontal case, step through columns
            for colx in range(self.origin[1],
                              self.origin[1]+self.length):
                yield Coord(self.origin[0], colx)
# - - -   S l o t . f i n d C o o r d

    def findCoord ( self, coord ):
        '''What position in this slot corresponds to a given coord?
        '''
        #-- 1 --
        # [ offset  :=  distance coord is to the right of and
        #       below self.origin, as a Coord instance ]
        offset = coord - self.origin

        #-- 2 --
        if (offset[0] < 0) or (offset[1] < 0):
            raise IndexError
        #-- 3 --
        # [ if self.isV ->
        #     rowLimit  :=  0
        #     colLimit  :=  self.length
        #   else ->
        #     rowLimit  :=  self.length
        #     colLimit  :=  0 ]
        rowLimit, colLimit = 1, self.length
        if self.isV:
            rowLimit, colLimit = colLimit, rowLimit

        #-- 4 --
        if ( (offset[0] >= rowLimit) or
             (offset[1] >= colLimit) ):
            raise IndexError
        #-- 5 --
        # [ if self.isV ->
        #     return offset[1]
        #   else ->
        #     return offset[0] ]
        return offset[perpendicular(self.isV)]

# - - - - -   c l a s s   W o r d B a n k

class WordBank(object):
    '''Represents the word list and the state of the solution.

      Exports:
        WordBank(puzzle):
          [ puzzle is a Puzzle instance ->
              return a new, empty WordBank instance that uses
              puzzle's geometry ]
        .maxLen:
          [ if self is empty -> 0
            else -> maximum word length in self ]
        .addWord ( word ):
          [ word is a nonempty string ->
              if word is not in self ->
                self  :=  self with word added
              else -> raise SyntaxError ]
        .__len__(self):  [ return number of words in self ]
        .wordsOfLen ( n ):
          [ n is an int ->
              return the number of words in self of length n ]
        .genAllWords():
          [ generate all words in self, regardless of length ]
        .genCandidates ( n ):
          [ n is an int > 2 ->
              generate all the available words of length n
              as Word instances ]
        .mayBe ( slot, word ):
          [ (slot is a Slot instance) and (word is a Word instance) ->
              add word to the set of available choices for slot ]
        .isNot ( slot, word ):
          [ remove word from the set of available choices for slot ]
        .totalChoices():
          [ return the sum of the count of choices for all
            slots in self ]
        .genSlotChoices ( slot ):
          [ slot is a Slot instance in self ->
              generate the current set of choices for slot
              as a sequence of Word instances ]
        .slotCharChoices ( slot, coord ):
          [ (slot is a Slot instance in self) and
            (coord is the location of a cell in slot as a Coord) ->
              return a set of the characters that are choices at
              that position ]
        .cellChoices ( coord ):
          [ coord is a Coord instance ->
              if there is no cell at coord ->
                return ' '
              else ->
                return a set of all the characters that are
                possible choices at coord ]
        .wordToSlots ( word ):
          [ word is a Word in self ->
              return a new list of the slots for which this word
              is currently a choice, as Word instances ]
      State/Invariants:
        .__nWords:  [ number of words in self ]
        .__totalChoices:
          [ the sum of the number of choices available to
            each slot in self ]
        .__lenMap:
          [ a dictionary whose keys are the unique lengths of
            words in self, and each associated value is a
            list of words of that length as Word instances,
            sorted in ascending order by (length, text) ]
        .__choiceMap:
           [ a dictionary whose keys are Slot instances, and
             each corresponding value is a set of the words
             that may fill that slot, as a Word instance ]
         .__wordToSlots:
           [ a dictionary whose keys are the Word instances in
             self, and each related value is a set of the
             Slot instances that have that word as a choice ]
    '''
# - - -   W o r d B a n k . _ _ i n i t _ _

    def __init__ ( self, puzzle ):
        '''Constructor
        '''
        self.puzzle = puzzle
        self.maxLen = 0
        self.__nWords = 0
        self.__totalChoices = 0
        self.__lenMap = defaultdict(set)
        self.__choiceMap = defaultdict(set)
        self.__wordToSlots = defaultdict(set)
# - - -   W o r d B a n k . a d d W o r d

    def addWord ( self, rawWord ):
        '''Add a word to the bank.
        '''
        #-- 1 --
        # [ word  :=  a Word instance made from rawWord ]
        word = Word ( rawWord )

        #-- 2 --
        # [ self.maxLen  :=  max ( self.maxLen, len(word) )
        #   self.__nWords  +:=  1
        #   self.__lenMap[len(word)]  +:=  word ]
        self.maxLen = max ( self.maxLen, len(word) )
        self.__nWords += 1
        if word in self.__lenMap[len(word)]:
            raise SyntaxError ( "Duplicate word '%s'." % word )
        self.__lenMap[len(word)].add ( word )
# - - -   W o r d B a n k . _ _ l e n _ _

    def __len__ ( self ):
        '''Return the number of words of all lengths.
        '''
        return self.__nWords
# - - -   W o r d B a n k . w o r d s O f L e n

    def wordsOfLen ( self, n ):
        '''How many words have length n?
        '''
        return len(self.__lenMap[n])
# - - -   W o r d B a n k . g e n A l l W o r d s

    def genAllWords ( self ):
        '''Generate all the words in self.
        '''
        #-- 1 --
        for word in self.__wordToSlots.keys():
            yield word

        #-- 2 --
        raise StopIteration
# - - -   W o r d B a n k . g e n C a n d i d a t e s

    def genCandidates ( self, n ):
        '''Generate all words of length n.
        '''
        #-- 1 --
        # [ wordList  :=  the words from self.__lenMap[n] as a
        #                 list of Word instances ]
        wordList = list ( self.__lenMap[n] )
        #-- 2 --
        # [ wordList  :=  wordList sorted into ascending order ]
        wordList.sort()

        #-- 3 --
        for word in wordList:
            yield word

        #-- 4 --
        raise StopIteration
# - - -   W o r d B a n k . m a y B e

    def mayBe ( self, slot, word ):
        '''Add word as one choice for slot.
        '''
        #-- 1 --
        # [ if self.__choiceMap has an entry for (slot) ->
        #     self.__choiceMap  +:=  word
        #   else ->
        #     self.__choiceMap  :=  a new set containing word ]
        if VERBOSE: print "=== Slot %s may be %s" % (slot,word)
        self.__choiceMap[slot].add ( word )
        self.__wordToSlots[word].add ( slot )

        #-- 2 --
        self.__totalChoices += 1
# - - -   W o r d B a n k . i s N o t

    def isNot ( self, slot, word ):
        '''Remove word from the set of choices for slot.
        '''
        #-- 1 --
        # [ choiceSet  :=  the set of choices for slot ]
        choiceSet = self.__choiceMap[slot]

        #-- 2 --
        if word not in choiceSet:
            return
        else:
            self.__totalChoices -= 1

        #-- 3 --
        # [ self.__choiceMap  :=  self.__choiceMap with choice
        #       word removed from the set for key (slot)
        #   self.__wordToSlots  :=  self.__wordToSlots with
        #       slot removed from the set for key (word) ]
        self.__choiceMap[slot].remove ( word )
        self.__wordToSlots[word].remove ( slot )
        if VERBOSE: print "=== Slot %s is not %s" % (slot,word)
# - - -   W o r d B a n k . t o t a l C h o i c e s

    def totalChoices ( self ):
        '''Returns the sum of the counts of all choices for all slots.
        '''
        return self.__totalChoices
# - - -   W o r d B a n k . g e n S l o t C h o i c e s

    def genSlotChoices ( self, slot ):
        '''Generate the words that are still choices for a given slot.
        '''
        #-- 1 --
        return iter ( self.__choiceMap[slot] )
# - - -   W o r d B a n k . s l o t C h a r C h o i c e s

    def slotCharChoices ( self, slot, coord ):
        '''Return the set of characters for slot's choices at coord.
        '''
        #-- 1 --
        # [ if coord is in slot ->
        #     k  :=  index within slot of coord
        #   else -> raise IndexError ]
        k = slot.findCoord ( coord )
        #-- 2 --
        # [ return the union of the sets of all characters that occur
        #   in position k of words that are choices for slot ]
        wordList = [ set(word[k])
              for word in self.genSlotChoices ( slot ) ]
        if len(wordList):
            return reduce ( set.__or__, wordList )
        else:
            return set()
# - - -   W o r d B a n k . c e l l C h o i c e s

    def cellChoices ( self, coord ):
        '''What characters are possible choices at a given location?
        '''
        #-- 1 --
        # [ if there is a cell at coord in self.puzzle ->
        #     cell  :=  the Cell instance at coord
        #   else -> return a space character ]
        cell = self.puzzle.whatCell ( coord )
        if cell is None:
            return ' '
        #-- 2 --
        if self.__totalChoices == 0:
            return cell.text
        #-- 3 --
        return reduce ( set.__and__,
            [ self.slotCharChoices ( slot, coord )
              for slot in cell.genSlots() ] )
# - - -   W o r d B a n k . w o r d T o S l o t s

    def wordToSlots ( self, word ):
        '''Return a list of the slots that have this word as a choice
        '''
        #-- 1 --
        # [ if word is a key in self.__wordToSlots ->
        #     return a copy of the related list
        #   else -> raise KeyError ]
        return list(self.__wordToSlots[word])

# - - - - -   c l a s s   W o r d

class Word(str):
    '''Represents a unique word in the word list.

      Exports:
        Word ( text ):
          [ text is a nonempty string containing no spaces or
            occurrences of UNK_CELL ->
              return a new Word instance representing text,
              uppercased
            else -> raise ValueError ]
    '''
    def __new__ ( cls, text ):
        '''Constructor for Word
        '''
        if UNK_CELL in text:
            raise ValueError ( "Word '%s': character '%s' is not "
                "allowed in the word list." % (text, UNK_CELL ) )
        if ' ' in text:
            raise ValueError ( "Word '%s': blanks are not allowed "
                "in the word list." % text )
        return str.__new__(cls, text.upper() )

# - - - - -   c l a s s   C o o r d

class Coord(object):
    '''Represents one location in the puzzle grid.

      Exports:
        Coord ( row, column ):
          [ (row is a nonnegative row number) and
            (column is a nonnegative column number) ->
              return a new Coord representing the intersection of
              row (row) and column (column) ]
        .rc:
          [ a two-tuple (self[0], self[1]); read-only ]
        .__cmp__(self, other):
          [ define an ordering with row number as the primary key
            and column number as the secondary key ]
        .__getitem__(self, isCol):
          [ isCol is 0 ->
              return self's row
            isCol is 1 ->
              return self's column ]
        .__setitem__(self, isCol, value):
          [ isCol is 0 ->
              self[0] := value
            isCol is 1 ->
              self[1] := value ]
        .__add__(self, other):
          [ return a new Coord with row (self[0]+other[0]) and
            column (self[1]+other[1]) ]
        .__sub__(self, other):
          [ return a new Coord with row (self[0]-other[0]) and
            column (self[1]-other[1]) ]
        .__str__(self): [ return a textual representation of self ]
    '''
    def __init__ ( self, row, col ):
        self.rc = [row, col]

    def __cmp__ ( self, other ):
        return cmp ( self.rc, other.rc )

    def __getitem__(self, isCol):
        return self.rc[isCol]

    def __setitem__(self, isCol, value):
        self.rc[isCol] = value

    def __add__ ( self, other ):
        return Coord ( self[0]+other[0], self[1]+other[1] )

    def __sub__ ( self, other ):
        return Coord ( self[0]-other[0], self[1]-other[1] )

    def __str__ ( self ):
        return "(%d,%d)" % (self[0], self[1])
#================================================================
# Epilogue
#----------------------------------------------------------------

if __name__ == '__main__':
    main()