Bad Apple yang Terdiri dari 6.500 Ekspresi Reguler yang Dicari di Vim

• Untuk memutar video Bad Apple di dalam Vim, setiap frame diubah menjadi kueri pencarian, lalu layar digambar hanya dengan highlight hasil pencarian di atas grid kosong 120x90
• Video dipecah menjadi sekitar 6.500 frame PNG dengan ffmpeg, lalu setiap gambar diubah di Python menjadi array 2D berisi 0 dan 1 untuk menandai piksel hitam
• Dengan menggabungkan \%l, \%c, \zs, \ze, dan pola OR \| di Vim, rentang persegi panjang baris-kolom tertentu bisa di-highlight dalam satu pencarian
• Proses mereduksi frame menjadi pola pencarian persegi panjang tidak memakai solusi optimal, melainkan memilih string pencarian terpendek di antara penggabungan atas→bawah, penggabungan kiri→kanan, dan RLE per baris
• Makro memasukkan pola pencarian tiap baris ke register / lalu berpindah ke baris berikutnya untuk mengganti frame, sehingga mengurangi kedipan dan penurunan frame rate yang muncul saat menempel kueri panjang langsung ke kotak pencarian

---

Memutar Bad Apple dengan highlight pencarian Vim

• Tujuannya adalah menonton video Bad Apple tanpa keluar dari Vim
• Yang benar-benar berubah di layar bukan isi file, melainkan kueri pencarian saat ini di Vim
• Video hasilnya dibatasi pada resolusi 120x90
  • Sulit memperbesarnya lebih jauh karena ukuran layar

Ekstraksi frame dan binerisasi

• Menggunakan video dan saran perintah ffmpeg dari repositori badapple-frames milik Felixoofed untuk mendapatkan sekitar 6.500 frame PNG
• Kode Python mengubah ukuran tiap PNG menjadi 120x90 dan mengonversinya ke hitam-putih, lalu memperlakukan nilai piksel di bawah 10 sebagai 1
  • 1 berarti piksel hitam
  • 0 berarti piksel terang
• Video asli berukuran 480x360, tetapi diperkecil ke 120x90 setelah mengukur ukuran terminal
• Fungsi text_preview digunakan untuk memeriksa hasil konversi dengan mencetak 0 sebagai ., dan 1 sebagai #

Membuat karakter terminal terlihat seperti piksel

• Jika membuat grid teks di dalam file Vim lalu mencari karakter tertentu, highlight hasil pencarian dapat terlihat seperti gambar
• Highlight pencarian bawaan berwarna biru sehingga kurang jelas, jadi digunakan pengaturan hi Search cterm=NONE ctermfg=grey ctermbg=grey
  • Warna depan dan latar belakang karakter yang ditemukan disamakan menjadi abu-abu agar terlihat seperti blok
• Font biasa memiliki bentuk huruf yang tinggi secara vertikal sehingga piksel tampak seperti persegi panjang
• Font Square digunakan agar karakter terminal lebih mendekati bentuk persegi dan grid tampak lebih alami

Menggambar persegi panjang dengan pola pencarian

• Pencarian Vim bisa mencocokkan berdasarkan nomor baris dan nomor kolom tertentu
• Contoh pola \%>5c\%<15c\%>4l\%<9l mencocokkan persegi panjang di antara kolom 5~15 dan baris 4~9
• Beberapa persegi panjang dapat dihubungkan dengan \| sebagai OR sehingga bisa dicocokkan sekaligus dalam satu string pencarian
• Berkat fitur ini, masalahnya berubah menjadi memecah piksel hitam tiap frame menjadi beberapa kumpulan persegi panjang

Algoritme untuk mereduksi frame menjadi persegi panjang

