bebek rewel

Permainan Edit Distance

Dalam bidang komputer-komputeran, edit distance berarti jumlah operasi minimum yang diperlukan untuk merubah suatu “kata” (String) untuk menjadi “kata” (String) yang lain.

Jenis operasi yang dimungkinkan adalah:
– Insert: memasukkan suatu huruf
– Delete: menghilangkan suatu huruf
– Change: menukar suatu huruf dengan huruf lain

Ambillah contoh kata “Doraemon”:
– Edit distance antara “Doraemon” dan “Doremon” adalah 1 (Dengan menghilangkan huruf “a”).
– Edit distance antara “Doraemon” dan “Dorayaki” adalah 4 (Dengan mengganti “e” ke “y”, “m” ke “a, “o” ke “k” dan “n” ke “i”)
– Edit distance antara “Doraemon dan “Dorami” adalah 3 (Dengan menghilangkan “e” dan “n”, lalu mengganti huruf “o” kedua dengan “i”)

Ketika bebek menjalani tahap awal menuju proses hibernasi (baca: bobo malam dengan guling tersayang) beberapa hari yang lalu, tiba-tiba bebek terpikirkan suatu permainan kata sederhana dengan menggunakan prinsip edit distance. Entah apakah memang permainan seperti ini sudah lazim dimainkan oleh makhluk hidup lainnya (yang lagi pengangguran) atau belum.

Ide pertama adalah sebagai berikut:
– Pilih satu kata untuk menjadi kata dasar (Misalnya, kata “alam”)
– Pilih kata kedua untuk menjadi kata tujuan (Misalnya, kata “kalem”)
– Ubahlah kata dasar (“alam”) menjadi kata tujuan (“kalem”) dengan syarat setiap perubahan yang dikenakan kepada kata dasar dan turunannya hanya berjarak 1 edit distance dari kata sebelumnya
– Kata-kata perantara yang terbentuk diantara kata dasar dan kata tujuan juga harus merupakan kata yang mempunyai arti
– Untuk mempermudah/mempersulit (coret yang tidak perlu) permainan, bisa menggunakan alat bantu berupa KBBI (Kamus Besar Bahasa Indonesia). Cepat atau lambat dikau akan dibuat cengar-cengir campur geleng-geleng kepala ketika mendapati bahwa kata-kata yang muncul secara acak di kepala dikau ternyata memang terdaftar di kamus dengan arti yang lucu-lucu
– Harap dicatat bahwa ada kemungkinan bahwa permainan ini mustahil untuk diselesaikan jika kata tujuan memang tidak bisa dicapai
– Permainan dinilai dari sedikitnya “mata rantai” yang terbentuk. 1 nilai untuk setiap “mata rantai” kata yang terbentuk
– Tujuan permainan adalah untuk mencapai nilai sekecil-kecilnya

Salah satu penyelesaian dari soal “alam” ke “kalem” adalah sebagai berikut (Arti kata diambil secara acak dari beberapa arti yang tertulis di KBBI edisi keempat, 2008):
1. _Alam: Lingkungan kehidupan
2. Kalam: Kemaluan (laki-laki) (Baru tau daku ada kosa kata “kalam” untuk “benda” yang satu itu! 0_o”” Selama ini taunya cuma ada mantan Presiden India yang namanya Abdul Kalam)
3. Kalem: Keadaan tidak tergesa-gesa; tenang; santai
Dari penyelesaian di atas, kata perantaranya adalah “kalam”. Perhatikan juga kalau masing-masing langkah mempunyai 1 edit distance terhadap kata sebelumnya.

