pal2.py

import random, re, bisect, time

"""Produce Panama-ish Palindromes. Copyright (C) 2002-2008, Peter Norvig."""

################ Checking for Palindromes

def is_panama(s):
    "Test if string s is a Panama-ish palindrome."
    return is_palindrome(s) and is_unique(phrases(s))

def is_palindrome(s):
    "Test if a string is a palindrome."
    s1 = canonical(s)
    return s1 == reversestr(s1)

def phrases(s):
    "Break a string s into comma-separated phrases."
    return [phrase.strip() for phrase in s.split(',')]

def canonical(word, sub=re.compile('''[-* \t\n\r.,;!?:()`"']''').sub):
    "The canonical form for comparing: lowercase, no blanks or punctuation."
    return sub('', word).lower()

################ Utilities

def reversestr(x):
    "Reverse a string."
    return x[::-1]

def is_unique(seq):
    "Return true if seq has no duplicate elements."
    return len(seq) == len(set(seq))

def update(obj, **entries):
    "Change attributes of obj, according to the keyword args."
    obj.__dict__.update(entries)
    return obj

################ Reading in a dictionary

class PalDict:
    """A dictionary from which you can find canonical words that start or end
    with a given canonical substring, and find the true name of a
    canonical word with d.truename[canonicalword]."""
    
    def __init__(self, k=1000, filename='npdict.txt'):
        words, rwords, truename = [], [], {'': '', 'panama': 'Panama!'}
        for tword in open(filename).read().splitlines():
            word = canonical(tword)
            words.append(word)
            rwords.append(reversestr(word))
            truename[word] = tword
        words.sort()
        rwords.sort()
        update(self, k=k, words=words, rwords=rwords, truename=truename,
               reversibles={}, rangek=range(k), tryharder=False)

    def startswith(self, prefix):
        """Return up to k canonical words that start with prefix.
        If there are more than k, choose from them at random."""
        return self._k_startingwith(self.words, prefix)

    def endswith(self, rsuffix):
        """Return up to k canonical words that end with the reversed suffix.
        If you want words ending in 'ing', ask for d.endswith('gni').
        If there are more than k, choose from them at random."""
        return map(reversestr, self._k_startingwith(self.rwords, rsuffix))

    def __contains__(self, word):
        return word in self.truename

    def reversible_words(self):
        "Find words that have a reverse in the dict, like {'Camus': 'Sumac'}"
        if not self.reversibles:
            reversibles = self.reversibles
            for rw in self.rwords:
                if rw in self:
                    w = reversestr(rw)
                    if w != rw and w not in reversibles:
                        reversibles[w] = rw
            self.reversibles = reversibles
        return self.reversibles

    def _k_startingwith(self, words, prefix):
        start = bisect.bisect_left(words, prefix)
        end = bisect.bisect(words, prefix + 'zzzz')
        n = end - start
        if self.k >= n: # get all the words that start with prefix
            results = words[start:end]
        else: # sample from words starting with prefix 
            indexes = random.sample(xrange(start, end), self.k)
            results = [words[i] for i in indexes]
        random.shuffle(results)
        ## Consider words that are prefixes of the prefix.
        ## This is very slow, so don't use it until late in the game.
        if self.tryharder:
            for i in range(3, len(prefix)):
                w = prefix[0:i]
                if ((words == self.words and w in self.truename) or
                    (words == self.rwords and reversestr(w) in self.truename)):
                    results.append(w)
        return results

paldict = PalDict() 

def anpdictshort():
    "Find the words that are valid when every phrase must start with 'a'"
    def segment(word):  return [s for s in word.split('a') if s]
    def valid(word): return all(reversestr(s) in segments for s in segment(word))
    words = map(canonical, file('anpdict.txt'))
    segments = set(s for w in words for s in segment(canonical(w)))
    valid_words = [paldict.truename[w] for w in words if valid(w)]
    file('anpdict-short.txt', 'w').write('\n'.join(valid_words))

################ Search for a palindrome

