Every week, NPR does a puzzle segment with Will Shortz, the editor of the New York Times crossword. Each week, a new puzzle is given out, the solution of which must be submitted to NPR by 3PM the following Thursday.

I've decided that I'm going to start posting these questions the following Sunday, after the answer has been released to the general public, with a way to find a programmatic solution. Generally, the puzzles are based around some sort of wordplay or manipulation, so they should be eminently Pythonable.

Last week's puzzle is as follows:

Think of a common nine-letter word that contains five consecutive consonants. Take three consecutive consonants out of these five and replace them with vowels to form another common nine-letter word. What is it?

Here's a Python script that'll give you the answer. Note that depending on your system, you may need to point it at a different words file. The standard words file may also not work, so I'm using urllib to get a larger dictionary. I'm also counting Y as both a vowel and a consonant to be sure I don't miss any possible combinations.

Also note that I'm using a set object to store my words. This is because I'm going to be doing a lot of lookup operations against it to determine if words I've created are actually valid, and the list is very long. As a result, using a list or tuple would be time prohibitive to search, with O(n) average time complexity, whereas a set, storing each item as a value keyed by hash, gives me an average of O(1) time complexity, with O(n) as a worst-case scenario.

from __future__ import print_function

try:
    from urllib2 import urlopen

except ImportError:
    from urllib.request import urlopen

CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
VOWELS = 'aeiouy'
DICTIONARY_URL = 'http://www-01.sil.org/linguistics' \
                 '/wordlists/english/wordlist/wordsEn.txt'

def main():
    words = set(urlopen(DICTIONARY_URL).read().decode('utf-8').splitlines())
    possible_substitutions = {x for x in substitutions(VOWELS, 3)}
    for word in compatible_words(words):
        for new_word in valid_changes(word, possible_substitutions, words):
            print('Original word "{}" becomes "{}"'.format(word, new_word))

def is_word_compatible(word):
    if len(word) != 9:
        return False
    for i in range(5):
        if all(x in CONSONANTS for x in word[i:i+5]):
            return True
    return False

def compatible_words(words):
    for word in words:
        if is_word_compatible(word):
            yield word

def substitutions(charset, length):
    for char in charset:
        if length == 1:
            yield char
        else:
            for string in substitutions(charset, length-1):
                yield char + string

def valid_changes(word, substitutions, real_words):
    for i in range(6):
        to_replace = word[i:i+3]
        if all(x in CONSONANTS for x in to_replace):
            for sub in substitutions:
                new = word.replace(to_replace, sub)
                if new in real_words:
                    yield new

if __name__ == '__main__':
    main()