David Baakman

Benelux Algorithm Programming Contest 2006 verslag

Zaterdag, 07:00. De wekker gaat. Nog vroeger dan door de week keer ik me geroutineerd om en druk op de snooze-knop. Achtien minuten later is het dan echt zo ver: vandaag gaat het gebeuren.

Na maanden (soms wat meer dan anders) oefenen is vandaag de wedstrijd: in 5 uur tijd zoveel mogelijk (efficiente) algoritmes halen uit de opgaven die als luchtige verhalen gepresenteerd worden, en deze omzetten naar werkende code.

Samen met twee collega’s (Maarten en Robbert) naar Leiden gereden en na een parkeertechnische uitdaging (kuch..) kwamen we rond half tien binnen. Na een kop thee, en het laatste team-overleg was de opening: veel te harde muziek (nou ja, de muziek was niet te hard, de boxen waren te zwak…), een DVDtje met een vantevoren toespraak van iemand die er niet bij kon zijn omdat hij nu in Canada zat en daarna een korte uitleg.

Om 10:30 begon de test-sessie: een oefen-gedeelte waarbij iedereen wat kon testen. Dat was wel een noodzaak: tijdens de test-sessie kwamen we (en eigenlijk alle andere teams) tot de ontdekking dat de PC’s die we ter beschikking hadden (1 per team) dusdanig traag waren dat het draaien van Eclipse echt totaal niet tot de mogelijkheden behoorde. We verlangden naar onze eigen ontwikkel-laptops waarop Eclipse al niet al te snel op draait. Ja, zelfs de meegenomen demo-laptop die die dag niets anders zou doen dan Powerpoint slides afspelen zou een wenselijke ruil zijn geweest. Maar helaas: ons werd te kennen gegeven dat ze ons maar adviseerden om vi of emacs te gebruiken, dus de enige ruil was een ruil van een IDE naar een teksteditor (nedit).

Nadat we om 10:45 uit pure frustratie van het wachten (we hadden inmiddels Eclipse opgestart en we waren op het wachten op de creatie van een nieuwe class…) de PC maar hadden gereset bleek dat ie standaard Windows opstartte (dat zou voor productiviteit wel een verbetering zijn geweest, maar we moesten Linux gebruiken). Dus na wat hulp van iemand van de ‘system committee’ konden we om 10:50 in ieder geval beginnen.

Dit keer dus met nedit als editor: geen templates, geen compile bij het opslaan van het bestand, geen shortcuts om op te slaan en te copy-pasten (om een of andere reden werkten Ctrl-S/C/V niet, terwijl die opties wel in het menu aangegeven waren, maar ja, dat zou natuurlijk ook wel te gebruiksvriendelijk zijn….), geen Ctrl-Shift-O om alle imports goed te zetten, geen Ctrl-shift voor auto-complete, geen debugging, geen compile-fouten die je ziet terwijl je aan het editen bent. Aan de ene kant besef je dat je normaal gesproken toch wel verwend bent met die features, maar aan de andere kant: komop zeg, ‘t is 2006…

Net een paar seconden na 11:15 submitten we onze laatste test-opgave, waardoor die niet meetelt. Niet erg natuurlijk, maar we hadden liever nog wat extra tijd gehad om nog een aantal dingen te testen: wat gebeurt er met excepties die we gooien, kunnen we veilig naar de stderr printen? Maar anyway, we hebben de test-tijd nuttig gebruikt om vast te stellen dat:

1) Eclipse een complete no-go is

2) De dvorak indeling zowel in KDE als in Gnome in te stellen is en werkt

3) We programma’s succesvol kunnen submitten

4) De Scanner-class toch wel erg handig is (met dank aan Topdesk Orange) (Tsja, dat komt ervan als je normaal gesproken met Java 1.3 werkt, dan ken je die nieuwerwetsche technologie natuurlijk niet zo goed…).

