You are here
How we almost won VPW-2011, using only Haskell
Last week, I competed in this years Flemish Programming Contest (VPW for short in Flemish/Dutch). After attending the first VPW edition in Leuven in 2009 as an impartial observer and co-organizing VPW-2010 in Ghent, I wanted to experience the contest from the perspective of the competitors.
First, a brief description of the contest: each team of max. 3 members is given 5 assignments of varying difficulty, and needs to solve as many as they can in just 3 hours. Naturally, the teams that solves the most assignments wins. The time needed since the start of the contest per solved problem is summed up to rank teams that correctly solved an equal number of problems, a punishment of 20 minutes is added for each incorrect submission made and a bonus of 60 minutes deduction is granted to the teams that are able to solve one particular problem sufficiently efficient. Important side-notes are that each team is only allowed to use one single laptop/keyboard/mouse, that teams are not allowed to access the internet during the contest and that solutions to problems are tested on non-disclosed input sets.
To make things more interesting (and maybe also harder), I picked Haskell as the sole language my team would use to implement my solutions. After finding two like-minded team mates in the GhentFPG community, we chose "Avoid Success At All Costs" (the Haskell motto) as team name and started prepping for the contest.
By second hand experience, I knew that having a set of functions handy to process input and write out answers in a structured way, implement some standard programming paradigms (backtracking, binary search, etc.) and handle with 'special' data structures like matrices and such is a big plus. Since only the Haskell Platform would be available on the contest servers, we put together a template which contains a whole bunch of functions that might come in useful during the contest. We also held a couple of training sessions in which we mimiced the contest setting a closely a possible, to figure out what tactic to use, decide who would sit behind the single available laptop (that turned out to be me in the end) and who would draft the algorithms for the hardest problems. A last minute dropout of one of the team members caused some minor headaches, but we were able to find a very worthy replacement in the end, i.e. a guy who co-organized VPW-2009.
I was fairly confident that we would perform well, given that our team was fairly well prepared and that two of us were closely involved with the design of assignments and/or organization during previous contests. However, it turned out I grosly underestimated the impact of the contest setting. Working together with three people you're not very familiar with, on a single laptop andunder the pressure of time and competition was harder than I anticipated.
We finished 6th out of 24 teams in our category, by solving two of the five assignments correctly in the 3-hour time span that was given us. We felt we were pretty close to also solving a third one, but didn't manage to weed out the bugs before the end of the contest. After seeing the final ranking (see screenshot), we realized that we were really close to actually winning. If we had managed to solve the third assignment in time, we might have taken 1st place because we had very little punishment time compared to the only team that had three solved assignments. The morning after the contest I finished the assignment we were working on in just 10 minutes on the train ride to work, which makes things even more painful.
Nevertheless, we had fun. The only way we could have been better prepared for such a contest was gaining experience through competing, so we had no regrets. Using another language wouldn't have changed things much, because the emphasis was on the algorithms to solve the assignments and less on the code you were write. Haskell is a very expressive language which is a significant advantage under the pressure of time, and the type system weeds out stupid bugs early, which is again a win in terms of time. Having only one laptop available for 3 people is a huge bottleneck, but something you can learn to deal with by working out assignments thoroughly on paper (something you usually don't do if you have a computer handy).
I haven't decided yet what I'll do next year. Maybe I'll compete again, and if I do I'll again only use Haskell. Another option is to rejoin the team of jury members that design and select the assignments (which is more work but easier than actually competing in my opinion), at the informal request of some jury members. Both sides are interesting, so I'll refrain from making a decision on this for a while longer and enjoy the good feeling I retain from competing in VPW-2011.