Wawancara Coding: Bagaimana Cara Menyelesaikan Word Ladder dengan BFS Dua Arah?

Pertanyaan dan Konteks yang Berlaku

Diberikan beginWord, endWord, dan wordList, temukan panjang urutan transformasi terpendek. Setiap pasangan kata yang berdekatan harus berbeda tepat pada satu posisi, dan setiap kata setelah beginWord, termasuk endWord, harus muncul di dalam kamus. Panjang yang dikembalikan menghitung jumlah kata, bukan jumlah perubahan.

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence:
hit -> hot -> dot -> dog -> cog

Return: 5

Gunakan kontrak standar: beginWord dan endWord berbeda, semua kata berisi huruf kecil alfabet Inggris, setiap kata dalam kamus memiliki panjang yang sama L, entri kamus bersifat unik, dan terdapat paling banyak N = 5,000 entri. Jika endWord tidak ada atau tidak dapat dijangkau, kembalikan 0.

Ini adalah soal graf yang struktur grafnya tersembunyi di dalam string. Setiap kata yang valid adalah sebuah verteks; dua kata dihubungkan oleh edge tak berarah dengan bobot satuan jika keduanya berbeda pada satu posisi. Oleh karena itu, pertanyaan ini meminta jalur terpendek pasangan tunggal (single-pair shortest path) pada graf tanpa bobot. Materi wawancara graf publik pada tahun 2026 masih mencantumkan Word Ladder sebagai masalah transformasi BFS, dan sebuah laporan wawancara publik pada Juni 2026 membahas varian Word Ladder II yang lebih sulit. Catatan-catatan tersebut menetapkan nilai persiapan saat ini; catatan tersebut tidak menetapkan frekuensi wawancara atau atribusi perusahaan yang terverifikasi, sehingga artikel ini tidak membuat klaim keduanya.

Apa yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah kandidat dapat mengenali graf implisit. Membandingkan setiap pasangan kata dalam kamus dapat membentuk graf yang benar, tetapi membutuhkan biaya O(N²L) perbandingan karakter. Jawaban yang lebih baik hanya menghasilkan tetangga yang memungkinkan dari kata saat ini: ganti masing-masing dari L karakternya dengan 25 huruf lainnya, lalu gunakan hash set untuk menguji keanggotaan dalam kamus.

Sinyal kedua adalah argumen jalur terpendek. Setiap transformasi membutuhkan satu langkah, sehingga BFS mengeksplorasi keadaan (state) berdasarkan jarak yang tidak menurun (nondecreasing). DFS mungkin pada akhirnya menemukan jalur tetapi tidak menjamin jalur pertama adalah yang terpendek. Dijkstra benar untuk bobot satuan, tetapi menambahkan antrean prioritas tanpa memberikan informasi tambahan.

Sinyal ketiga adalah waktu penandaan telah dikunjungi (visited timing). Sebuah kata harus keluar dari set unvisited ketika ia masuk ke dalam frontier, bukan ketika ia diekspansi nanti. Penundaan penandaan memungkinkan banyak simpul induk memasukkan kata yang sama ke dalam antrean, meningkatkan beban kerja dan memori. Pada BFS dua arah, tetangga yang dihasilkan harus diperiksa terhadap frontier aktif dari arah berlawanan sebelum diperiksa terhadap set unvisited.

Sinyal keempat adalah apakah optimasi tersebut tetap dapat dibuktikan secara formal. BFS dua arah mempertahankan satu frontier tingkat (level frontier) dari masing-masing titik ujung dan mengekspansi frontier yang lebih kecil. Pendekatan ini sering kali memangkas pencarian seperti pohon dari sekitar b^d keadaan menjadi dua pencarian di sekitar b^(d/2), di mana b adalah percabangan efektif dan d adalah jawabannya dalam jumlah edge. Hal ini tidak meningkatkan batas asimtotik kasus terburuk: kamus yang adversarial tetap dapat membuat algoritma memeriksa hampir setiap kata.