Over het team dat naast ons zat gesproken. Voor de wedstrijd hadden we besproken welke boeken we mee zouden nemen. In z’n algemeenheid heeft veel boeken meenemen niet zo veel zin: wanneer je tijdens de wedstrijd dingen in boeken moet gaan opzoeken ben je eigenlijk toch te langzaam. Maar aan de andere kant: soms kan je een algoritme in 1x zo overnemen. Dus het heeft eigenlijk alleen nut om materiaal mee te nemen waarvan je de inhoud al kent, maar waarvan je misschien code kunt kopieren. We hadden nog even overwogen om Knuth’s The Art of Computer Programming mee te nemen voor de psychologische oorlogsvoering. Waarschijnlijk dachten onze buren er precies zo over, maar wat bij ons bij een plan bleef, kwamen zij tot een uitvoering. Dus 10 seconden na de start van de oefen-ronde stonden de 3 delen pontificaal naast de PC van de buren (nee, volgens mij hebben ze de boeken niet ingekeken). Nou ik moet zeggen: de psychologische oorlogsvoering werkt…

Na een korte pauze begon om 12:00 dan echt de wedstrijd. We hadden als tactiek om eerst per persoon de opgaven door te nemen om zo de makkelijkste opgaven te identificeren, en daarna afwisselend paarsgewijs te werken: op die manier kan je parraleliseren en heb je toch de voordelen van pair-programming. We hadden al snel het makkelijkste probleem geidentificeerd (dus dat gedeelte van de tactiek werkte…), en Maarten en Robbert gingen deze uitwerken. Tegelijk ging ik een andere opgave op papier uitwerken. Helaas werkte de uitwerking van onze opgave niet direct (het algoritme was wel correct, maar een kleine slordigheid, zo bleek twee uur later) en maakte ik bij de andere opgave een stomme fout om te denken dat het probleem door middel van backtracking opgelost moest worden, terwijl het achteraf helemaal niet nodig was (achteraf had ik een aantal zelf bedachte test-cases handmatig moeten uitwerken om erachter te komen dat bij een keuze altijd de eerste/laatste genomen moest worden (of dat natuurlijk wiskundig moeten beredeneren; hoewel ik wel zo pragmatisch ben om dan meteen te zeggen dat de eerste manier makkelijker, en dus sneller is)).

Maar goed, de eerste anderhalf uur ofzo zijn we dus bezig met deze problemen. Ik loop enigzins vast met mijn probleem en ik zie dat veel andere teams inmiddels de laatste opgave al goed hebben: dat probleem moet dus makkelijker oplosbaar zijn dan we in eerste instantie aannamen. Ik besluit om aan dat probleem te gaan werken en zie al vrij snel de truc die je moet uithalen om het probleem in eindige tijd op te lossen. Maarten haalt nog wat essentiele bugs uit het algoritme (niet het minimum getal uit de matrix pakken, maar de minima optellen van de horizontale en vertikale optellingen… detail… detail… :)). Rond het zelfde moment vinden we het probleem in de eerste opgave, en zo rond half drie / drie uur hebben we twee opgaven goed.

De laatste twee uur zijn wat minder successvol: we gaan verder met het eerste probleem waarbij we uiteindelijk tot een implementatie komen die dus achteraf onnodig gebruik maakt van backtracking (sorry Maarten, maar ja, backtracking wordt pas in deel 4 van ‘The Art of Computer Programming’ besproken ;)) die daardoor te langzaam is (oh, en bovendien niet helemaal bug-vrij is..). Ik heb nu nog niet gekeken naar de code en naar de aanpassingen die we zouden moeten doen om de backtracking te vervangen door een straightforward keuze, maar ik denk dat het vrij triviale aanpassingen zouden zijn.

Verder pakken we nog een ander probleem op die we gewoon goed oplossen, maar niet snel genoeg. We krijgen bij het inzenden dus een time-out. En dat terwijl we bij het bedenken van het algoritme toch serieus gekeken hebben naar de O.

Tijdens het laatste uur worden de scores op het scorebord niet meer geupdate, je kan dus niet meer zien of anderen die op dit moment nog onder je staan inmiddels een extra opgave goed hebben. Dat maakt het allemaal wel een stuk spannender, en levert ook weer extra stress op. Achteraf gezien niet nodig, de enigen die in het laatste uur een opgave goed hadden stonden boven ons en bleven boven ons, of stonden onder ons en bleven onder ons. Zowieso: in het laatste uur zijn in totaal 15 van de 100 goede opgaven ingeleverd, zelf had ik meer ‘actie’ verwacht in het laatste uur.

