Bad Apple compuesto por 6,500 expresiones regulares para buscar en Vim

• Para reproducir el video de Bad Apple dentro de Vim, cada fotograma se convirtió en una consulta de búsqueda y la imagen se dibuja únicamente con el resaltado de búsqueda sobre una cuadrícula vacía de 120x90
• El video se dividió en unas 6,500 imágenes PNG con ffmpeg, y luego en Python cada imagen se convirtió en un arreglo 2D de 0 y 1 para marcar los píxeles negros
• Combinando \%l, \%c, \zs, \ze y el patrón OR \| de Vim, se resalta en una sola búsqueda un rectángulo dentro de un rango específico de filas y columnas
• El proceso para reducir cada fotograma a patrones de búsqueda rectangulares no usa una solución óptima, sino que elige la cadena de búsqueda más corta entre fusión de arriba→abajo, fusión de izquierda→derecha y RLE por fila
• Un macro coloca el patrón de búsqueda de cada línea en el registro / y pasa a la siguiente línea para avanzar fotogramas, reduciendo el parpadeo y la caída de rendimiento que ocurre al pegar consultas largas directamente en la barra de búsqueda

---

Reproduciendo Bad Apple con el resaltado de búsqueda de Vim

• El objetivo es ver el video de Bad Apple sin salir de Vim
• Lo que realmente cambia en pantalla no es el contenido del archivo, sino la consulta de búsqueda actual de Vim
• El video resultante queda limitado a una resolución de 120x90
  • Por el tamaño de la pantalla, era difícil hacerlo más grande

Extracción de fotogramas y binarización

• Usando el video y la sugerencia del comando ffmpeg del repositorio badapple-frames de Felixoofed, se obtuvieron unas 6,500 imágenes PNG
• Con código en Python, cada PNG se redimensionó a 120x90 y se convirtió a blanco y negro; luego, si el valor del píxel era menor que 10, se trataba como 1
  • 1 significa un píxel negro
  • 0 significa un píxel claro
• El video original era de 480x360, pero después de medir el tamaño de la terminal se redujo a 120x90
• La función text_preview se usa para verificar el resultado de la conversión, imprimiendo 0 como . y 1 como #

Hacer que los caracteres de la terminal parezcan píxeles

• Si se crea una cuadrícula de texto dentro de un archivo de Vim y se buscan caracteres específicos, el resaltado de los resultados puede verse como un dibujo
• Como el resaltado de búsqueda predeterminado es azul y no se veía con claridad, se usó la configuración hi Search cterm=NONE ctermfg=grey ctermbg=grey
  • Al igualar en gris el color de primer plano y el de fondo de los caracteres encontrados, estos se ven como bloques
• En una fuente normal, los caracteres son más altos que anchos, así que los píxeles se ven rectangulares
• Se usó la fuente Square para que los caracteres de la terminal se acercaran más a una forma cuadrada y la cuadrícula se viera más natural

Dibujar rectángulos con patrones de búsqueda

• La búsqueda de Vim puede hacer coincidencias tomando como referencia números de fila y números de columna específicos
• El patrón de ejemplo \%>5c\%<15c\%>4l\%<9l coincide con un rectángulo entre las columnas 5~15 y las filas 4~9
• Varios rectángulos pueden conectarse con \| como OR para coincidir al mismo tiempo dentro de una sola cadena de búsqueda
• Gracias a esto, el problema se convierte en descomponer los píxeles negros de cada fotograma en varios conjuntos de rectángulos

Algoritmo para reducir los fotogramas a rectángulos

• La cuadrícula de 90x120 tiene unos 10,000 píxeles, así que si se crea un patrón por píxel, la cadena de búsqueda puede crecer a decenas de miles de caracteres
• En las pruebas básicas, la búsqueda de Vim en sí era rápida, pero las cadenas de búsqueda demasiado largas reducían la velocidad de los fotogramas
• El método inicial encontraba, por fila, tramos continuos de 1 y los fusionaba en rectángulos si se superponían con los tramos de la fila siguiente
  • Encuentra los tramos continuos de 1 en la primera fila
  • Busca superposiciones entre los tramos de la fila siguiente y los de la fila anterior
  • Si el área del rectángulo fusionado es mayor que el área de cada fila por separado, se fusiona
  • Cuando es posible, sigue fusionando nuevos tramos al rectángulo existente
• Este método no es óptimo porque no mira más allá de una sola fila
  • Puede perder casos donde una fusión parece mala en el momento, pero sería buena al considerar también las filas siguientes

Tres formas de generar patrones para evitar cuellos de botella