Terakhir, jawaban yang kuat menyebutkan biaya string yang sebenarnya. Setiap kata yang diekspansi mencoba paling banyak 25L mutasi. Di Python, membuat string kandidat membutuhkan biaya O(L), sehingga implementasi ini memiliki ekspektasi waktu O(NL²) untuk alfabet tetap 26 huruf, dengan penyimpanan karakter O(NL). Menyebutnya sebagai O(NL) secara implisit menganggap konstruksi string terjadi dalam waktu konstan.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apa yang sebenarnya dihitung oleh nilai kembalian? Kontrak ini menghitung kedua titik ujung. Oleh karena itu, transformasi valid langsung

mengembalikan 2; API yang menghitung edge akan mengembalikan satu lebih sedikit.

• Apakah endWord harus ada di dalam kamus? Ya. Jika tidak ada, kembalikan 0 sebelum melakukan pencarian. Varian

yang memperbolehkan target berada di luar kamus akan mengubah aturan keluar awal (early-exit) ini.

• Apakah semua kata memiliki panjang dan alfabet yang sama? Ya: panjang L, huruf kecil alfabet Inggris. Unicode,

panjang yang bervariasi, atau alfabet yang lebih besar akan mengubah cara pembuatan tetangga dan biayanya.

• Apakah setiap entri unik? Ya. Mengonversi input menjadi set tetap berguna untuk keanggotaan dan penghapusan visited dengan waktu konstan yang diharapkan.

Jika duplikat diizinkan, mereka tidak akan membuat verteks yang berbeda.

• Apakah kita memerlukan satu nilai panjang, satu jalur, atau semua jalur terpendek? Masalah dasar hanya memerlukan panjangnya saja.

Mengembalikan jalur memerlukan pemetaan simpul induk (parent map); mengembalikan semua jalur terpendek memerlukan penyimpanan seluruh simpul induk dari level BFS yang sama dan tidak dapat menggunakan aturan penghapusan eager yang sama secara langsung.

• Apakah ini satu kueri atau banyak kueri pada kamus yang statis? Untuk satu kueri, mutasi sesuai kebutuhan (on-demand) bersifat sederhana dan menghindari pembentukan indeks lengkap. Kueri yang berulang dapat menjustifikasi penggunaan indeks pola wildcard yang dapat digunakan kembali.
• Bolehkah beginWord sudah muncul di dalam kamus? Ya. Kata tersebut tetap merupakan satu verteks dan harus dihapus dari set unvisited selama inisialisasi.

Kerangka Jawaban 30 Detik

“Saya memodelkan setiap kata sebagai verteks dan menghubungkan dua kata jika keduanya berbeda pada satu posisi. Setiap edge bernilai satu transformasi, jadi ini adalah masalah jalur terpendek tanpa bobot. Saya akan menjalankan BFS dua arah dari beginWord dan endWord, selalu mengekspansi frontier seluruh level yang lebih kecil. Untuk setiap kata di frontier, saya menghasilkan paling banyak 25L mutasi satu huruf dan mengujinya di hash set. Jika suatu mutasi berada di frontier yang berlawanan, dua prefiks terpendek yang telah dieksplorasi membentuk urutan terpendek, sehingga saya mengembalikan jumlah kata saat ini ditambah satu. Jika tidak, saya menghapus kata valid yang belum pernah dilihat segera setelah menambahkannya ke frontier berikutnya. Jika endWord tidak ada atau salah satu frontier menjadi kosong, saya mengembalikan nol. Kasus terburuk tetap mengunjungi N kata; karena konstruksi kandidat di Python menyalin L karakter, kompleksitas waktunya adalah O(NL²) dan konten string yang disimpan adalah O(NL). Saya akan menguji kasus langsung, tidak terjangkau, siklik, penemuan duplikat, dan frontier asimetris.”

Pembahasan Mendalam Langkah demi Langkah

Mulailah dengan model graf. Misalkan himpunan verteks berisi setiap kata dalam kamus ditambah beginWord. Untuk setiap dua kata dengan panjang yang sama, tambahkan edge tepat saat jarak Hamming keduanya adalah satu. Graf ini tidak berarah: jika hot dapat berubah menjadi dot, perubahan sebaliknya juga valid. Graf ini tidak berbobot karena setiap perubahan legal menyumbang satu edge.