We blijven uiteindelijk dus op twee goede antwoorden steken. Wanneer we de ranglijst bekijken zien we dat dat maar 1 opgave minder is dan de winnaars Eljakim (gewonnen zoals verwacht, resultaten uit het verleden bieden dan wel geen garanties, sterke indicatoren zijn het meestal wel…). Uiteindelijk een 5e plek van de 12. Lang niet erg slecht dus, maar achteraf had er meer ingezeten. Zowel qua aantal goede opgaven, maar ook qua tijd: we hebben in het begin te veel tijd verloren in de makkelijke opgaven, waardoor we net iets te weinig tijd hadden voor de gemiddelde opgaven (de moeilijke opgaven hebben we goed weten te vermijden, dus dat is in ieder geval goed gegaan).

Bij het nabespreken is er nog de mogelijkheid om een gokje te wagen in een verloting van een Dell Inspiron 6400 die door Dell weggegeven wordt aan de persoon wiens antwoord het dichtste bijzit bij het aantal bytes van de 10e goede inzending na 4 uur. Mijn gok van 3600 bytes zit er ongeveer 500 bytes naast, wat een marge van een factor 10 te groot is.

Na nog wat meer nagesproken te hebben tijdens het eten gingen we weer huiswaards. Na zelfs met een TomTom in de hand een doodlopende straat te hebben bezocht vonden we uiteindelijk toch nog de auto terug, en tijdens de terugreis leek het erop dat het stuk om uit Leiden weg te komen een stuk korter was dan het stuk om Leiden binnen te komen (kuch… ik trap er nog steeds in: TomTom zegt: na 300 meter linksaf, ga ik de eerste linksaf, en rijd dus zo wel de juiste snelweg op, maar dan wel de verkeerde kant op…, en dat is niet handig wanneer je 1 km voor Leiden zit…). Uiteindelijk laat TomTom ons ook nog een touristische route rijden om in Lunetten te komen (helemaal via de oost-kant van de ring van Utrecht) (nee, ik was niet verkeerd gereden: Maarten bevestigde dat ik precies de instructies had opgevolgd), maar goed, uiteindelijk kwamen we dan toch nog weer heelhuids terug.

Globaal terugkijkend kijk ik terug op een leuke dag. Met de 2 goede opgaven ben ik gematigd tevreden. Het is gelukkig niet op een totaal drama uitgelopen, maar er had wel meer ingezeten, maar voor een eerste keer is het niet een heel slecht resultaat. We kunnen natuurlijk wel de schuld neerleggen bij het feit dat we geen Eclipse konden gebruiken en daardoor veel onnodige tijd kwijt waren met het oplossen van compileerfouten die niet met Eclipse zouden zijn opgetreden, maar dat zou te makkelijk en te flauw zijn :) (maar wel een punt voor de organisatie: wanneer je het hebt over 256 MB geheugen, dan heb je het anno 2006 niet meer over het complete werkgeheugen van een PC, maar over het geheugen op een mid-end videokaart, of het cache geheugen van een mid-end I/O-controller). In 1999 had mijn PC 256 MB geheugen (dat is meer dan 7 jaar geleden!), en dat mijn ontwikkel-laptop 1 GB geheugen heeft komt niet doordat dat leuk staat, maar dat is gewoon broodnodig. De machines waren amper in staat om KDE / Gnome te draaien, zelf met alleen een browser, 4 instanties van nedit, en een shell was de PC al niet vooruit te branden en duurde het vaak vele seconden om van venster te wisselen, dat is echt jammer. En ook onnodig denk ik: zo moeilijk kan het toch niet zijn om op een universiteit een stuk of 40-50 capabele machines te regelen voor een zaterdag? Hoewel, de UL daar in 1997 toen ik daar een paar keer voor een masterclass chaostheorie was ook al redelijke problemen mee had. Dit soort zaken zijn geen goede reclame, en was voor mij toendertijd in ieder geval een reden om de UL niet op m’n shortlist te zetten van studiekeuzes.)