Saya punya pertanyaan, di mana saya perlu mengimplementasikan masalah tangga dengan logika yang berbeda.

Di setiap langkah, pemain harus menambahkan satu huruf ke kata dari langkah sebelumnya, atau mengambil satu huruf, lalu menyusun ulang huruf untuk membuat kata baru.

Croissant(-C) -> arsonist(-S) -> aroints(+E)->notaries(+B)->baritones(-S)->baritone

Kata baru harus masuk akal dari wordList.txt yang merupakan kamus kata.

Kamus

Kode saya terlihat seperti ini, di mana saya telah menghitung terlebih dahulu jumlah karakter yang dihapus "remove_list" dan menambahkan "add_list". Kemudian saya telah menyimpan nilai itu dalam daftar.

Kemudian saya membaca file tersebut, dan disimpan ke dalam kamus yang diurutkan berpasangan.

Kemudian saya mulai menghapus dan menambahkan kata awal dan mencocokkan dengan kamus.

Tapi sekarang tantangannya adalah, beberapa kata setelah penghapusan dan penambahan tidak sesuai dengan kamus dan meleset dari tujuan.

Dalam hal ini, itu harus mundur ke langkah sebelumnya dan harus menambahkan alih-alih mengurangi.

Saya mencari semacam fungsi rekursif, yang dapat membantu dalam hal ini atau menyelesaikan logika baru yang dapat saya bantu untuk mencapai output.

Contoh kode saya.

start = 'croissant'
goal =  'baritone'

list_start = map(list,start)
list_goal = map(list, goal)



remove_list = [x for x in list_start if x not in list_goal]

add_list = [x for x in list_goal if x not in list_start]



file = open('wordList.txt','r')
dict_words = {}
for word in file:
   strip_word = word.rstrip()
   dict_words[''.join(sorted(strip_word))]=strip_word
   file.close()
final_list = []


flag_remove = 0

for i in remove_list:
   sorted_removed_list = sorted(start.replace(''.join(map(str, i)),"",1))
   sorted_removed_string = ''.join(map(str, sorted_removed_list))

   if sorted_removed_string in dict_words.keys():
       print dict_words[sorted_removed_string]
       final_list.append(sorted_removed_string)
       flag_remove = 1
   start = sorted_removed_string
print final_list


flag_add = 0    
for i in add_list:
    first_character = ''.join(map(str,i))
    sorted_joined_list = sorted(''.join([first_character, final_list[-1]]))
    sorted_joined_string = ''.join(map(str, sorted_joined_list))

   if sorted_joined_string in dict_words.keys():
       print dict_words[sorted_joined_string]
       final_list.append(sorted_joined_string)
       flag_add = 1
sorted_removed_string = sorted_joined_string
1
nvnvashisth 16 Desember 2017, 17:44

1 menjawab

Jawaban Terbaik

Pelacakan mundur berbasis rekursi bukanlah ide yang baik untuk masalah pencarian semacam ini. Itu secara membabi buta turun di pohon pencarian, tanpa mengeksploitasi fakta bahwa kata-kata hampir tidak pernah berjarak 10-12 dari satu sama lain, menyebabkan StackOverflow (atau batas rekursi terlampaui dengan Python).

Solusinya di sini menggunakan pencarian luas-pertama. Ia menggunakan mate(s) sebagai pembantu, yang diberi kata s, menemukan semua kemungkinan kata yang dapat kita tuju berikutnya. mate pada gilirannya menggunakan kamus global wdict, yang telah diproses sebelumnya di awal program, yang untuk kata tertentu, menemukan semua anagramnya (yaitu penataan ulang huruf).

from queue import Queue
words = set(''.join(s[:-1]) for s in open("wordsEn.txt"))
wdict = {}
for w in words:
    s = ''.join(sorted(w))
    if s in wdict: wdict[s].append(w)
    else: wdict[s] = [w]

def mate(s):
    global wdict
    ans = [''.join(s[:c]+s[c+1:]) for c in range(len(s))]
    for c in range(97,123): ans.append(s + chr(c))
    for m in ans: yield from wdict.get(''.join(sorted(m)),[])

def bfs(start,goal,depth=0):
    already = set([start])
    prev = {}
    q = Queue()
    q.put(start)
    while not q.empty():
        cur = q.get()
        if cur==goal:
            ans = []
            while cur: ans.append(cur);cur = prev.get(cur)
            return ans[::-1] #reverse the array
        for m in mate(cur):
            if m not in already:
                already.add(m)
                q.put(m)
                prev[m] = cur


print(bfs('croissant','baritone'))

Yang menghasilkan: ['croissant', 'arsonist', 'rations', 'senorita', 'baritones', 'baritone']

1
Shihab Shahriar Khan 16 Desember 2017, 19:24