python - Transforming source word into target word -

i need code. need convert 1 input word another, changing 1 letter @ time. program inefficiently , not find shortest route. appreciated.

import re def same(item, target):   return len([c (c, t) in zip(item, target) if c == t])  def build(pattern, words, seen, list):   return [word word in words                  if re.search(pattern, word) , word not in seen.keys() ,                     word not in list]  def find(word, words, seen, target, path):   list = []   in range(len(word)):     list += build(word[:i] + "." + word[i + 1:], words, seen, list)   if len(list) == 0:     return false   list = sorted([(same(w, target), w) w in list])   (match, item) in list:     if match >= len(target) - 1:       if match == len(target) - 1:         path.append(item)       return true     seen[item] = true   (match, item) in list:     path.append(item)     if find(item, words, seen, target, path):       return true     path.pop()  fname = 'dictionary.txt' file = open(fname) lines = file.readlines() while true:   start = input("enter start word:")   words = []   line in lines:     word = line.rstrip()     if len(word) == len(start):       words.append(word)   target = input("enter target word:")   break  count = 0 path = [start] seen = {start : true} if find(start, words, seen, target, path):   path.append(target)   print(len(path) - 1, path) else:   print("no path found") 

edit: below failed attempt me fix problem trying different approach. time not seem loop properly.

def find(start, words, target): # find function. word = start word, words =    start=list(start)   target=list(target)    print("start word ", start)   print("target word ", target)     letter = 0   while start != target:       if letter == len(target):           letter = 0           continue        elif start[letter] == target[letter]:           letter = letter + 1           continue        else:           testword = list(start)           testword[letter] = target[letter]           testword = ''.join(testword)           if testword in words:               start[letter] = target[letter]               letter = letter + 1               print(start)               continue           else:               letter = letter + 1               continue        letter = letter + 1       continue     fname = "dictionary.txt" file = open(fname) # open dictionary lines = file.readlines() # read each line dictionary , store in lines while true: # until ended   start = input("enter start word:") # take word user   words = [] # inititialise array 'words'   line in lines: # each line in dictionary     word = line.rstrip() #strip white space , characters end of string     if len(word) == len(start):       words.append(word)    if start not in words:       print("your start word not valid")       continue    target = input("enter target word:")   if len(start) != len(target):       print("please choose 2 words of equal length")       continue    if target not in words:       print("your target word not valid")       continue     break 

edit: here basic algorithm code. (both variants compatiable purpose).

-input start word -input target word - if len(start) = len(target)        continue        -check dictionary see if target , start words present        - find letters different start target word        - change 1 different letter in start word until start word          =target          word #after each letter change, output must valid word in dictionary goal achieve in least amount of steps not achieved, first section of code this, think in huge amount of steps know far more efficient 

here's breadth-first search doesn't use 3rd party modules. don't guarantee finds shortest solutions, appears work. ;) stops when finds solution, due random order of sets each run of program may find different solution given start & target pair.

import re  # file containing dictionary fname = '/usr/share/dict/words'  start, target = 'hide', 'seek'  wlen = len(start) wrange = range(wlen)  words = set() open(fname) f:     word in f:         w = word.rstrip()         # grab words of correct length aren't proper nouns         # , don't contain non-alpha chars apostrophe or hyphen         if len(w) == wlen , w.islower() , w.isalpha():             words.add(w) print('word set size:', len(words))  # build regex find words differ `word` 1 char def make_pattern(word):     pat = '|'.join(['{}.{}'.format(word[:i], word[i+1:]) in wrange])     return re.compile(pat)  # find words extend each chain of words in `seq` def find(seq):     result = []     seen = set()     current in seq:         pat = make_pattern(current[-1])         matches = {w w in words if pat.match(w)} - seen         if target in matches:             return current + (target,)         result.extend(current + (w,) w in matches)         seen.update(matches)         words.difference_update(matches)     seq[:] = result  # search solution seq = [(start,)] words.discard(start) while true:     solution = find(seq)     if solution:         print(solution)         break     size = len(seq)     print(size)     if size == 0:         print('no solutions found')         break 

typical output

word set size: 2360 9 55 199 479 691 ('hide', 'hire', 'here', 'herd', 'heed', 'seed', 'seek') 

---

i ought mention word chains chew bit of ram, i'll try think of more compact approach. shouldn't problem on modern machines, unless you're working large words.