Saya memiliki daftar dengan 794 kata yang panjangnya tiga huruf. Tugas saya adalah menemukan kata dengan jalur terpanjang menuju kata tertentu.
Definisi (anak-anak):
Anak-anak dari kata induk adalah kata induk dengan satu dan hanya satu huruf yang diganti.
Contoh:
'can', 'run', 'rap' dan sebagainya adalah turunan dari kata 'ran' (mengingat kata-kata tersebut ada dalam daftar).
Definisi (jalur):
Jalur adalah rangkaian kata yang setiap kata dihasilkan dengan menukar satu huruf pada kata sebelumnya.
#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.
Ide saya adalah ini akan memberikan jalur terpanjang sejak kita terus menghasilkan anak-anak baru sampai kita kehabisan kemungkinan anak-anak (yaitu, anak-anak yang belum pernah dikunjungi).
Pertanyaan:
Apakah ide saya valid? Bagaimana cara menguji apakah ini benar-benar berfungsi?
Kode sebenarnya dapat dilihat di bawah, tetapi mungkin tidak masuk akal tanpa komentar.
Edit
Karena pohon dan daftar bisa agak lambat, saya menggantinya dengan set.
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)