• Grid 90x120 memiliki sekitar 10.000 piksel, jadi jika pola dibuat per piksel, string pencarian bisa menjadi puluhan ribu karakter
• Dalam pengujian dasar, pencarian Vim sendiri cepat, tetapi string pencarian yang terlalu panjang menurunkan kecepatan frame
• Metode awal yang dibuat mencari rentang berurutan dari angka 1 per baris, lalu jika tumpang tindih dengan rentang pada baris berikutnya, rentang itu digabung menjadi persegi panjang
  • Mencari rentang berurutan dari 1 di baris pertama
  • Mencari tumpang tindih antara rentang di baris berikutnya dan rentang di baris sebelumnya
  • Jika luas persegi panjang gabungan lebih besar daripada luas masing-masing baris secara terpisah, maka digabung
  • Jika memungkinkan, rentang baru terus digabung ke persegi panjang yang sudah ada
• Metode ini tidak optimal karena tidak melihat lebih jauh dari satu baris
  • Kasus yang saat ini tampak seperti penggabungan buruk bisa saja sebenarnya menjadi penggabungan yang baik jika mempertimbangkan baris-baris setelahnya, tetapi hal itu terlewat

Tiga cara membuat pola untuk menghindari bottleneck

• Banyak string pencarian berada di kisaran 500~2.000 karakter, tetapi pada beberapa frame ada string pencarian yang melebihi 10.000 karakter
• String pencarian yang panjang menurunkan frame rate dari sekitar 40 FPS menjadi hanya satu digit
• Panjang string pencarian bukan indikator kinerja yang sempurna, tetapi dalam kasus ini pola dengan panjang mirip yang dihubungkan dengan banyak OR dapat sekaligus menambah jumlah pola dan waktu pencarian
• Alih-alih mencari algoritme umum yang optimal, tiga algoritme sederhana dijalankan semuanya lalu dipilih pola pencarian yang paling pendek
  • Metode penggabungan atas→bawah
  • Metode penggabungan kiri→kanan
  • Metode RLE per baris
• Jumlah pemilihannya adalah sebagai berikut
  • Penggabungan atas→bawah, yaitu metode asli: 1.110 kali
  • Penggabungan kiri→kanan: 2.239 kali
  • RLE satu baris: 3.300 kali
• RLE paling sering terpilih, tetapi dalam kasus buruk hasilnya bisa sangat buruk, jadi tidak dipakai sendirian

Mengganti frame di dalam Vim

• Di jendela tengah atas Vim diletakkan file kosong berukuran 90 baris x 120 kolom
  • Karena pencarian didasarkan pada baris dan kolom, karakter nyata tidak diperlukan
• Di kiri dan kanan diletakkan buffer kosong untuk menempatkan gambar di tengah
• Di jendela bawah diletakkan sekitar 6.500 pola pencarian, satu per baris
• Makro membaca pola pencarian pada baris saat ini, memasukkannya ke register pencarian, lalu berpindah ke baris berikutnya

• Makro yang digunakan

  • Makronya berbentuk "ay$:let @/=@a^M+
  • Cara kerjanya sebagai berikut
  • "a: menggunakan register a
  • y$: menyalin hingga akhir baris saat ini
  • :let @/=@a: mengatur register pencarian / ke isi register a
  • ^M: menjalankan perintah
  • +: berpindah ke awal baris berikutnya
  • Jika makro ini direkam ke register q, maka 1500@q bisa memajukan 1.500 frame secepat mungkin
  • Jika kueri panjang langsung ditempel ke kotak pencarian seperti /^Ra^M, kotak pencarian bisa membesar mengikuti kueri ribuan karakter dan menyebabkan kedipan serta penurunan frame rate
  • Dengan mengatur register pencarian langsung memakai let @/=@a, masalah ini bisa dihindari

Keterbatasan dan kode yang dipublikasikan

• Karena memakai fitur pencarian baris-kolom Vim, ada argumen bahwa ini tidak sepenuhnya tersusun hanya dari ekspresi reguler tradisional
• Tidak ada penanganan untuk menjaga frame rate tetap stabil
  • Frame rate agak berfluktuasi di sepanjang video
• Meski begitu, hasilnya mendekati solusi umum untuk memutar video di dalam Vim hanya dengan kueri pencarian
• Kodenya belum dirapikan, tetapi bisa dilihat di repositori vim-badapple