Ide kedua adalah sebagai berikut:
– Pilih satu kata untuk menjadi kata dasar (Misalnya, kata “alam”)
– Tentukan jumlah jatah edit distance maksimum (Misalnya, 10)
– Ubahlah kata dasar (“alam”) ke kata apapun yang ada di pikiran dikau
– Kurangi jatah edit distance untuk setiap edit distance yang ada antara satu kata dengan kata selanjutnya (Misalnya: “alam” ke “kalam” akan menghabiskan 1 jatah edit distance, sementara “alam” ke “alis” akan menghabiskan 2 jatah edit distance)
– Teruskan sampai jatah edit distancenya habis (atau udah mentok, gak kepikiran lagi kata baru yang bisa dibentuk dengan jatah edit distance yang tersisa)
– Dilarang menggunakan kata yang sama lebih dari satu kali (Misalnya: dari “alam” ke “alas” ke “alis” lalu kembali ke “alas”)
– Permainan dinilai dari banyaknya “mata rantai” kata yang terbentuk. 1 nilai untuk setiap “mata rantai” kata yang terbentuk (Jika jumlah jatah edit distance maksimum adalah 10, maka nilai maksimum adalah 10 => dengan membentuk 10 kata yang berbeda, masing-masing berjarak 1 edit distance terhadap kata sebelumnya)
– Tujuan permainan adalah untuk mencapai nilai seBESAR-BESARnya

Ide ketiga adalah sebagai berikut:
– Pilih satu kata untuk menjadi kata dasar (Misalnya, kata “alam”)
– Tentukan jumlah edit distance maksimum yang diperbolehkan untuk setiap langkah (Misalnya, maksimum 2 edit distance untuk setiap langkah)
– Tentukan lama permainan (Misalnya: 2 menit)
– Ubahlah kata dasar (“alam”) ke kata apapun yang ada di pikiran dikau
– Teruskan sampai kehabisan ide atau sampai waktu permainan habis
– Permainan dinilai dari banyaknya “mata rantai” kata yang terbentuk. 1 nilai untuk setiap “mata rantai” kata yang terbentuk
– Tujuan permainan adalah untuk mencapai nilai seBESAR-BESARnya

Kalo dipikir-pikir, maenan gak jelas kaya gini asyiknya dimaenin waktu jaman sekolah, waktu pelajaran kosong (atau di tengah pelajaran yang membosankan). Kalo ditegor guru, kan tinggal pake alesan sedang melatih perbendaharaan kata Bahasa Indonesia. Sekalian variasi permainan juga (daripada terus-terusan maen suit atau do-mi-ka-do)

Sebagai penutup postingan gak jelas ini, mari kita bermain “Permainan Edit Distance” aturan pertama dengan kata dasar “Mulai” dan kata tujuan “Selesai”  (Arti kata diambil secara acak dari beberapa arti yang tertulis di KBBI edisi keempat, 2008):

1. Mulai: Mengawali berbuat (bertindak, melakukan, dsb)

2. Gulai: Sayur berkuah santan dan diberi kunyit serta bumbu khusus (biasanya dicampur dengan ikan, daging kambing, daging sapi, dsb)

3. Gula: Bahan pemanis biasanya berbentuk kristal (butir-butir kecil) yang dibuat dari air tebu, aren (enau), atau nyiur

4. Gila: Sakit jiwa (sarafnya terganggu atau pikirannya tidak normal)

5. Gilas: Tindih dengan benda bulat

6. Kilas: Kilat

7. Kelas: Tingkat

8. Kelasa: Bonggol di tengkuk atau punggung binatang (seperti unta, lembu)

9. Selasa: Hari ke-3 dalam jangka waktu satu minggu

10. Selesa: Luas (tidak sempit, tidak sesak)

11. Selesai: Habis, tamat, berakhir

Dengan demikian, selesailah tulisan tentang permainan gak jelas ini.
—————————————————————-

Catatan: Pada waktu bebek menghadiri salah satu acara training di tempat kerja, para peserta diajak untuk memainkan permainan kata yang sejenis dengan ide permainan yang bebek jabarkan di atas.

Permainannya adalah untuk mengubah kata “POOR” menjadi “GOLD”. Hanya operasi “Change” yang diperbolehkan dengan jarak edit distance = 1.

Solusi yang dihasilkan oleh peserta training adalah sebagai berikut:
“POOR” => “MOOR” => “MOOD” => “MOLD” => “GOLD”

3 Comments

Comments RSS TrackBack Identifier URI

Leave a comment