>From something on lambda.weblogs.com. #!/usr/bin/python """Compute the longest "add-a-gram" from a word list.
The problem is from http://www.itasoftware.com/careers/programmers.php Add-A-Gram An "add-a-gram" is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the words "CREDENTIALS" and "ANACHRONISM": ail + s = mar + c = sail + n = cram + h = nails + e = march + s = aliens + t = charms + o = salient + r = chromas + n = entrails + c = monarchs + i = clarinets + e = harmonics + a = interlaces + d = maraschino + n = CREDENTIALS ANACHRONISM (length 11) (length 11) Test your own credentials: given the dictionary found here [http://www.itasoftware.com/careers/WORD.LST] (1.66MB), what is the longest add-a-gram? So this is a Python solution; on the 157077-word wordlist they give, it runs on my laptop in 2 minutes, 22 seconds, and finds a length-16 "add-a-gram" for "indeterminations", starting with "ami". """ import string, sys def sig(ss): """Produce a signature of the string ss. Anagrams, and only anagrams, have the same signature. """ ll = list(str(ss)) ll.sort() # we used to intern here, but destructors at program exit time were # taking way too much time, so it was a net loss return string.join(ll, '') sigdict, ansdict = {}, {} def longest_addagram(startword): """Memoized recursive tree search; dynamic programming backwards. Returns the longest add-a-gram starting from startword, which can be of any length and is intended to be a word or an anagram of a word, in the form of a string of letters to add to startword --- or None if startword isn't a word (or anagram of a word). Might be faster if I removed recursion from it... """ startword = sig(startword) if not sigdict.has_key(startword): return None if ansdict.has_key(startword): return ansdict[startword] # At this point, we know we have at least a zero-length addagram starting # at this word, because the word is in sigdict. best = '' for letter in string.lowercase: addagram = longest_addagram(startword + letter) if addagram is not None and len(addagram) >= len(best): best = letter + addagram ansdict[startword] = best return best def display_addagram(start, addagram): """Display an add-a-gram in the format given on the web page.""" s = sig(start) for char in addagram: print "%s + %s =" % (sigdict[s], char) s = sig(s + char) print string.upper(sigdict[s]) print "(length %d)" % len(s) def main(dictfilename): startwords = [] words = open(dictfilename) # test data: #for word in ['ail', 'sail', 'nails', 'aliens', 'salient', 'entrails', # 'clarinets', 'interlaces', 'credentials']: for word in words.xreadlines(): if word[-1:] == "\n": word = word[:-1] sigdict[sig(string.lower(word))] = word if len(word) == 3: startwords.append(string.lower(word)) words.close() # for testing: # display_addagram('ail', 'snetrced') bestword = bestaddagram = None ii = 0 for word in startwords: addagram = longest_addagram(word) if (addagram is not None and (bestword is None or len(addagram) > len(bestaddagram))): bestword, bestaddagram = word, addagram # for testing: # display_addagram(word, addagram) ii = ii + 1 sys.stdout.write("\r%d / %d (%d)" % (ii, len(startwords), len(sigdict))) sys.stdout.flush() print # for testing: # x = longest_addagram('ali') display_addagram(bestword, bestaddagram) if __name__ == '__main__': main(sys.argv[1])
