Tebakan Berujung Coding

Bismillah…

Fasilitas pergumulan bersama dunia maya (group) salah satu layanan obrolan ternama yang baru-baru ini melayangkan fitur terbarunya itu bermacam-macam karakteristiknya. Ada yang cukup aktif, ada yang damai seperti di pantai, ada pula yang terkubur sekian lamanya karena tidak pernah update. Bahkan tidak sedikit yang menjadi sampah. Ditinggalkan seluruh penghuninya kecuali satu, orang yang ga nyadar kalau semua anggota sudah “ke kiri”.

Tema pembahasannya pun beraneka ragam. Ada yang serius membahas politik. Ada yang fokus dakwah agama. Ada pula yang menjadi ajang CLBK reuni teman-teman seangkatan yang dulu duduk bersama di bangku sekolahan. Sehingga obrolan ngalor-ngidul pun sah-sah saja. Termasuk yang isinya berupa obrolan ga penting, meme, hoax, juga tebakan. Nah… ada satu tebakan yang entah kenapa tiba-tiba membuat saya sekonyong-konyong coder. Hasrat untuk coding itu senyana-nyana kembali ada, di kala iman di dada sedang tipis-tipisnya, setipis dompet di celana. **halah lebay Walaupun bukan coding serius ya. Hanya “iseng” saja, sekadar mengasah sedikit logika algoritma yang sudah lama jarang dipakai. Oh ya, bagi yang belum tau apa itu coding silakan googling ya. Dan maaf kalau bahasa yang ada di postingan kali ini mungkin akan terlalu teknis.

Well… check this out. Di bawah ini adalah tebakannya.

———————
Daftar kue atau jajanan tradisional. Ayo… dijawab sama-sama kalau sedang santai, sambil olah raga otak, dibayangkan kuenya & nostalgia makanan tradisional.

No.1 sudah diberi contoh, teruskan ya…

1. PTUU : PUTU
2. AEMP :
3. EELPT :
4. CCRUU :
5. AIJKW :
6. AADHJ :
7. ILOPS : 
8. IMSTU :
9. CEILN :
10. EEKPY :
11. EELMT :
12. ILTUW :
13. AGOTT :
14. ASTUW :
15. IKPSU :
16. EKKOTU :
17. AILMPU :
18. ANGIRN :
19. GIKNOW :
20. AEGKLP :
21. EKLNOP :
22. ABEIRS :
23. EELMPR :
24. GLNOORT :
25. AAGMNPY :
26. AIGMNNR  :
27. AAEEMMRR :
28. EEDDNNOO :
29. BILOORTU :
30. AEGKLMNP :
31. AGIKLNNT :
32. AAAGINRS :
33. AAEKLMTU :
34. EEIILLWW :
35. BEGGLMNO :
36. BDGNNOOR :
37. EKLMPRUUU :
38. AEGGGINNNR :
39. IINNRRTTUU :
40. ADGMMNSUOO :
41. ADLNOOORRY :
42. ACEGKNNOPU :
43. AEGKKKMNOU :
44. EDGIIKLNRTU : 
45. AADDGGLNRUU:
46. EEIIKKMPPRT :
47. AIRRSSUUWW :
48. EEGKMNOPRSU :
49. AEGGGINNOPRS :
50. EEGGIINNNNTT :
51. EGIIJLMMNNOP : 
52. ADEGKKNPRRUU :

———————

Ada yang aneh? Sama sekali tidak. Malahan seru sepertinya. Di kala teman-teman anggota group lainnya pada memikirkan jawabannya, dan mungkin sambil membayangkan rasanya, saya justru memikirkan, “sepertinya bisa dilakukan dengan bantuan algoritma deh“. Atau setidaknya pilihan-pilihan jawabannya bisa di-generate tanpa pusing menyusun huruf demi huruf menjadi nama-nama kue atau jajanan tradisional yang benar. Ya sudah, kita coba saja.

Masalah

Ya namanya coding, ga afdol kalau ga cari masalah. Karena tujuan utamanya adalah menyelesaikan masalah, atau justru memperumitnya. 😛 Ya gpp, namanya juga bagian dari belajar. Hasil itu nomer ke sekian, yang penting usaha dan niatnya.