[GN⁺]

Opini Hacker News

• Kalau nolen, saya memang menduga dia tahu cara memperbesar sesuatu 1000 kali lipat :))) Dulu saya pernah mencoba teknik-teknik serupa, tapi terpisah-pisah, dan jelas bukan dikerjakan dalam sehari. Kalau tertarik:
  Bad Matrix (mencetak blok ke terminal dengan tput): https://www.evalapply.org/posts/bad-matrix/
  Animating Text Art in Javascript (mencetak teks pada grid tetap lalu menganimasikannya seperti flipbook): https://www.evalapply.org/posts/animate-text-art-javascript/...
  oxo (memformat dan mencetak papan tic-tac-toe di terminal, lalu mencocokkan hasil menang/kalah/seri dengan regex): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
  Tapi tetap saja Bad Apple itu yang terbaik

• Demo teknologi yang benar-benar membuat saya terpikat pada Bad Apple adalah versi yang berjalan di NES
  https://somethingnerdy.com/downloads/
  Video yang saya jalankan di Everdrive saya ada di sini
  https://inversethought.com/jordi/video/badapple.mp4
  Audionya juga keluar lengkap. Datanya sekitar 1GB, dan ini dilakukan pada sistem yang ukuran game biasa tidak lebih dari beberapa ratus KB serta CPU-nya hanya punya tiga register 8-bit untuk komputasi

  • Keren. Sebagai orang yang pernah sedikit mencoba pengembangan NES, sepertinya tidak mudah menyesuaikan performa grafisnya. Biasanya, hanya dengan beberapa sprite dalam satu baris saja NES mulai ‘melelehkan’ sprite, meski saya tidak tahu istilah tepatnya
    Saya penasaran apakah mereka memakai tile map latar alih-alih sprite. Itu pun cukup mengesankan dari sisi bandwidth grafis
    Tertulis “laju pemutaran audio penuh (44,2kHz)”, dan saya juga terkejut suaranya sejernih itu. Saya penasaran apakah ini fitur yang diperluas oleh cartridge. Seingat saya, kanal PCM NES sama sekali tidak mencapai bitrate itu, dan ukuran sampelnya juga tampaknya 8-bit
  • Tergantung bagian mana yang menurut Anda menarik, Anda mungkin juga suka Bad Apple serupa yang diimplementasikan di NES. Sebagai tantangan tambahan, ia dijalankan lewat ACE di Super Mario Bros., dan semua datanya di-streaming melalui controller
    https://www.youtube.com/watch?v=lfG8DbxFibY
    Ada juga video penjelasan yang dibuat bersama
    https://www.youtube.com/watch?v=Wa0u1CjGtEQ
  • Benar-benar keren; kalau ada tulisan rangkuman tentang pekerjaan ini, saya ingin membacanya

• Bagian yang memindahkan ke baris berikutnya di akhir agar macro Vim bisa “diputar ulang” juga bisa menjalankan macro sekali untuk tiap baris dengan perintah berikut
  :%norm @q

  • Wah, hari ini saya belajar sesuatu. Cukup mengejutkan saya tidak tahu trik ini
    Dulu saat bermain Vim golf, biasanya saya membuat macro secara rekursif. Merekam macro lalu mengakhirinya dengan +@q. Artinya, pindah ke baris berikutnya lalu menjalankan macro lagi. Dengan begitu, sekali menjalankan macro akan menyapu semua baris
    Dari sisi jumlah ketikan, itu sangat efisien, tapi dalam praktiknya sulit dipikirkan dan tidak mudah menjadi kebiasaan, jadi tidak sering saya pakai. Tetap saja, ini teknik yang menarik untuk golf