• Muchas cadenas de búsqueda estaban en el rango de 500 a 2,000 caracteres, pero en algunos fotogramas se generaban cadenas de más de 10,000 caracteres
• Las cadenas de búsqueda largas hacían caer la velocidad de los fotogramas de cerca de 40 FPS a un solo dígito
• La longitud de la cadena de búsqueda no es un indicador perfecto del rendimiento, pero en este caso muchos patrones de longitud parecida conectados con OR también podían aumentar tanto la cantidad de patrones como el tiempo de búsqueda
• En lugar de buscar un algoritmo general óptimo, se ejecutan tres algoritmos simples y se elige el patrón de búsqueda más corto
  • Método de fusión de arriba→abajo
  • Método de fusión de izquierda→derecha
  • Método de RLE por fila
• La cantidad de veces elegida cada opción fue la siguiente
  • Fusión de arriba→abajo, que era el método original: 1,110 veces
  • Fusión de izquierda→derecha: 2,239 veces
  • RLE de una sola fila: 3,300 veces
• Aunque RLE fue la opción elegida con más frecuencia, en los peores casos puede salir muy mal, así que se evita usarlo por sí solo

Avanzar fotogramas dentro de Vim

• En la ventana superior central de Vim se coloca un archivo vacío de 90 líneas x 120 columnas
  • Como la búsqueda se basa en filas y columnas, no hacen falta caracteres reales
• A izquierda y derecha se colocan buffers vacíos para centrar la imagen
• En la ventana inferior se ponen, una por línea, unos 6,500 patrones de búsqueda
• El macro lee el patrón de búsqueda de la línea actual, lo pone en el registro de búsqueda y pasa a la siguiente línea

• Macro utilizado

  • El macro tiene la forma "ay$:let @/=@a^M+
  • Su funcionamiento es el siguiente
  • "a: usa el registro a
  • y$: copia hasta el final de la línea actual
  • :let @/=@a: establece el registro de búsqueda / con el contenido del registro a
  • ^M: ejecuta el comando
  • +: se mueve al inicio de la siguiente línea
  • Si este macro se grabó en el registro q, con 1500@q se pueden avanzar 1,500 fotogramas lo más rápido posible
  • Si se pega directamente una consulta larga en la barra de búsqueda, como /^Ra^M, la barra puede expandirse para acomodar consultas de miles de caracteres, provocando parpadeo y caída de fotogramas
  • Al establecer directamente el registro de búsqueda con let @/=@a, se evita ese problema

Limitaciones y código publicado

• Como se usó la función de búsqueda por fila y columna de Vim, se puede argumentar que no está compuesto únicamente por expresiones regulares tradicionales
• No hay un mecanismo para mantener una velocidad de fotogramas estable
  • A lo largo del video completo, la velocidad fluctúa en algunos tramos
• Aun así, se logró un resultado cercano a una solución general para reproducir video dentro de Vim usando solo consultas de búsqueda
• El código no está ordenado, pero se puede revisar en el repositorio vim-badapple

[GN⁺]

Comentarios de Hacker News

• Si fuera nolen, habría sabido escalar algo 1000 veces :))) Antes he usado técnicas parecidas, pero por separado, y definitivamente no todo en un solo día. Si les interesa:
  Bad Matrix (imprimir bloques en la terminal con tput): https://www.evalapply.org/posts/bad-matrix/
  Animating Text Art in Javascript (imprimir texto en una cuadrícula fija para animarlo como un flipbook): https://www.evalapply.org/posts/animate-text-art-javascript/...
  oxo (formatear e imprimir un tablero de tres en raya en la terminal y hacer match del resultado de victoria/derrota/empate con regex): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
  Aun así, ese Bad Apple es lo máximo

• La demo técnica que de verdad me hizo obsesionarme con Bad Apple fue la versión que corría en NES
  https://somethingnerdy.com/downloads/
  Aquí está el video corriéndolo en mi Everdrive
  https://inversethought.com/jordi/video/badapple.mp4
  Incluso reproduce el audio completo. Los datos son de alrededor de 1 GB, y esto se logró en un sistema donde un juego normal no pasa de unos cientos de KB y la CPU solo tiene 3 registros de 8 bits para cálculo

  • Increíble. Habiendo hecho un poco de desarrollo para NES, siento que debió de haber sido difícil ajustarse al rendimiento gráfico. Normalmente, si tienes aunque sea unos cuantos sprites en una línea, la NES empieza a “derretir” sprites, aunque no sé cuál sea el término correcto
    Me pregunto si usaron el mapa de tiles de fondo en lugar de sprites. Incluso así, sería bastante impresionante en términos de ancho de banda gráfico
    Dice “frecuencia total de reproducción de audio (44.2kHz)”, y también me sorprende que el sonido sea tan claro. Me pregunto si es alguna capacidad extra que habilita el cartucho. Según recuerdo, el canal PCM de la NES ni de cerca llega a ese bitrate, y creo que el tamaño de muestra también era de 8 bits
  • Dependiendo de qué parte te haya parecido divertida, también podría gustarte un Bad Apple parecido hecho en NES. Como dificultad extra, corre mediante ACE de Super Mario Bros. y todos los datos se transmiten por el control
    https://www.youtube.com/watch?v=lfG8DbxFibY
    También hay un video explicativo hecho junto con eso
    https://www.youtube.com/watch?v=Wa0u1CjGtEQ
  • Está buenísimo; si por casualidad tienes una nota escrita sobre este trabajo, me encantaría leerla

