CODEWITHSUNDEEP
pythonpython-3.xpython-3.5
Lozansky
Lozansky

Reputation: 374

Find longest path with BFS

I have a list with 794 three-letter long words. My task is to find the word(s) with the longest path to a given word.

Definition (children):
Children to a parent word are the parent word with one and only one letter replaced.

Example:
'can', 'run', 'rap' etcetera are children to the word 'ran' (given that those words exist in the list).

Definition (path):
A path is a series of words where each word is generated by exchanging a single letter in the previous.

#Pseudo code
Given a word 
    Put the word in a queue
    Keep a list with all visited words
    As long as the queue is not empty
        Get the first word in the queue
        Generate a list with all the children to this word
        For every children in that list
            If the child is not in the list of visited words
                Append the child to the list of visited words
                Put the child in the queue
    Print the path to the last grandchild.

My idea is that this will give the longest path since we continue to generate new children until we run out of possible children (that is, children that hasn't already been visited).

Question:
Is my idea valid? How can I test if it actually works?

The actual code can be viewed below, but it might not make any sense without comments.

Edit
Since trees and lists can be a bit slow, I replaced them with sets. 

from Queue import Queuenode; import Bintree
with open('word3',encoding='utf-8') as f:
    lista=f.readlines()
    lista=[x.strip('\n') for x in lista]
alfabet='abcdefghijklmnopqrstuvwxyzåäö'
class Word:
    def __init__(self, w, f = None):
        self.word = w
        self.parent = f
children=Bintree.Bintree()
for i in lista:
    children.put(i)
def barn(far):
    barnlista=[]
    for i in range(3):
        for j in range(29):
            empty=''
            empty+=far[0:i]+alfabet[j]+far[i+1:]
            if empty!=far and children._exists(empty):
                barnlista+=[empty]
    return barnlista
ko=Queuenode()
def vag(item):
    start=item
    counter=0
    while start!=None:
        counter+=1
        print(start.word)
        start=start.parent
    print(counter)
def bfsx(startord):
    ko.put(Word(startord))
    besokta=[startord]
    while not ko.isempty():
        first=ko.get()
        lista=barn(first.word)
        for child in lista:
            if child not in besokta:
                besokta+=[child]
                ko.put(Word(child,first))
    vag(first)

Upvotes: 2

Views: 630

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76381

IIUC, this is not guaranteed to work (in fact, you can build cases where it doesn't).

Suppose you start at node a; there is a direct path a → b; there are also a direct path a → c and an indirect path c ⇒ b.

Suppose that when you iterate over the children of a, you encounter b before c. You deal with b and mark it as visited. At some point later you encounter c, and eventually reconsider b again. At that point, however, b is already considered visited, so your algorithm will consider the shorter subpath a → b rather than the longer one a → c ⇒ b.

You cannot also get rid of the "visited" mark, as the story behind your graph makes it clear it is not a DAG. If you remove the "visited" logic, you will encounter infinite loops.

Upvotes: 1

Related Questions