Baik, kembali ke persoalan di atas. Kalau tidak keliru, persoalan di atas adalah masalah kombinasi karakter dalam setiap kata yang goal-nya adalah mencari kombinasi yang pas dan menjadi kata bermakna tertentu sesuai domain yang ditentukan. Dalam hal ini adalah nama-nama kue atau jajanan tradisional Indonesia. Oh ya, walaupun ada yang hasilnya berupa dua (2) kata, tapi tetap direpresentasikan sebagai satu (1) kata. Biar lebih sederhana permasalahannya.

Membentuk satu kata yang sesuai, artinya keterurutan setiap karakter menjadi penting. Harus urut. Harus sesuai dengan kata yang dimaksud. Sehingga akan lebih cocok jika didefinisikan sebagai persoalan Permutasi, bukan Kombinasi. Masih ingat kedua istilah ini? Saya juga lupa-lupa ingat. Padahal ini mah pelajaran SMP kalau tidak salah ya, atau SMA? Ntahlah, rumusnya kira-kira begini:

Variabel n menyatakan banyaknya elemen, sedangkan k adalah jumlah posisi yang disusun. Dalam kasus persoalan tebakan di atas, n dan k bernilai sama, karena jumlah karakternya tetap sama, hanya diacak saja posisinya. Sehingga untuk contoh yang empat (4) karakter, seperti soal nomor 2: AEPM = 4 karakter dan 4 posisi, banyaknya kemungkinan yang dapat disusun adalah sebesar 4! dibagi (4-4)! atau 4! dibagi 0!. Kita tahu 0! bernilai 1. Jadi, hasilnya sama saja dengan 4! = 24 kemungkinan. Apa saja? Inilah yang akan coba kita selesaikan dengan bantuan algoritma. Mengapa? Kalau cuman empat (4) karakter mungkin tidak terlalu banyak. Masih sanggup lah kita tuliskan satu-satu. Lha kalau lebih, contohnya seperti soal nomor 24: GLNOORT. Ada tujuh (7) karakter. Yang kalau dihitung akan menghasilkan 7! yaitu 5.040 kemungkinan. Banyak kan? Yang segini saja kita sudah mikir-mikir untuk menuliskannya satu-satu. Apalagi soal nomor terakhir yang terdiri atas 12 karakter. Kemungkinannya sebanyak 12! = 479.001.600. Empat ratusan JUTA lebih. Lumayan kan. Bisa gondrong. 😀

Algoritma Permutasi Karakter

Entah apa nama yang pas, saya menyebutnya algoritma permutasi karakter karena yang disusun dan dituliskan kombinasinya adalah rangkaian karakter-karakter dalam setiap kata. Untuk ini, kita perlu menuliskan dulu secara manual, urut-urutannya bagaimana dan dimulai dari mana. Contoh simulasinya seperti ini:

Kata = ABCD

Maka, kemungkinan-kemungkinannya adalah:

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

Perhatikan urut-urutannya yang menandakan ada pola pengurutan tertentu. Pola pengulangan yang sama untuk seluruh urutan elemen yang berlaku juga untuk setiap subset-nya, hingga menemui kondisi atau nilai basis tertentu. Jadi, untuk kasus kombinasi karakter ini, ambil salah satu karakter sebagai prefix, lalu gabungkan dengan sisanya, yang juga diberlakukan proses yang sama, hingga menemui kondisi karakter kosong atau habis. Mudeng kan ya? Ya pokoknya begitulah. Pola semacam ini sepertinya cocok kalau diterapkan mekanisme rekursif (recursion). Yaitu fungsi yang memanggil dirinya sendiri dengan parameter yang diset secara gradual hingga mencapai kondisi basis tertentu. Kalau masih bingung, ingat-ingat saja pelajaran matematika SMA yang terkait fungsi variabel. Kalau masih ingat, isinya itu yang terkait fungsi yang dituliskan dengan contoh format seperti ini: . Di situ fungsi f memanggil dirinya sendiri dengan parameter n-1 dan n-2. Ok ya? Ini sebenarnya saya sendiri juga bingung. Ga ngerti-ngerti amat. Apalagi disuruh menjelaskan. Makin mumet. Intinya begitu lah. Tidak perlu terlalu diambil pusing. Rumus faktorial yang merupakan bagian dari rumus permutasi yang saya tulis di atas juga sebenarnya berlaku perhitungan rekursif kok.

Nah, bagaimana menerapkannya ke dalam algoritma atau kode pemrograman? Dengan logika yang sama, pemrograman juga bisa digunakan untuk mekanisme rekursif. Definisikan fungsinya, lalu panggil di dalam fungsi itu sendiri dengan parameter yang diset secara gradual dan ada nilai basisnya. Seperti contoh fungsi berikut ini yang saya tulis menggunakan bahasa pemrograman Java.

public static void letterPermutation(String pref, String s) {
        int n = s.length();
        if (n == 0) {
		    System.out.println(pref);
        }
        else {
            for (int i = 0; i < n; i++) {
	            letterPermutation(pref+s.charAt(i), s.substring(0,i) + s.substring(i+1,n));
	        }
        }
}

Jika program dijalankan, maka akan tampil hasilnya seperti berikut.

Apakah sudah sesuai dengan yang kita jabarkan sebelumnya? Sepertinya sih begitu. Kita coba saja menggunakan salah satu soal tebakan di atas. Misal, kasus soal nomor 2 = AEMP.

Apakah ada yang familiar dengan salah satu hasilnya? Ya, benar, APEM. Kue rumahan yang enak. Biasanya dibuat kalau menjelang bulan puasa Ramadhan untuk dibagi-bagikan ke tetangga karib kerabat terdekat. Kalau istilah Jawanya, megengan.

Masalah Kedua

Menuliskan satu demi satu kombinasi secara otomatis sudah dapat dilakukan dengan bantuan algoritma di atas. Tinggal memilih salah satu kombinasi yang pas, yang membentuk nama kue atau jajanan tradisional. Masalahnya, kembali ke persoalan awal yang sempat saya singgung. Kalau cuman empat (4) karakter mungkin masih terjangkau. Tapi kalau sudah lebih dari itu tetap pusing juga, walaupun tinggal milih mana kombinasi karakter yang pas dengan nama kue atau jajanan tradisional. Kalau skalanya masih puluhan bahkan ratusan masih ok lah. Tapi kalau sudah ribuan atau jutaan, ini yang jadi sumber masalah baru.

Kita coba tes dengan contoh soal nomor 24 = GLNOORT.

Dihasilkan sebanyak 5040 kemungkinan kombinasi. Rasanya tidak efisien kalau disuruh mencari satu per satu. Metani siji-siji. Terlalu lama. Kemungkinan kelewat sangat besar.

Sepertinya tidak ada pilihan lain kecuali membiarkan program membantu mencarikannya. Bagaimana caranya? Ada dua pendekatan. Yang pertama dengan membuat kamus referensi sesuai dengan domain yang didefinisikan. Kalau kasus di atas berarti domainnya adalah semua nama-nama kue atau jajanan tradisional yang ada di Indonesia. Daftarkan pada satu tabel tertentu, lalu cek apakah setiap kombinasi karakter yang di-generate ada di dalam tabel tersebut. Jika ada maka itulah jawabannya. Jika tidak ada, maka tidak dituliskan dan lanjut ke kombinasi berikutnya. Sepertinya cukup sederhana. Tapi, ada masalah lagi. Kita tahu bahwa nama kue atau jajanan tradisional Indonesia itu banyak sekali. Setiap daerah bisa berbeda penamaannya. Belum lagi penulisannya yang kadang tidak standar. Dan rasanya belum ada acuan atau direktori lengkap tentang kue atau jajanan tradisional Indonesia ini. Barangkali ada yang sudah nemu? Kalau boleh di-share ya. Siapa tau dengan adanya direktori lengkap tentang kue atau jajanan tradisional ini bisa turut melestarikan khasanah kuliner tradisional Indonesia. Nah, kalau tebakan di atas diganti domainnya, misal dengan nama kota-kota besar di Indonesia, mungkin akan lebih mudah karena baik penulisan maupun database-nya sudah pasti ada dan lengkap.

Biar simpel, saya biasanya menuliskan kamus ini ke dalam struktur array. Lalu tambahkan fungsi pengecekan apakah kombinasi karakter yang sedang dicek ada di dalam array tersebut.

public static String[] kamus = new String[] {"PUTU", "APEM", "LEPET", "CUCUR", "WAJIK", "CELOROT", "JADAH", "RENGGINANG", "LOPIS", "ENTINGENTING", "RONDOROYAL", "MADUMONGSO", "TUMIS", "CENIL", "NAGASARI", "PEYEK", "LEMET", "DADARGULUNG", "TETEL", "TIWUL", "GATOT", "KUELUMPUR", "SAWUT", "PUKIS", "KUETOK", "LUMPIA", "WINGKO", "GAPLEK", "KLEPON", "SRABEI", "LEMPER", "NGLOROT", "AMPYANG", "MARNING", "AREMAREM", "ONDEONDE", "ROTIBOLU", "KEMPLANG", "KLANTING"};

public static boolean inKamus(String str) {
		boolean res = false;
		for (String s : kamus) {
			if (str.contains(s)) {
				res = true;
				break;
			} else {
				res = false;
			}
		}
		return res;
}

Jangan lupa tambahkan pengkondisian pada saat hendak memproses kombinasi karakter apakah ada di dalam kamus atau tidak.

public static void letterPermutation(String pref, String s) {
        int n = s.length();
        if (n == 0) {
            if (inKamus(pref)) {
		    System.out.println(pref);
            }
        }
        else {
            for (int i = 0; i < n; i++) {
	            letterPermutation(pref+s.charAt(i), s.substring(0,i) + s.substring(i+1,n));
	        }
        }
}

Kita coba lagi dengan salah satu contoh yang lain, misal soal nomor 32 = AAAGINRS.

Lho.. kok hasilnya ada enam (6) NAGASARI? Ingat, permutasi memperhatikan keterurutan elemen-elemennya. Itu berarti, NA₁GA₂SA₃RI dianggap tidak sama dengan NA₂GA₁SA₃RI. Untuk persoalan ini bisa diatasi dengan memasukkan semua kombinasi ke dalam struktur data yang disebut HashSet. Sehingga, isinya dijamin unik. Tapi konsekuensinya, ketika kita memasukkan elemen yang terlalu banyak, atau lebih besar dari jumlah alokasi memori yang diizinkan, maka program akan ngadat alias error atau overlimit pada saat dijalankan. Selain itu pemrosesan lebih lama pastinya. Saya sudah mencobanya. Ternyata untuk memproses permutasi 13 karakter yang menghasilkan sekitar enam (6) milyaran kombinasi, sudah overlimit. Padahal RAM komputer saya cukup besar, 12GB.

public static Set<String> hash = new HashSet<String>();

public static void letterPermutation(String pref, String s) {
        int n = s.length();
        if (n == 0) {
            if (inKamus(pref)) {
		    hash.add(pref);
            }
        }
        else {
            for (int i = 0; i < n; i++) {
	            letterPermutation(pref+s.charAt(i), s.substring(0,i) + s.substring(i+1,n));
	        }
        }
}

Dengan cara ini, untuk kasus contoh soal yang sama, akan dihasilkan satu (1) jawaban saja.

Ok. Selesai. Untuk pendekatan kedua tidak saya bahas karena saya juga ga yakin apakah bisa solutif atau tidak. “Sepertinya” bisa menggunakan pendekatan pola penulisan dari segi kata dalam bahasa. Misal, tidak akan mungkin jawabannya itu mengandung huruf A bersebelahan atau berjejeran sebanyak tiga (3) kali. Atau tidak akan mungkin jawaban yang dihasilkan itu ada empat (4) huruf konsonan yang bersebelahan. Tapi kan yang namanya kue atau jajanan tradisional kita itu kan biasanya diambil dari bahasa daerah. Sedangkan kita tahu, penulisan dalam bahasa daerah itu cukup unik. Bahasa Jawa saja contohnya, bisa ada tiga (3) huruf konsonan yang mengawali sebuah kata. Contohnya: NGLANGI. Dan masih banyak sekali contoh-contoh keunikan dalam mengenali pola bahasa. Mungkin orang-orang yang jauh lebih cerdas seperti Anda lah yang bisa men-define-nya. Da saya mah apa atuh.

Semoga bermanfaat. Matur nuwun.