Graf eksplisit berpasangan membandingkan O(N²) pasangan dan menghabiskan biaya O(L) per perbandingan. Itu memerlukan pra-pemrosesan sebesar O(N²L) bahkan ketika sebagian besar pasangan tidak berhubungan. Alfabet input menyediakan ruang kandidat yang lebih kecil. Sebuah kata memiliki paling banyak 25L mutasi satu huruf yang berbeda; keanggotaan kamus menentukan mana yang merupakan verteks nyata.

BFS satu arah sudah terbukti benar. Invariannya adalah:

At the start of level k:
  the frontier contains exactly the discovered words at edge distance k;
  no undiscovered word has distance less than k;
  every word outside unvisited has already been assigned its minimum distance.

BFS membuat level k + 1 hanya dari level k. Oleh karena itu, penemuan pertama suatu kata selalu menggunakan jalur terpendek. Menghapus suatu kata dari unvisited saat pertama kali ditemukan menjaga fakta tersebut dan mencegah duplikasi entri frontier.

Untuk satu target yang diketahui, lakukan pencarian dari kedua titik ujung. front adalah satu level lengkap dari sisi awal, dan back adalah satu level lengkap dari sisi akhir. sequence_length sama dengan jumlah kedalaman edge mereka saat ini ditambah satu, karena ia menghitung kata-kata di frontier pada kedua ujung tanpa edge penghubung terlebih dahulu. Mengekspansi salah satu frontier utuh akan meningkatkan jumlah kedalaman tersebut sebesar satu. Jika sebuah kata yang dihasilkan termasuk dalam frontier yang berlawanan, edge penghubung membuat jawabannya menjadi sequence_length + 1.

Mengekspansi frontier yang lebih kecil mengubah performa, bukan kebenaran algoritma. Menukar kedua set hanya mengubah lapisan BFS valid mana yang dimajukan berikutnya; setiap set tetap merepresentasikan satu kedalaman eksak dari titik awalnya masing-masing. Memeriksa perpotongan (intersection) terhadap frontier aktif dari arah berlawanan adalah hal yang sangat penting. Satu set global unvisited bersifat aman karena ketika salah satu sisi menemukan suatu kata, sisi tersebut langsung mengklaimnya. Jika ekspansi selanjutnya memiliki edge ke lapisan yang sudah diekspansi dari pencarian sisi lainnya, ekspansi sebelumnya pasti sudah menemukan kata tersebut lebih dulu, sehingga kedua pencarian tidak dapat saling bersilangan secara tak terlihat di belakang frontier aktif masing-masing.

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

Telusuri contoh berdasarkan lapisan frontier:

Algoritma mengekspansi sisi cog yang lebih kecil pada ekspansi 3. Pada ekspansi 4, dot mencapai dog atau lot mencapai log, sehingga mengembalikan 5. Urutan iterasi set mungkin memilih edge pertemuan terpendek yang berbeda; panjangnya tetap tidak berubah.

Misalkan N adalah ukuran kamus dan L adalah panjang kata. Setiap kata ditambahkan ke frontier paling banyak satu kali dan, jika diekspansi, mencoba 25L kandidat. Pencarian hash memiliki ekspektasi waktu O(1), tetapi setiap kandidat yang dibuat melalui pemotongan dan penggabungan (slice-and-concatenate) di Python membutuhkan biaya O(L), menghasilkan ekspektasi waktu kasus terburuk sebesar O(NL²) dengan alfabet tetap. Set menyimpan paling banyak O(N) referensi dan string-nya berisi O(NL) karakter. String kandidat sementara menambahkan O(L) pada satu waktu. Jika sebuah sesi wawancara menggunakan buffer karakter berukuran tetap yang dapat diubah (mutable) dan memperlakukan proses instansiasi atau hashing kandidat sebagai O(L), batas perhitungan yang cermat ini tetap berlaku.

