words.py

import operator
from graphviz import Digraph

alphabet = 'qwertyuiopasdfghjklzxcvbnm'

with open('/usr/share/dict/british-english') as f:
    WORDS = {
        word.strip()
        for word in f
        if all(c in alphabet for c in word.strip())
    }
    print(len(WORDS), 'words')

def get_chain_words(word):
    new_words = {}
    for i in range(len(word)):
        new_word = word[:i] + word[i+1:]
        if new_word in WORDS:
            new_words[new_word] = get_chain_words(new_word)
    return new_words

def calc_depth(d, word, c=1):
    if d[word]:
        return max(calc_depth(d[word], k, c+1) for k in d[word])
    else:
        return c

def create_graph(chain, word, dot=None, base=None):
    if dot is None:
        dot = Digraph(format='png')
    if base is None:
        base = word
    else:
        base = f'{base}_{word}'

    dot.node(base, word)
    for w, words in chain[word].items():
        node = f'{base}_{w}'
        dot.node(node, w)
        dot.edge(base, node)
        dot = create_graph(chain[word], w, dot, base)
    return dot

if __name__ == '__main__':
    chain = {word: get_chain_words(word) for word in WORDS}

    chain_lengths = {word: calc_depth(chain, word) for word in chain}

    n = max(chain_lengths.items(), key=operator.itemgetter(1))[1]

    print('max chain length:', n)
    for word, length in chain_lengths.items():
        if length == n:
            print(word)
            dot = create_graph(chain, word)
            dot.render(word)

z_carrousels.png

z_colonisers.png

z_splittings.png