kkck: A solver for Kriss Kross puzzles

For a discussion of the design of this class, see Section 4.7, “The WordBank class”.

# - - - - -   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 ]

There are several internal data structures. The .__nWords attribute tracks the number of words in the word list. The .__totalChoices invariant tracks the sum of the numbers of choices for each slot. The .__lenMap dictionary holds all the words, segregated by length.

      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) ]

The .__choiceMap attribute tracks which words are still considered possible choices for each slot. The .__wordToSlots attribute tracks the inverse of that relation: which slots have a given word as a choice.

        .__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 ]
    '''