En inLab FIB es habitual charlar y compartir anécdotas con los compañeros con los que compartes espacio de trabajo, aunque no siempre llegas a trabajar conjuntamente. La idea de colaborar en un mismo proyecto nos llevó a apuntarnos a la hackathon HackEPS.
Así que este pasado sábado 26 de noviembre, nos levantamos temprano para ir todos juntos hacia la Escuela Politécnica Superior de Lleida, donde nos esperaba un evento cuidadosamente organizado por la asociación juvenil LleidaHack que contaba con la participación de unas 160 personas. Entre éstas, enseguida encontramos algunas caras familiares: algunos de los organizadores de la HackUPC que, si habían asistido buscando nuevas ideas, seguro que encontraron, ya que durante toda la hackathon se ofrecieron diferentes actividades, retos y charlas que aportaron positivamente a la experiencia.
La jornada empezó con una presentación en un anfiteatro donde se explicaban, entre otras cosas, quiénes eran los organizadores, que se podía hacer en la hackathon, qué normas debían seguirse y qué comidas se nos ofrecerían. Seguidamente subieron, una a una, las cinco empresas que hacían de esponsor del evento, a revelar cuáles eran los retos que proponían. Nuestro equipo, prestando atención a los requisitos que se estaban exponiendo, pensábamos que había algunos más o menos interesantes, y más o menos alineados con lo que consideramos que son nuestras habilidades. Por último, cuando Origen Studio propuso un reto centrado en constrayendo programming enseguida estuvimos de acuerdo en que era en lo que queríamos competir.
El reto se subdividía en tres partes. Las dos primeras se basaban en desarrollar un algoritmo de scheduling para asignar un conjunto de tareas de un pedido a diferentes máquinas para ser ejecutadas. Había una lista de restricciones que contemplaban dependencias entre tareas, en qué máquinas se podían ejecutar, etc. que la solución encontrada debía cumplir. Este tipo de problema se asemeja mucho a los que los estudiantes de computación de la FIB se encuentran en las prácticas de la asignatura Lógica en la Informática (LI), donde se busca definir un conjunto de átomos, variables y predicados que generan una fórmula en CNF (Conjunctive Normal Form) donde, posteriormente, un SAT solver es capaz de encontrar una solución, o determinar como insatisfactible.
Usamos las herramientas que conocemos (Prolog) para crear una solución al primer problema que encontraba la distribución de tareas óptima. En el segundo problema se hacían ciertas ampliaciones que imposibilitaban atacarle de la misma forma, ya que los casos eran exponencialmente más difíciles y encontrar el óptimo era inviable. Aunque dedicamos ciertos esfuerzos obteniendo algunos progresos, finalmente no lo solucionamos del todo. En todo caso, el equipo pivotó a tiempo para conseguir el tercer punto, que era realizar una visualización del resultado del algoritmo implementado, de forma que cualquier persona pudiera entender la asignación propuesta. Creamos una simple aplicación web que compilaba el programa Prolog con la entrada del problema, extraía el resultado, y lo devolvía al navegador para su visualización.
Finalmente presentamos nuestra solución al jurado de la empresa que ofrecía el reto, quienes se sorprendieron de que usáramos Prolog, ya que no lo conocían. Después de las presentaciones hablamos un rato y nos dieron algunas intuiciones de cómo reducir la complejidad del segundo problema sacrificando que la solución fuera óptima, y nos recomendaron echar una mirada a las “Google Optimization Tools” para considerar una alternativa basada en IA y funciones heurísticas.
¡Para clausurar el evento, estamos contentos de haber ganado el premio, y de próximamente recibir un par de gafas de realidad virtual que tenemos muchas ganas de probar! ¡Además, nos han comunicado que también nos han otorgado el premio «Josep Maria Ribó» a las Buenas Prácticas de Programación!