• Bulan lalu Govee Curtain Lights ini sedang diskon
  https://us.govee.com/products/govee-curtain-lights
  Setahu saya, kita bisa mengunggah GIF animasi ke sana. Jadi saya menambahkan tugas membuat GIF “Bad Apple” ke papan kanban, tapi saya belum tahu seberapa besar memori perangkatnya dan seberapa baik itu akan berjalan
  Adegan ketika Remmy Scarlet sesekali melebarkan sayapnya masih membuat saya merinding

  • Saya pernah mencoba ini dengan lampu Twinkly, tetapi sayangnya memori di sisi lampunya tidak cukup sehingga tidak bisa berjalan lebih dari beberapa detik
  • Saya punya GIF Bad Apple beresolusi 64x32, ukurannya sedikit di bawah 1MB
    https://ezgif.com/ sangat membantu

• Bad Apple tidak pernah membosankan. Ini hal terbaik di internet. Dan hampir setiap kali melihatnya, saya agak iri kenapa bukan saya yang lebih dulu memikirkan ide itu
  Saya juga sangat suka implementasi catatan kaki di blog ini. Sepertinya akan saya pakai

  • Catatan kaki itu diambil dari situs teman saya yang berbakat, Jake (https://jakelazaroff.com/). Mungkin Anda pernah melihat karyanya di sini sebelumnya
    Di layar besar, catatan itu tampil sebagai sidenote; di layar kecil, berubah menjadi catatan kaki inline yang terbuka saat diklik. Silakan ambil sesuka hati

• Dalam persoalan minimisasi persegi panjang, masalah di sini tampaknya berbeda dari yang dibahas di StackOverflow. Thread SO membahas partisi persegi panjang yang tidak saling tumpang tindih, sedangkan proyek Vim ini mengizinkan tumpang tindih
  Jadi mungkin mencari solusi optimalnya jauh lebih mudah

  • Dari sudut pandang algoritma, sebenarnya kebalikannya. Masalah penutup minimum yang mengizinkan tumpang tindih bersifat NP-hard, sedangkan masalah partisi minimum yang tidak mengizinkan tumpang tindih punya algoritma waktu polinomial. Lihat makalah Franzblau dan Kleitman tahun 1984, “An Algorithm for Covering Polygons with Rectangles”: https://core.ac.uk/download/pdf/82333912.pdf
    Tentu ini hanya catatan akademis, dan bukan berarti salah satunya benar-benar lebih mudah dalam situasi proyek sore hari yang sekadar membuat sesuatu berjalan
  • Poin bagus. Benar, saya benar-benar melewatkan fakta bahwa persegi panjangnya bisa saling tumpang tindih. Proyek ini mungkin akan saya akhiri di sini dan saya cukup puas dengan solusi saat ini, tetapi benar bahwa hal ini tampaknya sangat menyederhanakan masalahnya

• Generator kandidat solusi paralel adalah ide yang sangat bagus, tapi setiap kali saya butuh waktu lama untuk menyadari bahwa kita tidak harus membuat algoritma terkuat. Karena selalu terasa kalau sedikit diperbaiki lagi, kita bisa membuat solusi yang berlaku untuk semua kasus

  • Ini mungkin cara favorit saya untuk membuat prototipe cukup cepat. Setiap kali berhasil, rasanya menyenangkan
    Namun saya setuju bahwa sangat sulit menyadari bahwa kita bisa mundur selangkah dan memakai cara ini alih-alih memakai sesuatu yang “sempurna”

• Cukup keren. Kreativitasnya bagus. Game-game yang menjadi dasarnya juga lumayan, dan bullet hell-nya terasa menghipnotis

• Orang-orang yang menjalankan Doom atau Bad Apple dengan cara yang tak terduga benar-benar hebat
  Ada juga contoh menarik seperti menjalankan Doom di alat tes kehamilan

  • Saya sulit sepakat dengan itu. Pada dasarnya itu lebih mirip memasukkan mikrokontroler sembarang ke dalam casing alat tes kehamilan lalu menjalankan Doom

• Saya jadi teringat menonton Piala Dunia 2006 di kantor. Saya bisa login ke server rumah lewat ssh dan menonton pertandingan di terminal
  Bandwidth tidak cukup untuk menontonnya dengan cara lain