Indeks wildcard adalah alternatif utama. Memetakan pola seperti h*t, *ot, dan ho* ke kata-kata yang cocok. Indeks ini dapat digunakan kembali di banyak kueri dan menghindari percobaan huruf yang tidak ada di dalam kamus. Di Python, membuat L string pola untuk N kata juga membutuhkan O(NL²) operasi karakter dan dapat menyimpan O(NL) entri bucket. Selama BFS, kosongkan bucket pola yang telah digunakan atau tandai sebagai sudah diproses; memindai bucket besar yang sama untuk banyak kata dapat menyebabkan timbulnya kembali kompleksitas kuadratik. Untuk satu kueri di bawah batasan yang telah disebutkan, pendekatan mutasi ditambah set memiliki komponen bergerak yang lebih sedikit.

Uji kontrak yang dapat dieksekusi, bukan hanya contoh dasar:

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

Pengujian berbasis properti (property tests) dapat menghasilkan kamus acak berukuran kecil, membangun graf eksplisit berpasangan sebagai trusted oracle, dan membandingkan hasil BFS biasanya dengan fungsi yang telah dioptimalkan. Jaga juga agar list input tidak berubah, uji kamus di mana satu frontier tumbuh jauh lebih cepat daripada yang lain, dan pastikan bahwa kata yang dapat dijangkau melalui beberapa simpul induk hanya diekspansi satu kali.

Contoh Jawaban Berkualitas Tinggi

“Kata-kata membentuk graf tak berarah implisit. Sebuah verteks adalah kata yang valid, dan sebuah edge menghubungkan kata-kata dengan jarak Hamming satu. Karena semua edge memiliki bobot satu, BFS memberikan jumlah transformasi minimum. Saya akan mengembalikan jumlah kata, sehingga hit -> hot memiliki panjang dua.

Pertama, saya memasukkan kamus ke dalam sebuah set dan menolak kasus di mana endWord tidak ditemukan. Saya mempertahankan satu frontier pada masing-masing titik ujung dan satu set kata yang belum ditemukan oleh kedua pencarian. Pada setiap iterasi, saya mengekspansi frontier lengkap yang lebih kecil. Untuk setiap kata dan posisi karakter, saya mencoba 25 huruf kecil lainnya. Saya memeriksa kandidat terhadap frontier yang berlawanan terlebih dahulu; jika cocok, itu menghubungkan dua prefiks BFS, sehingga jawabannya adalah jumlah kata yang terakumulasi ditambah satu. Jika tidak, jika kandidat tersebut belum dikunjungi, saya segera menghapusnya dan menambahkannya ke frontier berikutnya.

Invariannya adalah bahwa setiap frontier tepat berada pada satu lapisan jarak dari titik awalnya, dan setiap kata yang dihapus sudah memiliki jarak minimum dari sisi yang menemukannya. Mengekspansi sisi yang lebih kecil tidak mengubah lapisan-lapisan tersebut. Hubungan frontier yang pertama kali terjadi adalah yang terpendek karena jalur yang lebih pendek pasti sudah menghubungkan dua lapisan sebelumnya. Penghapusan langsung mencegah penemuan duplikat.

Paling banyak N kata diekspansi. Masing-masing mencoba 25L mutasi, dan Python menghabiskan O(L) untuk membangun setiap kandidat, jadi saya menyatakan ekspektasi waktu sebesar O(NL²) dan O(NL) karakter yang disimpan. Pencarian dua arah biasanya mengurangi keadaan yang dieksplorasi tetapi memiliki kasus terburuk yang sama. Untuk kueri berulang, saya akan mempertimbangkan indeks wildcard yang dapat digunakan kembali; untuk kueri sekali jalan ini, mutasi lebih sederhana. Saya akan memverifikasi contoh resmi, target yang hilang, transformasi langsung, beberapa rute terpendek, siklus, dan oracle graf eksplisit acak.”

Kesalahan Umum

• Menjalankan DFS dan mengembalikan jalur pertamanya → DFS tidak mengunjungi jalur berdasarkan jumlah transformasi →

Gunakan BFS karena setiap edge memiliki bobot satuan.

• Membandingkan setiap pasangan di kamus → konstruksi graf membutuhkan biaya O(N²L) → **Hasilkan paling banyak 25L

