Segundo post de la serie en la que comento mis progresos semanales. Quizás no haya sido una semana tan productiva como la anterior, o al menos mirado desde el punto de vista del número de cosas que he hecho, pero ha sido una semana intensa :)

Playa de Ris, Noja (España)
Playa de Ris, Noja (España)

Competitive programming en CodeForces

Esta semana ha tenido lugar otra competición de CodeForces en la que he tenido el gusto (o el disgusto) de participar. No me ha salido nada bien, pero me ha dado para aprender mucho.

En primer lugar, el uso de C++ me volvió a pasar otra mala jugada, demasiado tiempo perdido en mitad de una competición intentando hacer algo muy básico. Es por ello que he añadido un nuevo template de Python a CodeForces Tools, la utilidad de línea de comandos que uso para acelerar la participación en los concursos de la página. Esta utilidad te prepara los ficheros iniciales listos para que tú solo tengas que programar. También te descarga los test de ejemplo de cada uno de los problemas para que con una simple instrucción puedas ejecutarlos todos. Para más información puedes consultar el repositorio de GitHub del autor.

Aunque no puede completar más que 1 problema de 6, después de la competición me puse a estudiar en detalle cada uno de los ejemplo y a resolverlos. Eso desencadenó unas cuantas (muchas) horas de investigación sobre temas relacionados con aritmética modular. En las siguientes secciones comento más cosas al respecto.

Esta semana no solo hay una competición. Hay otra que está teniendo lugar en estos mismos instantes que estoy escribiendo estas líneas. Por una vez creo que dejaré pasar esta competición porque no considero que el aeropuerto sea el mejor lugar para concentrarse…

Aritmética modular

La aritmética modular o aritmética de reloj está presente un muchos problemas de programación competitiva. Sin ir más lejos, en mis dos primeras competiciones me he encontrado con 3 problemas que se pueden resolver utilizando el operador módulo. De todos los problemas, mi favorito es el problema B.

Aproveché este tipo de problemas para repasar sobre aritmética modular y… una cosa llevó a la otra y acabé viendo vídeos de criptografía y cómo generar los números primos tan grandes que son necesarios para que se pueda encriptar con seguridad. La mayor parte de los recursos consultados son contenidos de KhanAcademy:

Reservoir sample

Durante la semana resolví un problema de programación competitiva y típico de entrevistas de trabajo para Google, Facebook, Microsoft… El problema consiste en elegir un elemento random de un string. En este artículo explico en detalle cómo se resuelve.

Euler Phi function

Para resolver el problema D de esta competición se necesita conocimiento matemático extra que yo no poseía. Este conocimiento está relacionado con la función Phi del gran Euler. Si no sabes cómo resolverlo te recomiendo visitar el artículo con la solución a este bonito problema.

Zenbakia

Hace ya años que tenía pensado iniciar mi propia librería de álgebra lineal. Pues bien, no es que la haya empezado a programar aún, pero tengo una idea mucho más clara de lo que quiero hacer. Me gustaría tener una librería en la que yo pueda añadir mi propia implementación de algoritmos conocidos. Estoy hablando de cualquier tipo de algoritmo, no necesariamente aquellos relacionados con el álgebra lineal. Por ejemplo, me gustaría tener en un solo lugar un una clase para tratar con arrays multidimensionales (tipo ndarray de NumPy), una función para factorizar un número en sus factores primos, una implementación del A* con un ejemplo de uso, una implementación de un Trie…

Zenbakia es el nombre elegido para dicho proyecto. ¿Por qué ese nombre? Después de darle la vuelta a muchos nombres, este es el que más me gustó y también el más único. Pensaba en nombres relacionados con números, algoritmos… probé en varios idiomas: español, inglés, japonés, latín… ¡todos contaban con repositorios en GitHub y con muchas estrellas! Zenbakia significa número en Euskera, la lengua que se habla en el Pais Vasco. Es un nombre que me suena bien, va en relación con el tema y no tiene casi proyectos con ese nombre en GitHub (lo que simplemente lo hace algo más único).

Aún estoy en proceso de decidir en qué lenguaje programarla, estoy entre C++ y Rust. Quizás por el momento me decante más por Rust, por probar un nuevo lenguaje. C++ ya me lo conozco un poco (no soy un experto ni de lejos) y ya sé que no me gusta demasiado.

También sería de mi interés poder compilar mi librería en WebAssembly, para así poder portar muchos de los ejemplos a la web, haciéndolos interactivos y disponibles para todo el mundo. Hice varios toy examples con esta tecnología y me atrae la idea de programar en Rust/C++ y generar una librería de JavaScript que pueda utilizar en la web.

La semana que viene más… pero no mucho

Este texto lo escribo en el aeropuerto de Santander, mientras espero mi vuelo dirección a la capital Irlandesa. Mi estancia en Dublín va a ser muy corta, por lo que aprovecharé para visitar a mis viejos amigos hacer algunos recados y a recordar el sabor de una buena Guinness. Dudo que me sobre tiempo para trabajar en el ordenador… pero oye, nunca se sabe.