maximum-length minimal word ladders

wordladder.py

#!/usr/local/bin/python3

import sys
from networkx import nx
from pprint import pprint
from functools import reduce

N = 4

words=[w.strip()
       for w in open('/usr/share/dict/words').readlines()
       if len(w.strip()) == N and w.islower()]

def nc(c):
    return ord(c) - ord('a')

A = [[[] for _ in range(26)]
      for _ in range(N)]

for i in range(N):
    for j in range(len(words)):
        A[i][nc(words[j][i])].append(j)

A1 = [[frozenset(A[i][j]) for j in range(26)]
      for i in range(N)]

def neighbors(w):
    word = words[w]
    sets = [A1[j][nc(word[j])]
            for j in range(N)]
    neighbors = reduce(lambda a, b: a | b,
                       [reduce(lambda a, b: a & b,
                               [sets[j] for j in range(N)
                                if j != i])
                        for i in range(N)])
    return neighbors - {w}

G = nx.Graph()
G.add_nodes_from(words)
for w in range(len(words)):
    G.add_edges_from((words[w], words[k]) for k in neighbors(w))

K, P = 0, []
for s, p in nx.shortest_path_length(G).items():
    for t, l in p.items():
        if l > K:
            K, P = l, []
        if l == K:
            P.append(nx.shortest_path(G, s, t))

print(K)
pprint(P)