class Panama:
    def __init__(self, L='A man, a plan', R='a canal, Panama', dict=paldict):
        ## .left and .right hold lists of canonical words
        ## .diff holds the number of characters that are not matched,
        ##  positive for words on left, negative for right.
        ## .stack holds (action, side, arg) tuples
        update(self, left=[], right=[], best=0, seen={}, diff=0, stack=[],
               used_reversibles=False, starttime=time.clock(), dict=dict)
        for word in L.split(','):
            self.add('left', canonical(word))
        for rword in reversestr(R).split(','):
            self.add('right', canonical(reversestr(rword)))
        self.consider_candidates()
        
    def search(self, steps=50000000):
        "Search for palindromes."
        for _ in xrange(steps):
            if not self.stack:
                return 'done'
            action, dir, substr, arg = self.stack[-1]
            if action == 'added': # undo the last word added
                self.remove(dir, arg)
            elif action == 'trying' and arg: # try the next word if there is one
                self.add(dir, arg.pop()) and self.consider_candidates()
            elif action == 'trying' and not arg: # otherwise backtrack
                self.stack.pop()
            else:
                raise ValueError(action)

    def add(self, dir, word):
        "add a word"
        if word in self.seen:
            return False
        else:
            getattr(self, dir).append(word)
            self.diff += factor[dir] * len(word)
            self.seen[word] = True
            self.stack.append(('added', dir, '?', word))
            return True

    def remove(self, dir, word):
        "remove a word"
        oldword = getattr(self, dir).pop()
        assert word == oldword
        self.diff -= factor[dir] * len(word)
        del self.seen[word]
        self.stack.pop()
        
    def consider_candidates(self):
        """Push a new state with a set of candidate words onto stack."""
        if self.diff > 0: # Left is longer, consider adding on right
            dir = 'right'
            substr =  self.left[-1][-self.diff:]
            candidates = self.dict.endswith(substr)
        elif self.diff < 0: # Right is longer, consider adding on left
            dir = 'left'
            substr =  reversestr(self.right[-1][0:-self.diff])
            candidates = self.dict.startswith(substr)
        else: # Both sides are same size
            dir = 'left'
            if not self.used_reversibles:
                self.report()
                self.add_reversibles()
            substr = ''
            candidates = self.dict.startswith('')
        if substr == reversestr(substr):
            self.report()
        self.stack.append(('trying', dir, substr, candidates))

    def add_reversibles(self):
        "Add in reversible words."
        print 'using reversibles ...'
        for (word, rword) in self.dict.reversible_words().items():
            if word not in self.seen and rword not in self.seen:
                self.add('left', word)
                self.add('right', rword)
        self.used_reversibles = True
        self.stack = []
        print '...done'
                
    def report(self):
        "Report a new palindrome to log file (if it is sufficiently big)."
        N = len(self)
        if N > 13333:
            self.dict.tryharder = True
        if N > self.best and (N > 12500 or N > self.best+500):
            self.best = len(self)
            self.bestphrase = str(self)
            print '%5d phrases (%5d words) in %3d seconds' % (
                self.best, self.bestphrase.count(' ')+1, time.clock() - self.starttime)
            assert is_panama(self.bestphrase)
            f = open('pallog%d.txt' % (id(self) % 10000), 'w')
            f.write(self.bestphrase + '\n')
            f.close()

    def __len__(self):
        return len(self.left) + len(self.right)

    def __str__(self):
        truename = self.dict.truename
        lefts = [truename[w] for w in self.left]
        rights =[truename[w] for w in self.right]
        return ', '.join(lefts + rights[::-1])

factor = {'left': +1, 'right': -1}

# Note that we only allow one truename per canonical name.  Occasionally
# this means we miss a good word (as in "a node" vs. "an ode"), but there
# are only 665 of these truename collisions, and most of them are of the
# form "a mark-up" vs. "a markup" so it seemed better to disallow them.

################ Unit Tests
 
def tests(p=Panama()):
    assert is_panama('A man, a plan, a canal, Panama.')
    assert is_panama('''A (man),     a   plan,,;, a ```canal?'' -- Panama!''')
    assert not is_panama('A man, a plan, a radar, a canal, Panama.')
    assert is_palindrome('A man, a plan, a canal, Panama.')
    assert is_palindrome('radar, radar? radar!')
    assert not is_palindrome('radars')
    assert phrases('A man, a plan, Panama') == ['A man', 'a plan', 'Panama']
    assert canonical('A man, a plan, a canal, Panama') == 'amanaplanacanalpanama'
    assert reversestr('foo') == 'oof'
    assert is_unique([1, 2, 3])
    assert not is_unique([1, 2, 2])
    d = p.dict
    def sameset(a, b): return set(a) == set(b)
    assert 'panama' in d
    assert d.words[0] in d
    assert d.words[-1] in d
    assert sameset(d.startswith('aword'), ['awording', 'awordbreak',
        'awordiness', 'awordage', 'awordplay', 'awordlore', 'awordbook',
        'awordlessness', 'aword', 'awordsmith'])
    assert sameset(d.endswith('ytisob'), ['aglobosity', 'averbosity',
        'asubglobosity', 'anonverbosity', 'agibbosity'])
    d.tryharder = True
    assert sameset(d.startswith('oklahoma'), ['oklahoma', 'okla'])
    d.tryharder = False
    assert d.startswith('oklahoma') == ['oklahoma']
    assert d.startswith('fsfdsfdsfds') == []
    print 'all tests pass'

if __name__ == '__main__': 
    p = Panama();
    tests(p)
    p.search()