• Para hacer que una macro de Vim se pudiera “reproducir de nuevo”, esa parte de moverse a la siguiente línea al final también se puede resolver ejecutando la macro una vez por cada línea con este comando
  :%norm @q

  • Wow, hoy aprendí algo. La verdad me sorprende bastante no haber conocido este truco
    Cuando hacía Vim golf, normalmente lo resolvía haciendo la macro recursiva. Grababas la macro y terminabas con +@q; o sea, moverte a la siguiente línea y volver a ejecutar la macro. Entonces, al ejecutarla una sola vez, recorría todas las líneas
    Es muy eficiente en número de teclas, pero en la práctica es difícil de razonar y no se te pega mucho en las manos, así que no terminé usándolo mucho. Aun así, es una técnica divertida para golf

• El mes pasado estas Govee Curtain Lights estaban en oferta
  https://us.govee.com/products/govee-curtain-lights
  Según entiendo, puedes subirles GIFs animados. Así que agregué a mi tablero Kanban la tarea de hacer un GIF de “Bad Apple”, aunque todavía no sé cuánta memoria tiene el dispositivo ni qué tan bien funcione
  La escena donde Remmy Scarlet abre las alas todavía me pone la piel chinita de vez en cuando

  • Yo intenté esto con luces Twinkly, pero tristemente la memoria del lado de las luces no alcanzaba para correrlo por más de unos segundos
  • Tengo un GIF de Bad Apple en resolución 64x32, y pesa un poco menos de 1 MB
    https://ezgif.com/ me ayudó muchísimo

• Bad Apple nunca aburre. Es de lo mejor que hay en internet. Y casi cada vez que lo veo me da un poco de celos no haber tenido yo esa idea primero
  También me encanta la implementación de notas al pie de este blog. Creo que la voy a copiar

  • Esas notas al pie vienen del sitio de mi talentoso amigo Jake (https://jakelazaroff.com/). Puede que ya hayas visto su trabajo por aquí antes
    En pantallas grandes aparecen como sidenotes, y en pantallas pequeñas se convierten en notas al pie en línea que se despliegan al hacer clic. Siéntete libre de copiarlas

• En el problema de minimización de rectángulos, aquí el problema parece distinto al que se discutió en StackOverflow. El hilo de SO trata sobre partición en rectángulos sin solapamiento, pero este proyecto en Vim permite traslapes
  Así que da la impresión de que encontrar la solución óptima podría ser mucho más fácil

  • Desde el punto de vista algorítmico, en realidad es al revés. El problema de cobertura mínima permitiendo traslapes es NP-hard, mientras que el problema de partición mínima sin traslapes sí tiene algoritmos en tiempo polinomial. Ver el artículo de Franzblau y Kleitman de 1984, “An Algorithm for Covering Polygons with Rectangles”: https://core.ac.uk/download/pdf/82333912.pdf
    Claro, esto es solo una digresión académica, y no necesariamente significa que uno sea más fácil en la práctica cuando estás armando algo que funcione en un proyecto de una tarde
  • Buen punto. Sí, se me estaba pasando por completo el hecho de que los rectángulos pueden traslaparse. Probablemente voy a dejar este proyecto hasta aquí y estoy bastante satisfecho con la solución actual, pero sí parece cierto que ese detalle simplifica bastante el problema

• El generador paralelo de soluciones candidatas es una idea realmente buena, pero siempre me toma mucho tiempo darme cuenta de que no hace falta construir el algoritmo definitivo. Porque siempre parece que con un pequeño ajuste más podrías hacer una solución que sirva para todos los casos

  • Probablemente es uno de mis enfoques favoritos para hacer prototipos lo suficientemente rápido. Me da gusto cada vez que funciona
    Pero coincido en que es realmente difícil dar un paso atrás y darte cuenta de que puedes usar este enfoque en lugar de irte por algo “perfecto”

• Bastante genial. Muy buena creatividad. Los juegos en los que se basa también están muy bien, y el danmaku es hipnótico

• La gente que logra correr Doom o Bad Apple de formas inesperadas de verdad está en otro nivel
  Hay casos curiosos como el de correr Doom en una prueba de embarazo

  • No estoy tan de acuerdo con eso. En realidad fue más bien meter un microcontrolador cualquiera dentro de la carcasa de una prueba de embarazo y correr Doom ahí

• Esto me recordó cuando vi el Mundial de fútbol de 2006 en el trabajo. Me conectaba por ssh a mi servidor de casa y podía ver el partido en la terminal
  No tenía suficiente ancho de banda para verlo de otra manera