The width of the first search with three-letter words, optimization

Question

I use the width search algorithm in Python to find the shortest "path" from a three-letter word to another. It works for me, but the performance is terrible, and I suspect that the word generation function in my word.

Basically, for every word that I exit the queue, I generate all the other three-letter words that can be formed by exchanging one letter. The function works as follows:

#Pseudo code For each position (1-3) For each letter (az) create a new word by exchanging the letter at the position if this word is a valid word and is not used earlier add it to the return list return the list 

It usually takes about 0.03 seconds. Is there a faster way to do this?

Answer 1

If you want to invent a wheel, maybe this would help (NB This gave literals, so it needs at least Python 2.7):

 from collections import defaultdict WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'} D1 = defaultdict(set) D2 = defaultdict(set) D3 = defaultdict(set) for w in WORDS: D1[w[:2]].add(w) D2[w[0]+w[2]].add(w) D3[w[1:]].add(w) def follows(w): followers = set(D1.get(w[:2]).union(D2.get(w[0]+w[2]), D3.get(w[1:]))) followers.discard(w) return followers for w in WORDS: print(w, follows(w)) 

Answer 2

I assume that you have a list of valid words, and you are not really looking for one way (why do you need to optimize it), but for many ways. This can be done quite easily with networkX :

 from networkx import Graph from networkx.algorithms.shortest_paths import shortest_path, all_pairs_shortest_path from itertools import combinations WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'} def makeGraph(words): """ create a graph where nodes are words and two words are connected iff they have one different letter """ G = Graph() # all word combinations for a,b in combinations(WORDS,2): # number of different letters diff = sum(1 for x,y in zip(a,b) if x!=y) if diff == 1: G.add_edge(a,b) return G g = makeGraph(WORDS) # path between two words print shortest_path(g, 'cat', 'pad') # generating all shortest paths is way more efficient if you want many paths paths = all_pairs_shortest_path(g) print paths['cat']['pad'] 

Thanks @Ducan for examples of words.

If you really want to implement these algorithms yourself, you can find many descriptions in wikipedia . The classic Dijkstra's single-source shortest path algorithm and the classic Floyd-Warshall shortest path algorithm.

Answer 3

Instead of reinventing the wheel, perhaps not optimal: use existing modules:

http://pypi.python.org/pypi/altgraph/0.8