kandidat tetangga per kata yang diekspansi.**

• Menandai kata telah dikunjungi hanya saat dikeluarkan dari antrean (popped) → beberapa simpul induk dapat memasukkannya ke dalam antrean secara bersamaan → **Hapus kata dari

unvisited saat menambahkannya ke frontier.**

• Hanya memeriksa unvisited sebelum frontier yang berlawanan → kata pertemuan sudah dihapus

oleh pencarian dari sisi lain → Uji frontier aktif dari arah berlawanan terlebih dahulu.

• Mengekspansi sisi mana pun yang bernama front → satu sisi dapat meledak sementara sisi lainnya tetap kecil →

Tukar dan ekspansi frontier seluruh level yang lebih kecil.

• Mencampurkan jumlah edge dengan jumlah kata → contoh kasus mengembalikan empat, bukan lima → **Inisialisasi

penghitung urutan menjadi satu dan tambahkan kata penghubung saat edge pertemuan ditemukan.**

• Mengklaim bahwa BFS dua arah mengubah kompleksitas kasus terburuk → kamus adversarial yang padat mungkin

tetap mengekspos hampir setiap kata → Jelaskan manfaat faktor percabangan sebagai hal yang umum terjadi, bukan jaminan pasti.

• Menyebut mutasi di Python sebagai O(NL) → setiap kandidat menyalin atau melakukan hash pada L karakter → **Nyatakan

model operasi string dan gunakan O(NL²) untuk implementasi ini.**

• Menggunakan kembali bucket wildcard tanpa mengonsumsinya → list besar yang sama akan dipindai berulang kali →

Kosongkan setiap bucket pola yang telah diproses atau tandai sebagai telah dikonsumsi.

• Menggunakan satu set visited global tetapi mengizinkan ekspansi level parsial → urutan pertemuan dan perhitungan jarak

menjadi sulit dibuktikan → Majukan satu level frontier lengkap pada satu waktu.

• Mengutip pengalaman perusahaan yang dilaporkan sendiri sebagai atribusi terverifikasi → postingan publik bukanlah

catatan resmi pemberi kerja → Biarkan companyName bernilai null dan gunakan catatan tersebut hanya sebagai bukti publik saat ini.

Pertanyaan Lanjutan dan Cara Menanganinya

Pertanyaan Lanjutan 1: Bagaimana cara mengembalikan satu urutan terpendek yang sebenarnya?

Pertahankan peta simpul induk (parent map) untuk setiap arah. Ketika sebuah kandidat ditemukan, catat kata yang menghasilkannya. Pada edge pertemuan, telusuri parent map sisi awal kembali ke beginWord, balikkan prefiks tersebut, lalu telusuri parent map sisi akhir menuju endWord. Karena implementasi dapat menukar variabel frontier, simpan parent map berdasarkan arah semantik daripada berasumsi bahwa front saat ini selalu merupakan sisi awal. Penyimpanan simpul induk memerlukan O(N) referensi di luar string kamus.

Pertanyaan Lanjutan 2: Apa yang berubah untuk Word Ladder II, yang mengembalikan semua urutan terpendek?

Satu simpul induk per kata tidak cukup. BFS urutan level (level-order BFS) biasa sering kali lebih mudah dianalisis: kumpulkan setiap pendahulu yang mencapai suatu kata pada level minimumnya, dan hapus kata-kata yang baru ditemukan dari kamus global hanya setelah seluruh level selesai diproses. Hal itu memungkinkan beberapa simpul induk pada level yang sama tanpa membiarkan jalur yang lebih panjang menambahkan simpul induk nantinya. Berhenti setelah menyelesaikan level pertama yang mencapai endWord, lalu lakukan backtracking melalui DAG pendahulu tersebut. Ukuran output bisa bersifat eksponensial, sehingga kompleksitas harus mencakup total jumlah dan panjang urutan yang dikembalikan.

Pertanyaan Lanjutan 3: Kapan BFS satu arah biasa lebih disukai?

