Member Avatar for Netcode

Am new to python and i need help dealing so i would go ahead and post the question and my little solution so far.

Question: a Procedure which takes four parameters as follows;
Dictionary File- the file name of a text file containing four letter words
Start Word- a four letter word (that you can assume is found in the Dictionary File file)
End Word- a four letter word (that you can assume is found in the Dictionary File file)
Result File- the file name of a text file that will contain the result
The result is the shortest list of four letter words, starting with StartWord, and ending with EndWord, with a number of intermediate words that are to be found in the DictionaryFilefile where each word differs from the previous word by precisely one letter.

So far, i've been able to return true or false if the searched strings exist. I used a list because i didnt wanna use a file so i loaded sample words into a list. See my code below but i wanna achieve the above.

# create list of words
dicfile = ["ante", "ants", "calf", "call", "calm", "clam", "diet", "dire", "earl", "edit",
        "emit", "erst", "fail", "fate", "feat", "feta", "ires", "irks", "item", "lair",
        "lame", "late", "leap", "les", "lets", "liar", "lips", "lira","list", "lite", 
        "male", "mall", "mate", "matt", "meal", "meat", "mint", "mite", "mitt", "naps",
        "neat", "nips", "nite", "nits", "opts", "pale", "pans", "past", "pate", "pats",
        "peal", "peat", "pest", "pets", "pier", "pins", "pits", "plea", "post", "pots", 
        "rail", "rant", "rate", "real", "rest", "rial", "ride", "ripe", "rise", "risk",
        "rite", "rite", "shin", "silt", "sire", "slip", "slit", "snap", "snip", "snit", 
        "span", "spat", "spin", "spit", "spot", "step", "stop", "tale", "tall", "tame", 
        "tans", "tape", "taps", "tare", "tarn", "teal", "team", "tear", "tide", "tied",
        "tier", "tier", "tile", "time", "tine", "tins", "tint", "tips", "tire", "tire", 
        "tops", "lisp"] 

print len(dicfile)

def is_string_in_list(startword, endword, dicfile):
    for str in startword, endword:
        if str not in dicfile:
            return False
        return True

#test the function
print (is_string_in_list("stone", "son", dicfile))
Edited by Netcode
  • 3 Contributors
  • 7 Replies
  • 312 Views
  • 6 Days Discussion Span
  • Latest Post Latest Post by Netcode

Dani AI

Generated

This is the classic "word ladder" problem. is correct to check lengths; words must all be the same length (four letters here). As pointed out, treat each word as a graph node and edges join words that differ by one letter — but to guarantee the shortest sequence use breadth‑first search (BFS), not depth‑first. For large dictionaries it’s faster to build neighbors with a wildcard/bucket technique (e.g. replace each letter in turn with a placeholder) instead of comparing every pair (avoids O(n^2) pairwise checks).

Below is a compact, practical procedure that takes the dictionary filename, start word, end word and result filename, writes one word per line to the result file, and returns the ladder as a Python list. It:

  • normalizes and filters words to the correct length,
  • indexes words by wildcard buckets for fast neighbor lookup,
  • runs BFS to find a shortest path,
  • writes "No path found" (or an error) if needed.
def find_shortest_ladder(dict_file, start, end, result_file):
    from collections import defaultdict, deque

    start = start.strip().lower()
    end = end.strip().lower()
    if len(start) != len(end):
        with open(result_file, 'w') as f:
            f.write('No path found (different lengths)\n')
        return []

    with open(dict_file) as fh:
        words = set(w.strip().lower() for w in fh if len(w.strip()) == len(start))

    if start not in words or end not in words:
        with open(result_file, 'w') as f:
            f.write('Start or end word not in dictionary\n')
        return []

    L = len(start)
    buckets = defaultdict(list)
    for w in words:
        for i in range(L):
            buckets[w[:i] + '*' + w[i+1:]].append(w)

    q = deque([start])
    parent = {start: None}
    while q:
        cur = q.popleft()
        if cur == end:
            break
        for i in range(L):
            key = cur[:i] + '*' + cur[i+1:]
            for nb in buckets[key]:
                if nb not in parent:
                    parent[nb] = cur
                    q.append(nb)
            buckets[key] = []  # avoid revisiting same bucket

    if end not in parent:
        with open(result_file, 'w') as f:
            f.write('No path found\n')
        return []

    path = []
    node = end
    while node:
        path.append(node)
        node = parent[node]
    path.reverse()
    with open(result_file, 'w') as f:
        f.write('\n'.join(path))
    return path

