StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Assuming you need to do this repeatedly (or you want the answer for every one of the 26 letters), do it backwards:</p> <ol> <li>Load a dictionary, and sort it by length, descending</li> <li>Establish a mapping, initially empty, between words and (extension, max_len) tuples.</li> <li>For each word in the sorted list: <ol> <li>If it's already in the mapping, retrieve the max len.</li> <li>If it's not, set the max len to the word length.</li> <li>Examine each word produced by deleting a character. If that word is not in the mapping, or our max_len exceeds the max_len of the word already in the mapping, update the mapping with the current word and max_len</li> </ol></li> </ol> <p>Then, to get the chain for a given prefix, simply start with that prefix and repeatedly look it and its extensions up in the dictionary.</p> <p>Here's the sample Python code:</p> <pre><code>words = [x.strip().lower() for x in open('/usr/share/dict/words')] words.sort(key=lambda x:len(x), reverse=True) word_map = {} # Maps words to (extension, max_len) tuples for word in words: if word in word_map: max_len = word_map[word][1] else: max_len = len(word) for i in range(len(word)): new_word = word[:i] + word[i+1:] if new_word not in word_map or word_map[new_word][2] < max_len: word_map[new_word] = (word, max_len) # Get a chain for each letter for term in "abcdefghijklmnopqrstuvwxyz": chain = [term] while term in word_map: term = word_map[term][0] chain.append(term) print chain </code></pre> <p>And its output for each letter of the alphabet:</p> <pre><code>['a', 'ah', 'bah', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] ['b', 'ba', 'bac', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] ['c', 'ca', 'cap', 'camp', 'campo', 'campho', 'camphor', 'camphory', 'camphoryl', 'camphoroyl'] ['d', 'ad', 'cad', 'card', 'carid', 'carida', 'caridea', 'acaridea', 'acaridean'] ['e', 'er', 'ser', 'sere', 'secre', 'secret', 'secreto', 'secretor', 'secretory', 'asecretory'] ['f', 'fo', 'fot', 'frot', 'front', 'afront', 'affront', 'affronte', 'affronted'] ['g', 'og', 'log', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] ['h', 'ah', 'bah', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] ['i', 'ai', 'lai', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] ['j', 'ju', 'jug', 'juga', 'jugal', 'jugale'] ['k', 'ak', 'sak', 'sake', 'stake', 'strake', 'straked', 'streaked'] ['l', 'la', 'lai', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] ['m', 'am', 'cam', 'camp', 'campo', 'campho', 'camphor', 'camphory', 'camphoryl', 'camphoroyl'] ['n', 'an', 'lan', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] ['o', 'lo', 'loy', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] ['p', 'pi', 'pig', 'prig', 'sprig', 'spring', 'springy', 'springly', 'sparingly', 'sparringly'] ['q'] ['r', 'ra', 'rah', 'rach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] ['s', 'si', 'sig', 'spig', 'sprig', 'spring', 'springy', 'springly', 'sparingly', 'sparringly'] ['t', 'ut', 'gut', 'gutt', 'gutte', 'guttle', 'guttule', 'guttulae', 'guttulate', 'eguttulate'] ['u', 'ut', 'gut', 'gutt', 'gutte', 'guttle', 'guttule', 'guttulae', 'guttulate', 'eguttulate'] ['v', 'vu', 'vum', 'ovum'] ['w', 'ow', 'low', 'alow', 'allow', 'hallow', 'shallow', 'shallowy', 'shallowly'] ['x', 'ox', 'cox', 'coxa', 'coxal', 'coaxal', 'coaxial', 'conaxial'] ['y', 'ly', 'loy', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] ['z', 'za', 'zar', 'izar', 'izard', 'izzard', 'gizzard'] </code></pre> <p>Edit: Given the degree to which branches merge towards the end, I thought it would be interesting to draw a graph to demonstrate this:</p> <p><a href="http://picasaweb.google.com/arachnidandlex/BlogImages#5453996960338897106" rel="nofollow noreferrer"><img src="https://lh6.ggpht.com/_23zDbjk-dKI/S7B9VsMPaNI/AAAAAAAABps/PLqBwvC-Fg4/s800/wordgraph.png" alt="Graph"></a></p> <p>An interesting extension of this challenge: It's likely there are several equilength final words for some letters. Which set of chains minimizes the number of final nodes (eg, merges the most letters)?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload