ICPC 4 Tahun

Setelah menceritakan pengalaman menuju OSN/IOI, kini saya akan menceritakan pengalaman menuju ICPC World Final. Tujuannya adalah berbagi pengalaman. Berhubung rentang maksimal untuk karir ICPC adalah 4 tahun, yang lebih lama dari 2-3 tahun pada OSN/IOI, memutuskan untuk menginvestasikan sebagian dari 4 tahun kuliah ke ICPC merupakan komitmen yang panjang.

---

Partisipasi Pertama

Setelah masuk Fasilkom UI dan mengikuti berbagai orientasi, saya direkrut untuk ikut ICPC oleh Felik. Anggota tim satunya lagi adalah Rasmunandar Rustam, sehingga tim kami sepenuhnya adalah TOKI 2011. Nama tim yang disepakati adalah Vidina, dari Felik yang artinya "masa depan".

Sebenarnya saya hanya tahu kalau ICPC adalah kontes pemrograman seperti IOI, dengan ciri:

• Partisipasi tim
• Penilaian jawaban hanya ada benar atau salah

... dan saya tidak tahu bagaimana aturannya kualifikasinya bekerja. Apakah dipilih N tim terbaik di suatu negara? Atau suatu region? Bagaimana pembagian regionalnya bekerja? Berhubung baru mulai kuliah dan banyak aktivitas, saya tidak mencari tahu jawabannya (atau mungkin karena saya lupa).

Felik kemudian mengurus administrasi tim kami. Kami juga berkenalan dengan Pak Denny, yang merupakan coach untuk tim UI untuk urusan ICPC. Saya mempelajari bahwa biasanya UI mengirim sekitar 3 tim ke suatu regional di Asia. Kalau pada tahun itu diselenggarakan ICPC regional Jakarta juga, maka UI dapat mengirim segerombolan tim karena biaya yang jauh lebih murah. Sebagai catatan, ICPC hanya ada pada semester ganjil.

Berhubung tahun 2011 tidak ada ICPC regional Jakarta, berarti tahun ini hanya 3 tim yang akan ikut regional. Penentuan 3 tim ini diputuskan dengan INC (Indonesia National Contest) yang diselenggarakan Binus. Tim Vidina berhasil mengamankan posisi di INC sebagai salah satu dari 3 tim terbaik dari UI, sehingga kami akan dikirim ke ICPC regional.

Ternyata regional yang dipilih adalah Kuala Lumpur. Kami berangkat ke Malaysia berasama dengan Pak Denny dan 1 tim UI lainnya. Kontesnya akan diselenggarakan di IIUM (International Islamic University Malaysia).

Selama perjalanan, saya belajar dari Pak Denny kalau sekitar 3 tim terbaik di suatu regional akan terkualifikasi ke ICPC World Final (biasa disebut "WF" saja). Aturan sebenarnya lebih rumit, yang melibatkan regional quota, suatu rumus yang memusingkan, pertimbangan khusus, dan sebagainya. Rasanya yang penting bertanding sebaik mungkin, lalu serahkan WF atau tidak ke tangan panitia.

Sejujurnya saya tidak banyak persiapan untuk ICPC ini. Saya juga tak tahu apa harapan partisipasi ini. Rasanya untuk menduduki 3 besar tidaklah mungkin. Namun karena sudah jauh-jauh ke Malaysia, saya tidak pikir panjang dan berkompetisi sebaik mungkin.

Hasil kompetisinya tidak baik. Peringkat akhir Vidina adalah 25-an, yang sangatlah jauh dari 3 besar.

Rasanya tidak enak telah menghabiskan uang fakultas, lalu tidak berkompetisi dengan baik. Kami pulang ke Indonesia sambil memikirkan solusi soal kompetisinya.

Pada semester kedua, Rasmunandar mundur dari Vidina karena ingin fokus ke pemrograman yang lebih aplikatif (seperti website atau aplikasi HP). Felik kemudian merekrut Cakra, yang tahun depan akan masuk UI sebagai angkatan 2012, dan nama timnya menjadi Vidina 2.0.

---

Tahun Kedua yang Suram

Masuk semester ketiga, tim kami kembali mengikuti INC dan masuk ke dalam 3 tim terbaik UI. Tahun ini terdapat ICPC regional Jakarta, sehingga kami akan berpartisipasi di 2 kontes. Ternyata selain Jakarta, kami akan dikirim ke Hanoi. Sebagai catatan, kontes di Hanoi jauh lebih awal daripada Jakarta.

Hasil regional di Hanoi suram, lagi-lagi kami peringkat 25-an. Namun kali ini saya cukup sedih karena tidak ada kemajuan jika dibandingkan tahun sebelumnya, padahal sudah berlatih selama semester genap. Selain merasa bersalah kepada Pak Denny dan fakultas karena tidak memberikan hasil yang baik, saya mulai merasa untuk mendapat peringkat 3 besar tidaklah mungkin. Saingan dari Taiwan, Cina, Hongkong, Vietnam, atau Singapura (yang isinya teman-teman TOKI juga) terlalu tangguh untuk dikalahkan. Rasa suram ini membuat saya kehilangan semangat dan tidak ikut jalan-jalan ke Ha Long Bay. Setidaknya, pengalaman berkunjung Vietnam cukup menarik dan saya membeli caping khas sana.

Caping "Pandaren" (foto oleh Felik)

Kontes selanjutnya adalah INC 2012, yang mana Cakra tidak bisa ikut karena ada acara orientasi. Jadinya hanya saya dan Felik yang harus nge-tank dan carry. Namun secara mengejutkan, performa kami sangat baik dan memperoleh peringkat ke-3. Hasil yang lebih baik mungkin bisa dicapai kalau kami ber-3. Berkat hasil yang baik ini, moral berperang saya kembali bangkit, dan siap untuk menghadapi regional Jakarta.

Tim UI berbondong-bondong berangkat ke Binus dengan bis kuning untuk regional Jakarta. Ini kedua kalinya saya ke Binus, setelah BNPC HS 2011 pada Pelatnas 1 yang lalu. Berkat moral yang positif, kami bertanding dengan baik dan berhasil duduk di peringkat 10. Ada pencapaian pertama yang diraih, yaitu first solver untuk suatu soal dan kami mendapatkan balon bintang.

Foto dari Felik

Lebih jauh lagi, ternyata kami mendapat penghargaan tim lokal (Indonesia) terbaik ke-3 dan mendapat plakat. Tim lokal terbaik pertama dan ke-2 adalah "Dongskar Pedongi" (timnya Irvan Jahja) dan "+1 Saklar Lhompat" (timnya Ashar). Penghargaan ini juga tiba dengan hadiah berupa hard disk eksternal. Kebetulan saat itu saya perlu format komputer dan butuh media penyimpanan data yang besar, jadilah pucuk dicinta ulam pun tiba.

Walaupun hasil ICPC di Hanoi suram, tapi hasil di Jakarta memberikan harapan. Masih ada waktu 2 tahun untuk berlatih untuk mencapai WF!

Graf Berarah dengan Setiap Node Memiliki Tepat Satu Keluaran

Graf merupakan konsep yang umum ditemui pada kompetisi pemrograman. Kali ini kita akan membahas graf dengan sifat yang menarik, yaitu setiap node-nya memiliki tepat satu keluaran (memiliki tepat 1 outdegree).

Kalau digambar, grafnya terlihat seperti ini:

---

Sifat 1: Dijamin terdapat cycle

Tidak mungkin kita dapat membentuk grafnya tanpa cycle. Jika terdapat N node, maka usaha terbaik yang dapat kita lakukan untuk menghindari cycle adalah membentuk struktur seperti rantai: setiap node menunjuk ke node lainnya. Sayangnya ujung terakhir dari struktur rantai ini harus menunjuk ke suatu node lainnya, yang mana pilihannya adalah node-node sebelumnya. Hal ini menjamin selalu terbentuk setidaknya sebuah cycle.

Petunjuk Coding: Binary Search

Konsep binary search sederhana; pada data terurut, periksa nilai di tengah, lalu putuskan apakah pencarian dilanjutkan di setengah awal atau akhir. Kenyataannya, implementasinya tidak semudah itu. Tulisan ini akan membahas implementasi berbagai macam binary search.

---

Jenis 1: data diskret

Biasanya kita diberikan sebuah array terurut berisi N nilai, lalu diminta mencari index untuk suatu nilai v.

Implementasi yang saya sukai adalah secara iteratif, menggunakan while. Representasikan rentang pencarian dengan dua variabel, sebut saja l dan r. Selama rentang pencarian tidak kosong (yaitu l <= r), periksa nilai di tengah. Kalau nilai di tengah sama dengan v, hentikan pencarian. Kalau lebih kecil, geser batas bawah rentang pencarian menjadi 1 indeks setelah bagian tengahnya. Kalau lebih besar, geser batas atas rentang pencarian menjadi 1 indeks sebelum bagian tengah.

Berikut implementasi lengkapnya. Kalau sampai keluar dari while dan variable ans masih bernilai -1, artinya nilai v tidak ditemukan.

Variasi lain yang memusingkan adalah kalau v tidak ditemukan, cari nilai terdekat yang lebih besar.
Solusinya sama seperti sebelumnya, kecuali ketika nilai di tengah mungkin menjadi jawaban, catat indeksnya. Setelah rentang pencarian habis, dijamin indeks terakhir yang dicatat menyimpan jawaban yang diinginkan. Berikut implementasinya:

Apabila nilai v tidak ditemukan dan yang diinginkan adalah nilai terdekat yang lebih kecil, cukup ubah kondisinya:

Kedua variasi ini adalah binary search yang akan sering Anda temukan pada kompetisi. Pastikan Anda hafal kapan jawaban perlu dicatat.

---

Jenis 2: Data Kontinu

Biasanya kita tidak diberikan array berisi data, melainkan kita diminta menebak suatu bilangan riil yang memenuhi suatu kondisi. Anggap saja kita memiliki fungsi f, yang menerima bilangan riil antara 0 sampai 1 dan mengembalikan true jika dan hanya jika kondisi terpenuhi. Lalu anggap fungsi f ini memiliki sifat khusus, yaitu terdapat suatu bilangan v, sehingga setiap x yang memenuhi x≥v pasti memiliki nilai f(x) bernilai true.

Sama seperti sebelumnya, buat dua variabel yang merepresentasikan rentang pencarian.
Lalu terdapat setidaknya dua pandangan tentang implementasinya, yaitu menggunakan while sampai rentang pencarian hampir tidak berubah lagi seperti berikut:

Pada implementasi di atas, dipilih nilai 10^-8 sebagai nilai toleransi. Kalau beda rentang pencarian sudah lebih kecil dari nilai tersebut, pencarian dianggap selesai dan l dianggap sebagai jawabannya.

Pandangan implementasi lainnya adalah dengan menggunakan for sebanyak K kali. Nilai K biasanya 100, yang mana sudah sangat akurat:

Secara pribadi saya lebih menyukai strategi yang menggunakan for. Alasannya adalah dijamin setelah 100 langkah, program akan berhenti; sementara untuk strategi dengan while, tidak ada jaminan kapan program berhenti. Saya selalu menggunakan strategi dengan for dan tidak pernah ada masalah.

---

Penutup

Sekian petunjuk untuk mengimplementasikan binary search. Semoga bermanfaat!

Penulisan Buku Pemrograman Kompetitif Dasar

Libur akhir tahun baru saja lewat. Saya jadi ingat masa-masa liburan akhir tahun 2017 yang dihabiskan untuk menulis buku Pemrograman Kompetitif Dasar (PKD). Proses penulisan buku itu cukup lama. Banyak yang sebelumnya tidak diketahui jadi harus diketahui. Saya akan membagikan pengalaman sepanjang penulisan buku PKD.

Awal Mula

Pada tahun 2014, saya diminta Ashar untuk menuliskan materi pemrograman dasar Pascal untuk dimuat ke TLX Training Gate (seterusnya akan saya sebut TLX-TG). Lalu tahun 2016, ada inisiatif untuk memperluas cakupan materi TLX-TG, sehingga dibuatlah materi pemrograman kompetitif dasar yang isinya lebih ke algoritma-algoritma. Seluruh materi ini ditulis dengan format slide presentasi (seperti materi perkuliahan). Argumennya adalah slide presentasi lebih ringkas daripada penjelasan berupa paragraf, dan dapat memuat gambar yang dianimasikan. Animasi yang saya maksud sebenarnya sesederhana seperti slide 1 memuat array, lalu slide kedua memuat array yang elemennya ditukar; misalnya digunakan untuk mengajarkan pengurutan.

Setelah satu tahun berlalu, Aji tiba-tiba mengajak saya untuk menganalisis kemajuan pemrograman kompetitif di Indonesia. Saya pun terpikir, apakah selama ini materi yang ditulis benar-benar digunakan dan bermanfaat bagi pelajar Indonesia?

Sepanjang saya menulis materi pemrograman kompetitif dasar, sebenarnya ada keraguan apakah slide media yang tepat. Slide mungkin unggul kalau digunakan oleh pengajar, seperti dosen atau guru. Namun kali ini konteksnya adalah pembelajaran mandiri. Saya pribadi lebih suka belajar hal baru dengan membaca tulisan yang penjelasannya lengkap, seperti buku atau artikel.

Analisis tahun 2017 itu dimulai dengan memberikan survey kepada anggota grup facebook "Olimpiade Informatika Indonesia". Saya menggunakan kesempatan ini untuk mengetahui apa pendapat peserta didik tentang media pembelajaran TLX-TG. Salah satu pertanyaan survey tersebut adalah mengurutkan preferensi terhadap empat media pembelajaran:

1. Slide presentasi
2. Tulisan artikel/blog
3. Buku
4. Video pengajaran

Ternyata keraguan saya terbukti benar. Yang lebih mengejutkan adalah slide presentasi berada di peringkat paling bawah. Media pembelajaran yang lebih diminati adalah video pengajaran, disusul dengan buku.

Memproduksi video pengajaran jelaslah sulit. Diperlukan peralatan untuk merekam video, microphone yang bagus untuk kualitas suara yang bagus, kemampuan mengedit, dan "sosok berkharisma" yang melakukan pengajaran. Lagipula, video pengajaran yang diakses lewat internet tidak menjamin kemudahan akses. Kualitas internet di Indonesia sangat beragam, dan saya sendiri kadang kesulitan untuk nonton video youtube. Singat cerita, video pengajaran tidak dapat dikejar.

Pilihan selanjutnya adalah buku. Mungkin buku adalah media pembelajaran yang paling seimbang dari keempat yang dicalonkan, karena:

• Penjelasan dapat diberikan secara lengkap, tanpa perlu khawatir halaman menjadi penuh tulisan. Ini perlu dihindari pada penulisan slide.
• Pembelajarannya sistematis, tidak lompat-lompat atau tercecer seperti tulisan artikel/blog pada umumnya.
• Lebih mudah diakses daripada video pengajaran.
• Dapat dicetak, lalu dikirimkan ke segala pelosok di Indonesia.

Yah, memang buku memiliki kekurangannya tersendiri. Anak SMP/SMA yang diminta membaca buku pemrograman atau algoritma penuh tulisan mungkin akan terintimidasi. Buku pelajaran sekolah biasanya memiliki gambar dan berwarna. Bahkan, kadang gambarnya tidak penting dan hanya berperan sebagai dekorasi, misalnya pelajaran ekonomi tentang barter lalu diberikan gambar orang menukar beras dengan kambing.

Selama diskusi dengan teman-teman TOKI berlangsung, keputusannya lebih condong ke penulisan buku. Tujuannya adalah membuat buku yang lengkap, sistematis, dan gratis untuk mempermudah pembelajaran mandiri. Namun saya ragu, dan mempertanyakan apa gunanya buku ini kalau sudah ada buku Competitive Programming 1 (CP1), yang sudah digratiskan oleh Steven & Felix Halim? Argumen yang diberikan adalah CP1 menggunakan Bahasa Inggris, dan tidak semua siswa-siswi sudah lancar berbahasa Inggris. Setelah diyakinkan masih ada niche, akhirnya diputuskanlah untuk menulis buku.

Rencananya adalah membukukan slide materi, ditambah dengan beberapa materi baru. Saya dan Aji berkomitmen menjadi penulis utama buku ini, dan berencana menyelesaikannya sebelum PJJ pra-OSN 2018.

Mulai Menulis Buku

Penulisan dimulai dengan mencari template buku. Idealnya penulisan akan dilakukan dengan Latex, karena gratis dan mudah diintegrasikan dengan version control seperti Git. Aji menemukan template buku yang sekiranya cocok, yaitu tidak terlalu ilmiah dan tidak terlalu santai. Diputuskan untuk sementara menggunakan template buku tersebut.

Selanjutnya dilakukan transformasi slide presentasi ke bentuk buku, atau lebih tepatnya "transpile" kode latex beamer slide ke format latex buku. Aji menulis script untuk melakukannya, dan jadilah buku sangat mentah versi 0.

Tugas selanjutnya adalah mengubah format poin-poin dalam slide menjadi narasi. Aji mengusulkan untuk merekrut sukarelawan untuk membantu proses ini. Jadinya dilaksanakan "hackathon" di kantor Sirclo atas bantuan Brian dan Ashar. Secara mengejutkan cukup banyak yang berminat untuk membantu. Kini bukunya lebih berwujud buku daripada sebelumnya, walaupun gaya penulisan setiap bab gado-gado karena dikerjakan oleh orang yang berbeda. Orang-orang yang membantu hackathon ini namanya dicantumkan sebagai kontributor buku.

Peserta Hackathon PKD

Memasuki libur hari natal dan tahun baru, kantor saya libur selama 2 minggu. Saya menghabiskan waktu bersama Aji untuk merapikan dan menyeragamkan penulisan setiap bab. Setiap bab diperiksa oleh kami, dari awal sampai akhir. Setelah itu bukunya sudah bisa disebut dengan "versi 0.0". Sebetulnya sempat ada perdebatan apakah bukunya mau diberi versi dalam bentuk <major>.<minor>.<patch> yang klasik, atau <major>.<patch> saja. Diputuskan untuk menggunakan <major>.<patch> saja karena tidak jelas kapan minor atau patch bertambah.

Pemolesan Konten

Tahap selanjutnya adalah review. Ashar dan Aji mengusulkan untuk merekrut Pak Suhendry. Untungnya Pak Suhendry bersedia membantu.

Awalnya saya percaya diri kalau bukunya ditulis dengan baik. Ternyata pemikiran itu terbukti salah ketika ditemukan kekeliruan di sana sini. Saya belajar kalau pihak ketiga dibutuhkan untuk memberikan masukan, sehingga hal-hal yang tidak kita pikirkan bisa diketahui.

Pak Suhendry memberikan review yang SANGAT BERMANFAAT. Banyak kekeliruan yang ditemukan, dan hal-hal kecil yang terlewatkan. Saya ingat saran yang paling bermanfaat adalah memperbaiki sistematika penulisan. Misalnya pembahasan perlu dimulai dari A dulu, lalu dilanjutkan ke B, dan seterusnya.

Dekorasi dan Estetika

Setelah kontennya memenuhi standar yang kita tetapkan, saya dan Aji mulai menggarap buku ini dari segi tampilan. Kami merekrut Ali untuk memberi masukan tentang font, skema warna, gambar cover, dan sebagainya. Setelah konsepnya jelas, saya menulis ulang template Latex bukunya sehingga memenuhi konsep yang kita tetapkan.

Bagian yang menyusahkan di sini adalah menulis template Latex itu tidak semudah menulis HTML + CSS (walaupun CSS sendiri pun tidak mudah). Banyak kode-kode misterius, konfigurasi library yang saling bertentangan, dan sebagainya. Setelah berdarah-darah, akhirnya selesai juga.

Suatu buku kurang sempurna apabila tidak ada kata pengantar dan basa-basinya. Jadi kami juga menambahkan kata pengantar, berikut yang lebih pentingnya, yaitu ucapan terima kasih kepada kontributor.

Publikasi

Kini buku sudah sangat berbentuk buku, tinggal dipublikasikan saja. Kami coba bertanya kepada alumni TOKI yang pernah menulis buku, dan ternyata kalau bukunya mau dijual di toko, tidak mungkin bisa non-profit. Toko buku pasti mau keuntungan.

Kalau pihak kita yang mengelola percetakannya, rasanya repot. Kita seakan-akan menjadi penjual toko online. Jadinya kami mulai dengan mempublikasikan dalam bentuk e-book.

Pelajaran

1. Menulis buku itu melelahkan! Butuh kesabaran, ketangguhan, dan niat untuk menghabiskan berbulan-bulan untuk menyelesaikannya. Untungnya ada teman-teman TOKI dan Aji yang memotivasi.
2. Harus mampu menulis Bahasa Indonesia dengan benar. Walaupun kita menggunakan bahasa itu setiap hari, penulisannya tidak semudah berbicara. Pertanyaan yang sering muncul kira-kira seperti "apakah ada spasi sebelum 'pun'?".
3. Walaupun awalnya berdarah-darah, penggunaan Latex sangat membantu. Kita dapat menulis buku dengan editor apapun, lalu dimuat di version control dengan mudah. Kalau disuruh menulis buku lagi, saya pasti pakai Latex.  

Demikianlah pengalaman penulisan buku ini. Apa yang akan terjadi dengan buku ini pada masa depan? Apakah ada edisi kedua? Atau apakah akan ada PKL (Penjual Kaki Lima Pemrograman Kompetitif Lanjut)? Mari anggap saja itu pertanyaan untuk hari esok.

Seperti biasa, saya harap buku ini menjadi pedoman belajar pemrograman bagi kalian yang baru memulai. Semoga bermanfaat.

Video Seri Persiapan OSN Informatika

Sekitar 2 tahun yang lalu, saya dan Aji melakukan survey di grup Facebook Olimpiade Informatika Indonesia. Tujuan surveynya adalah mengukur apakah Training Gate TLX efektif dalam memberi pelajaran, dan juga media apa yang diharapkan ada untuk membantu pembelajaran. Hasilnya, media yang paling diminati adalah video pembelajaran, diikuti dengan buku, dan lain-lain. Berhubung tenaga kerja kami terbatas, maka dibuatlah buku terlebih dahulu.

Entah dari mana datangnya, tiba-tiba tim konten TOKI mendapatkan "hibah" tenaga kerja. Ali yang baru selesai studi mau membantu merekam dan mengedit video, sementara Aji dan Felix Jingga menyiapkan materinya. Pada akhirnya, mereka ditambah Andreas sukses merekam video pembelajaran yang dipublikasikan lewat youtube.

Pembelajaran melalui video tentunya sangat membantu, terutama mereka yang lebih cepat belajar dengan cara mendengarkan daripada membaca (cara belajar visual vs auditori). Saya menyarankan kalian yang ingin belajar OSN informatika untuk mencoba menonton videonya.

Hingga tulisan ini dibuat, sudah ada 16 video. Daftar videonya bisa anda cek di sini: https://www.youtube.com/watch?v=dnpkD_p12WM&list=PL42SmLrOBFuRoDXatrv1PajCbt2ejb2Gn.

Kini bertambahlah sumber pembelajaran kalian. Mulai dari forum, website, buku, sampai video. Yang diperlukan hanyalah motivasi dan semangat dari kalian. Jadi, selamat belajar!

Terasi (bagian 4): Migrasi ke C++

Di tengah-tengah pengerjaan front end, tiba-tiba saya ada mendapatkan komitmen pekerjaan baru yang membuat proyek Terasi perlu ditunda dulu. Jadi sekitar bulan Juni 2016, saya berhenti untuk sementara.

---

Lanjutan Pengerjaan

Kini sudah bulan Juni 2017. Sekitar setahun setelah Terasi ditinggal.

Saya sudah beres urusan pekerjaan lainnya dan dapat kembali melanjutkan proyek Terasi. Sebelum langsung melanjutkan, saya periksa dulu apakah tiba-tiba sudah muncul aplikasi yang serupa.

Dari teman, saya tahu kalau Google Maps sudah mengintegrasikan jalur Transjakarta. Jadi saya lihat-lihat. Ternyata implementasinya masih sangat kasar. Jadi ketibaan bus di setiap halte di-hardcode "setiap 15 menit". Ditulisnya data didapatkan dari Transportasi Jakarta. Mungkin karena mereka belum memiliki data yang akurat, jadinya digunakan estimasi kasar 15 menit.

Dari teman lagi, ada sebuah aplikasi yang bernama "Trafi". Saya periksa, dan aplikasinya bagus. Saat itu kita bisa melihat posisi bus secara live. Sepertinya API yang digunakan sama dengan yang saya pakai. Melihat estimasi waktu tunggu, lagi-lagi waktunya di-hardcode per halte.

Kesimpulannya, saya bisa lanjut mengerjakan Terasi.

Oke lalu saya lihat data yang sudah dipanen. Secara mengejutkan ukuran data 1 hari menjadi besar. Setelah dibandingkan dengan data tahun lalu, ini yang saya lihat:

gyosh@gyosh ~/workspace/terasi/data $ ls -l --block-size=M | grep 01-01.tar.gz
-rw-r--r-- 1 gyosh gyosh 12M Jan  1  2016 2016-01-01.tar.gz
-rw-r--r-- 1 gyosh gyosh 25M Mar 18  2017 2017-01-01.tar.gz

Perhatikan kolom ke-5 (1 based). Terlihat bahwa dulunya 12 MB, kini 25 MB. Jadi ukurannya menjadi 2 kali lebih besar!
Pastinya ini hal yang baik untuk Jakarta, karena banyaknya bus bertambah. Lalu tiba-tiba terpikir, atau jangan-jangan ada koridor baru?

Jadi saya periksa peta Transjakarta terbaru, dan ternyata benar. Muncul lebih banyak subkoridor yang namanya berupa angka + huruf, seperti 5A, 5B, 5C, 5D, 5E. Koridor seperti itu biasanya menggunakan sebagian besar koridor 5, tetapi halte awal dan akhirnya mungkin saja berbeda. Selain itu, ada juga koridor baru dengan kode huruf + angka, seperti S11, S21, T11, dan sebagainya. Koridor itu sepertinya mencapai luar Jakarta, seperti daerah "-bodetabek".

Selanjutnya, saya coba menonton rekam jejak terbaru di aplikasi visualisasi saya. Ternyata data bus baru itu tidak terekam. Bus-busnya masih menggunakan informasi koridor yang lama. Artinya tidak ada bus yang mengaku di koridor 5A, 5B, s/d 5E. Semuanya mengaku di koridor 5. Lalu muncul juga banyak bus dengan kode koridor "NBRT".

Saya menduga kalau NBRT ini adalah bus pengumpan (Feeder Bus) Transjakarta. Merekalah yang saya sebut subkoridor, seperti 1A, 1B, 5A, 5B, dsb.

Terasi (bagian 3): Agregasi, Database, dan Back End API

Sejauh ini, kita berhasil mendapatkan datanya. Kini waktunya untuk menghitung statistiknya dan membuat back end API sederhana. Nantinya bisa dibuat aplikasi sederhana (entah di HTML atau Android) untuk mengambil datanya dan menampilkan grafik waktu tunggu dan waktu tempuh.

---

Agregasi Nilai Statistik

Data yang telah kita miliki adalah:

1. Daftar ketibaan suatu bus, lengkap dengan:
1. lokasi haltenya
2. halte tujuan akhirnya
3. waktu ketibaannya
2. Daftar waktu tempuh suatu bus, lengkap dengan:
1. halte awal
2. halte akhir
3. durasi

Untuk prototipe pertama, informasi statistik berikut perlu didapatkan dengan bermodalkan data mentah di atas:

1. Distribusi probabilitas dalam bentuk PDF (Probability Density Function) untuk waktu tunggu di suatu halte, ke halte tujuan, pada suatu waktu.
2. PDF untuk waktu tempuh bus antara setiap halte yang bertetanggaan.

Dari PDF, segala nilai seperti rata-rata, median, p95, dan lainnya yang nantinya dibutuhkan dapat dihitung dengan mudah. Strategi yang akan saya gunakan adalah memperkirakan PDF-nya dengan Kernel Density Estimation (KDE).

Terasi (bagian 2): Panen dan Pengolahan Data

Setelah membahas bagaimana ide dasar proyek Terasi muncul, tulisan ini akan membahas pengolahan data yang dibutuhkan.

---

Jakara Smart City API

Dengan googling sekilas, saya menemukan bahwa Jakarta Smart City memang membuka API untuk Transjakarta. Terdapat data untuk halte-halte dalam suatu koridor, koordinat halte, dan koordinat setiap bus pada saat itu juga. Saya tidak menemukan data lain yang lebih berguna, jadi diputuskanlah untuk menggunakan koordinat setiap bus pada suatu waktu.

API untuk koordinat setiap bus dapat diakses di http://202.51.116.138:8088/jsc_tj_api.php. API itu sekarang sudah tewas, tetapi sebelumnya dia akan memberikan JSON berisi koordinat setiap bus dalam format:

Saya hanya menampilkan tiga bus saja, tetapi sebenarnya ada 461 bus pada 26 Januari 2016. Sekali mengkonsumsi API itu, didapatkan data sekitar 60 kB. Untuk keperluan Terasi, saya akan mengkonsumsi API itu setiap 1 menit sekali, sehingga setiap hari didapatkan 24 * 60 berkas. Jika 1 berkas berukuran 60 kB, berarti setiap harinya saya memanen data sebesar 86,4 MB. Dalam 1 bulan, datanya akan sebesar 2,6 GB. Angka ini terlihat besar, tapi sebenarnya data JSON yang diberikan ini dapat dikompres menjadi data tabular (misal: csv) yang lebih ringkas. Karena itu saya tidak mengkhawatirkan ukuran datanya.

Dengan "snapshot" koordinat bus setiap menitnya, kita dapat mensimulasikan pergerakan bus secara cukup akurat.

---

Pemanen Data

Selanjutnya saya menuliskan program sederhana dengan Node.js untuk memanggil API tersebut setiap menitnya, lalu menyimpan JSON yang diberikan. Setiap akhir hari, data yang terkumpul dikompres menjadi .tar.gz. Kalau ditanya kenapa pakai Node.js, karena kebetulan saya sedang belajar itu.

Karena saya tidak mau menyalakan komputer sepanjang waktu, saya menyewa server melalui DigitalOcean. Dengan biaya 5 dollar AS setiap bulannya, saya mendapat server paling murah dengan spesifikasi lebih lemah dari laptop tua saya. Servernya memiliki RAM 512 MB dan hard disk 25 GB. Meskipun lemah, cukup untuk keperluan pemanenan data ini.

Untuk memastikan bahwa data terus menerus dipanen, saya membuat sistem logging sederhana. Kalau untuk alasan apapun API memberikan error atau data yang rusak, maka error akan dicatat dan dilaporkan ke channel gratisan Slack (https://slack.com/). Saya cukup memasang aplikasi Slack di hp saya, lalu setiap notifikasi error dapat segera diketahui. Untuk menjaga kesehatannya, setiap hari akan ada laporan berapa ukuran data yang dipanen hari itu juga. Jadi kalau ukuran datanya tidak normal, error bisa disampaikan juga.

Sampai saat ini, saya rasa pemanen datanya sudah bekerja. Selanjutnya perlu dipastikan bahwa data yang diberikan API ini masuk akal. Kalau misalnya posisi busnya sering tidak diperbaharui, atau koordinatnya bisa kacau, dijamin hasil akhirnya amburadul. Oleh karena itu saya terpikir untuk menulis program sederhana untuk memvisualisasikan data perjalanan bus tersebut seperti sebuah video.

---

Visualisasi

Setelah pulang kerja keesokan harinya, saya memeriksa data yang telah dipanen. Terlihat baik, karena setiap menitnya ada data dan tidak ada kerusakan data.

Lalu saya menghabiskan 2 jam berurusan dengan Java awt sambil mengingat kembali ilmu kuliah semester 1. Akhirnya berhasillah penulisan program untuk menggambarkan pergerakan bus berdasarkan API.

Hasilnya memuaskan. Berikut gambaran bus dari 00:00 sampai 23:59. Terlihat bahwa dari 00:00 sampai 03:00 pergerakan bus hanya di koridor tertentu. Masuk akal, berhubung tidak semua bus beroperasi tengah malam. Sesudah itu bus mulai ramai (jam masuk kerja), terutama sejak 05:00. Selanjutnya saya menyaring hasilnya supaya hanya menunjukkan bus dengan label koridor "1".

Video beresolusi tinggi bisa dilihat di https://youtu.be/lzyAfKbAiwc

Terasi (bagian 1): Proyek Analitik Transjakarta

Seri tulisan kali ini tidak ada hubungannya langsung dengan pemrograman kompetitif. Namun, saya menggunakan sejumlah ilmunya dalam perjalanan yang akan saya ceritakan berikut.

Setelah lulus dari perguruan tinggi, saya kerja di Cermati. Kantornya di dekat mall Central Park, Jakarta Barat. Kebetulan lokasinya sangat strategis, terdapat halte Transjakarta di dekatnya. Saya pikir untuk pergi dan pulang ke kantor menjadi sesederhana naik Transjakarta saja. Namun sebenarnya tidak sesederhana itu...

Waktu itu adalah tahun 2015. Saya tidak tahu apakah sekarang situasinya sudah membaik, tetapi kondisi lalu lintas tahun itu cukup mengenaskan. Daerah Jalan S. Parman terkenal sangat macet pada jam masuk atau pulang kantor. Awalnya saya pikir ada busway (jalur Transjakarta), yang membuat Transjakarta kebal kemacetan. Sayangnya, ternyata di Jalan S. Parman terdapat penyatuan busway dengan jalan raya yang membuat bus ikut kena macet...

Akibat dari kemacetan ini adalah:

1. Pergerakan bus menjadi lambat, sehingga...
2. Frekuensi kedatangan bus menjadi rendah, sehingga...
3. Orang yang mengantre di halte menjadi ramai, sehingga...
4. Begitu bus sampai di halte, tidak semua orang kedapatan menaiki bus, sehingga...
5. Harus menunggu kedatangan bus berikutnya, sehingga...
6. ... tekanan darah saya meningkat karena perjalanan dari rumah ke kantor menjadi lama.

Seluruh akibat itu saya rasakan setiap hari, ditambah dengan setiap kali naik TJ (Transjakarta) untuk jalan-jalan di Jakarta. Hingga suatu ketika saya muak, dan menjadi marah. Bagaimana mungkin fasilitas umum untuk masa depan beroperasi seperti ini?

Akhirnya energi amarah yang meluap-luap itu saya alirkan ke ide untuk membuat sistem yang dapat menghitung metrik-metrik Transjakarta, seperti waktu tunggu, waktu perjalanan dari halte ke halte, rata-rata kedatangan bus, dan sebagainya. Dengan metrik tersebut, saya dapat mengukur apakah untuk suatu perjalanan saya akan menggunakan Transjakarta. Apabila ternyata data menunjukkan perjalanannya akan memakan waktu lama, lebih baik saya naik ojek.

Struktur Data Dynamic Range Query

Tanpa terasa saya sudah membahas banyak struktur data dynamic range query. Tulisan ini akan menjadi rangkuman semuanya dan menjadi peta bagi kalian yang hendak mempelajarinya.

---

Technology Tree

Intermezzo:

Kalau kalian pernah bermain game berjenis Real Time Strategy (RTS), mungkin tahu tentang konsep "technology tree". Biasanya Anda akan memainkan satu peradaban yang dimulai dengan teknologi seadanya. Seiring dengan berjalannya waktu, Anda dapat melakukan riset untuk memajukan teknologi dan meningkatkan produktivitas. Ditemukannya suatu teknologi juga memungkinkan pembuatan sejumlah teknologi lain. Contohnya pada game Age of Empires, pembuatan kandang hewan akan memungkinkan dibuatnya cavalry dan pemanah berkuda.

Oke cukup dengan cerita game. Pembelajaran struktur data pun dapat digambarkan seperti sebuah technology tree. Mempelajari suatu struktur data memungkinkan Anda untuk belajar sejumlah struktur data lainnya. Berikut adalah gambarannya:

Klik untuk memperbesar gambar.

Semuanya dimulai dengan array. Dengan array polos, kita dapat melakukan apa saja walaupun secara kurang efektif. Lalu saya tidak mengikutkan keluarga struktur data linear seperti stack/queue/deque, dan juga keluarga heap.

Anak panah menunjukkan bahwa setelah mempelajari suatu konsep (struktur data/teknik), Anda dapat beranjak ke konsep yang lebih lanjut.

Petunjuk Coding: Segment Tree Lazy Propagation

Setelah menguasai penulisan kode segment tree yang melayani update sebuah elemen dan range query, kini waktunya beranjak ke operasi yang lebih sulit: range update.

Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.

---

Konsep

Lazy propagation dapat diimplementasikan ketika:

1. Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
2. Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.

Apabila kedua syarat itu dipenuhi, maka lazy propagation dapat diterapkan. Setiap range update atau query dapat dilaksanakan dalam O(log N).

Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".

Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.

Petunjuk Coding: Segment Tree

Sebenarnya tulisan ini mau difokuskan ke implementasi segment tree. Tapi karena tulisan saya sebelumnya di ristekfasilkom.com sudah musnah (hosting-annya habis), jadinya saya kembalikan back-up tulisannya ke sini.

Segment tree merupakan struktur data yang biasa dipakai untuk menjawab dynamic range
query, yaitu sejumlah operasi yang dilakukan dengan rentang yang bervariasi. Selama tidak ada penyisipan atau penghapusan elemen, segment tree hampir selalu bisa digunakan. Tulisan ini akan membahas tentang konsep struktur data ini dan cara implementasinya.

---

Permasalahan Motivasi

Diberikan sebuah array integer dan serangkaian operasi.
Sebut saja array itu adalah ar. Operasi-operasi yang diberikan bisa berupa:

• update(x, v), yang artinya mengubah isi ar[x] menjadi v.
• query(x, y), yang artinya mencari nilai minimum dari ar[x], ar[x+1], ..., ar[y].

Dengan cara naif, update dapat dilaksanakan dalam O(1). Sementara query dapat dilaksanakan dalam O(N), dengan N adalah panjang array. Tentunya cara ini kurang efisien, khususnya jika N cukup besar dan operasi yang diberikan cukup banyak.

Dengan segment tree, kita dapat melakukannya dengan lebih baik.