Gunakan BFS satu arah ketika ukuran kamus kecil, hanya satu titik ujung yang diketahui, graf berarah dan mencari tetangga mundur (reverse neighbors) membutuhkan biaya besar, atau kesederhanaan kode lebih diutamakan daripada memperkecil frontier. BFS satu arah memiliki lebih sedikit invarian dan membuat rekonstruksi simpul induk menjadi lebih mudah. Pendekatan ini mempertahankan generator tetangga yang sama dan batas O(NL²) yang sama untuk representasi Python ini.

Pertanyaan Lanjutan 4: Kapan sebaiknya Anda membuat bucket pola wildcard?

Bangun indeks ini ketika banyak kueri berbagi kamus statis yang sama, alfabet berukuran besar, atau menghasilkan setiap substitusi alfabet membuang-buang komputasi. Berikan versi pada indeks bersama dengan kamusnya, sertakan beginWord pola per kueri saat tidak diindeks, dan konsumsi setiap bucket paling banyak satu kali per pencarian. Konsekuensinya (trade-off) adalah waktu pra-pemrosesan, memori bucket, dan kebutuhan pembatalan/pembaruan indeks (invalidation) saat kata-kata berubah.

Pertanyaan Lanjutan 5: Bagaimana jika perubahan huruf yang berbeda memiliki biaya yang berbeda?

Graf menjadi berbobot, sehingga lapisan BFS tidak lagi merepresentasikan biaya minimum. Gunakan Dijkstra untuk biaya non-negatif, menghasilkan tetangga implisit yang sama tetapi mengurutkan frontier berdasarkan biaya yang terakumulasi. Heuristik admissible yang valid dapat mendukung penggunaan algoritma A*, tetapi jarak Hamming hanya bersifat admissible setelah diskalakan dengan batas bawah (lower bound) terbukti dari biaya perubahan karakter yang tersisa.

Pertanyaan Lanjutan 6: Bagaimana jika alfabet menggunakan Unicode atau kata-kata memiliki panjang yang berbeda?

Definisikan operasi yang legal terlebih dahulu. Code point Unicode dan kluster grafem adalah unit yang berbeda, dan operasi penyisipan (insert) atau penghapusan (delete) akan memunculkan edge yang mengubah panjang kata. Pembuatan substitusi langsung tidak lagi mencakup seluruh graf. Bergantung pada kontraknya, gunakan pencarian tetangga jarak-edit-satu terindeks, trie, atau bucket panjang-dan-pola, serta sertakan aturan normalisasi dalam operasi kesetaraan dan hashing.

Pertanyaan Lanjutan 7: Bagaimana cara membuktikan kondisi berhenti dua arah dalam wawancara?

Tetapkan kedalaman dari titik awalnya masing-masing untuk setiap frontier aktif. Algoritma memajukan tepat satu lapisan kedalaman lengkap per iterasi. Sebelum ekspansi, sequence_length adalah jumlah dua kedalaman frontier ditambah satu. Oleh karena itu, edge yang dihasilkan menuju frontier yang berlawanan membentuk jalur dengan sequence_length + 1 kata. Jika terdapat jalur yang lebih pendek, jalur tersebut pasti mengandung edge antara dua lapisan dengan jumlah kedalaman yang lebih kecil, dan lapisan-lapisan tersebut pasti sudah diekspansi dan terhubung sebelumnya. Hal ini bertentangan dengan fakta bahwa ini adalah pertemuan frontier yang pertama.

Pertanyaan Lanjutan 8: Bagaimana cara memvalidasi pencarian yang dioptimalkan di luar contoh kasus yang ada?

Untuk kamus acak berukuran kecil, hubungkan secara eksplisit setiap pasangan yang memiliki jarak Hamming satu dan jalankan BFS biasa sebagai oracle pembanding. Bandingkan jawabannya dengan BFS dua arah di ribuan kasus yang dibuat secara acak. Tambahkan invarian bahwa tidak ada frontier yang beririsan dengan unvisited, tidak ada kata yang ditemukan dua kali, dan setiap kata pada frontier berikutnya berbeda satu karakter dari kata pada frontier saat ini. Hal ini memisahkan bukti kebenaran algoritma dari sekadar beberapa output yang dipilih secara manual.