Notes: trim and lowercase your dictionary lines, handle duplicates with a set, and if you want to allow start/end not present in the file you can add them to words before indexing. This approach is memory‑efficient for typical 4‑letter dictionaries and guarantees a shortest ladder.

Recommended Answers

All 7 Replies

Member Avatar for vegaseat

I thought that startword and endword have to be four letter words?

Member Avatar for Gribouillis

The 4 letters words are nodes in a graph where adjacent nodes differ by one letter from the current node. Starting from the startword, you can do a depth first walk of the graph until you reach the endword. I posted a clue for depth first traversal here (replace urls with 4 letter words).

Edited by Gribouillis
Member Avatar for Netcode

I thought that startword and endword have to be four letter words?

yes, they are both four letter words and are words assumed to be in the list. If you take a good look at the list, all words there are four letter words.

Member Avatar for Gribouillis

Here is the graph, generated with this code snippet and a few more lines:

from fastgraph import graph

dicfile = ["ante", "ants", "calf", "call", "calm", "clam", "diet", "dire", "earl", "edit",
        "emit", "erst", "fail", "fate", "feat", "feta", "ires", "irks", "item", "lair",
        "lame", "late", "leap", "les", "lets", "liar", "lips", "lira","list", "lite", 
        "male", "mall", "mate", "matt", "meal", "meat", "mint", "mite", "mitt", "naps",
        "neat", "nips", "nite", "nits", "opts", "pale", "pans", "past", "pate", "pats",
        "peal", "peat", "pest", "pets", "pier", "pins", "pits", "plea", "post", "pots", 
        "rail", "rant", "rate", "real", "rest", "rial", "ride", "ripe", "rise", "risk",
        "rite", "rite", "shin", "silt", "sire", "slip", "slit", "snap", "snip", "snit", 
        "span", "spat", "spin", "spit", "spot", "step", "stop", "tale", "tall", "tame", 
        "tans", "tape", "taps", "tare", "tarn", "teal", "team", "tear", "tide", "tied",
        "tier", "tier", "tile", "time", "tine", "tins", "tint", "tips", "tire", "tire", 
        "tops", "lisp"]

def dist(word, other):
    return sum([1 if (x == y) else 0 for (x, y) in zip(word, other)])

def all_items():
    for i, word in enumerate(dicfile):
        for other in dicfile[i+1:]:
            if dist(word, other) == 3:
                yield (word, other)

if __name__ == '__main__':
    def label(x):
        return x

    g = graph(all_items(), label)
    g.draw('dicfile.png', prog='fdp') # prog can be neato|dot|twopi|circo|fdp|nop
dicfile.png.zip (263.13 KB)
Member Avatar for Netcode

Gribouillis, thanks for your reply. However, if you read my very first statement just before the question at hand, you will know its likely you have added to my worries.

Member Avatar for Gribouillis

Yes, you are new to python, but not to programming. Here is a simpler snippet to create an adjacency dictionary

dicfile = ...

def dist(word, other):
    return sum(1 if (x == y) else 0 for (x, y) in zip(word, other))

def all_items():
    for i, word in enumerate(dicfile):
        for other in dicfile[i+1:]:
            if dist(word, other) == 3:
                yield (word, other)
                yield (other, word)

if __name__ == '__main__':

    from collections import defaultdict
    from pprint import pprint

    D = defaultdict(set)
    for k, v in all_items():
        D[k].add(v)
    D = dict(D)
    pprint(D)

""" my output:
{'ante': set(['ants']),
 'ants': set(['ante']),
 'calf': set(['call', 'calm']),
 'call': set(['calf', 'calm', 'mall', 'tall']),
 'calm': set(['calf', 'call']),
 'dire': set(['sire', 'tire']),
 'edit': set(['emit']),
 'emit': set(['edit']),
 'fail': set(['rail']),
 'fate': set(['late', 'mate', 'pate', 'rate']),
 'feat': set(['meat', 'neat', 'peat']),
 ...
 """
Edited by Gribouillis
Member Avatar for Netcode

Thanks alot. Got it!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.