kkck: A solver for Kriss Kross puzzles

Each instance of this class represents one unique word in the word list.

There is not much to this class, and except for one detail, we could actually use regular Python str instances: they support the len() function, and they sort in alphabetical order. The sole functional objection is that they are case-sensitive.

By convention, letters in a Kriss Kross are all treated as uppercase. This solves two problems. First, the solution is displayed with uppercase letters even if the input file presented the words in lowercase. More subtly, suppose the person preparing the input file spelled the word COD with uppercase letters, and spelled dog with lowercase, and the solution requires that those two words interesect at the letter D. If d and D are considered separate characters, the solution algorithm will not allow those two words to intersect there.

So that we don't have to define all the special methods like __cmp__() and __getitem__(), our Word class can inherit from the built-in str class. To give the class our special rules, we must override the .__new__() method, not the usual .__init__() method. Notes on this process can be found in Guido van Rossum's Unifying types and classes in Python 2.2, in the section “Overriding the __new__ method.”

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