Monday 12 December 2022
Monday 12 December 2022
In inLab FIB it is common to chat and share anecdotes with the colleagues with whom you share work space, although you do not always get to work together. The idea of collaborating on the same project led us to sign up for the HackEPS hackathon.
So this past Saturday, November 26, we woke up early to go together to the Higher Polytechnic School of Lleida, where an event carefully organized by the LleidaHack youth association with the participation of about 160 people was waiting for us. Among these, we immediately found some familiar faces: a few of the organizers of the HackUPC who, if they had attended looking for new ideas, surely they found, since throughout the hackathon different activities were offered, challenges and talks that contributed positively to the experience.
The day began with a presentation in an amphitheater where they explained, among other things, who were the organizers, what could be done to the hackathon, what rules had to be followed and what meals would be offered. Then they went up, one by one, the five companies that acted as sponsor of the event, to reveal what were the challenges they proposed. Our team, paying attention to the requirements that were being exposed, thought there were some more or less interesting, and more or less aligned with what we consider to be our abilities. Finally, when Origen Studio proposed a challenge focused on constraint programming we immediately agreed that it was in which we wanted to compete.
The challenge was divided into three parts. The first two were based on developing a scheduling algorithm to assign a set of tasks from an order to different machines to be executed. There was a list of restrictions that contemplated dependencies between tasks, which machines to run to, etc. that the solution found had to comply with. This type of problem is very similar to those that the computer students of the FIB are to the practices of the subject Logic to Informatics (LI), where it seeks to define a set of atoms, variables and predicates that generate a formula in CNF (Conjunctive Normal Form) where, subsequently, a solver SAT is able to find a solution, or else determine as unsatisfactory.
We used the tools we know (Prolog) to create a solution to the first problem that found the optimal task distribution. The second problem was made certain enlargements that made it impossible to attack it in the same way, since the cases were exponentially more difficult and finding the optimal one was not feasible. Although we put some effort into making some progress, we did not solve it at all. In any case, the team pivoted in time to get the third point, which was to make a visualization of the result of the implemented algorithm, so that anyone could understand the proposed assignment. We created a simple web application that compiled the Prolog program with the problem entry, extracted the result, and returned it to the browser to be viewed.
Finally we presented our solution to the jury of the company that offered the challenge, which were surprised that we used Prolog, since they did not know it. After the presentations we talked for a while and they gave us some intuitions of how to reduce the complexity of the second problem sacrificing that the solution was optimal, and recommended us take a look at Google Optimization Tools" to consider an alternative based on AI and heuristic functions.
To close the event, we are happy to have been rewarded for the effort with the first position, and soon to receive a pair of glasses of virtual reality that we look forward to try! In addition, we have been informed that we have been awarded with the "Josep Maria Ribó" award for good programming practices!
fib.upc.edu