Artikel top billede

Lambdabamserne består af Thomas Dybdahl Ahle, Jakob Knudsen og Mathias Knudsen. Til højre er holdets træner Søren Dahlgaard.
Billedet er taget første dag under VM, da holdene fik udleveret t-shirts og de små souvenirkameler, som de fire har sat på skuldrene.

Med landsholdet i programmering til VM: Kodesport gør dig mere præcis

Klumme: Kan man bruge kodesport til noget i den virkelige verden? Tag med på en fascinerende rejse til finalen i verden største kodekonkurrence, hvor Danmark var med for første gang.

Man kan sige, at jeg i sidste måned udgjorde en del af "landsholdet i programmering".

I hvert fald tog Mathias og Jakob Bæk Tejs Knudsen og jeg selv 16-21. maj til Marrakesh, for, som de første danskere nogensinde, at deltage i verdensfinalen af verdens største og ældste kodekonkurrence: "The ACM International Collegiate Programming Contest (ICPC)".

Sammen med Harvard, Moscow State, Beijing Jiaotong, Universidade de São Paulo, og hold fra 123 andre universiteter verden over var vi i en uge bosat på et resort i en 35 grader varm Marrokansk oase. Formål: at kode algoritmer.

Det er ikke første gang, at mit hold, Lambdabamserne, har repræsenteret Københavns Universitet i udlandet.

Faktisk har vi forsøgt at kvalificere os til netop ICPC finalen i fem år, men kun to-tre hold går hvert år videre fra den nordeuropæiske region, som omfatter alle universiteter i Skandinavien, England, Tyskland og Benelux.

Måske også derfor var det en ekstra stor oplevelse at repræsentere sit land mod konkurrenceprogrammeringens usual suspects fra Rusland og Kina, der traditionelt tager alle guldmedaljerne med hjem.

Det gjorde de så også i år, og vi endte på en delt 64'ende plads. Men hvordan gjorde de det egentlig? Og kan man bruge erfaring fra kodesport til noget i den virkelige verden?

Sådan er kodesport

Når vi taler om kodesport handler det typisk om at skrive 30-150 linjers lange programmer, der løser algoritmiske problemer.

Dette er i modsætning til for eksempel de populære hackathons, hvor konkurrenterne laver komplette (web)apps næsten klar til udgivelse.

For hvert af de relativt matematisk betonede problemer får man en sides problembeskrivelse, som man skal fortolke matematisk, løse algoritmisk, kode og typisk debugge.

De gode hold kan nå igennem alle disse faser på 25 minutter i gennemsnit, så selvom hovedet skal holdes helt koldt er der er konstant ekstrem høj adrenalin.

Måske er det dette kick, der gør konkurrencerne så populære i hele verden. ICPC havde i år 40.000 deltagere på verdensplan med 51 hold fra Danmark.

Google, Facebook og andre holder pendanter, der årligt eller ugentligt trækker titusindvis af programmører. Vil du prøve det selv, er det bare at sætte to timer af en lørdag på for eksempel codeforces.com.

Begyndte i gymnasiet

Personligt blev jeg interesseret allerede i gymnasiet. Det var en mere praktisk hobby at skrive en-sides programmer end store programmer, der skulle dokumenteres, oversættes, promoveres og så videre.

Det er selvfølgelig også spændende, men jeg følte nok, at jeg udviklede mig hurtigere ved at fokusere på det mest mentalt udfordrende.

Mathias og Jakob kommer begge fra en primært matematisk baggrund, men jeg tror, de nyder, hvor nemt computere kan levendegøre ideer og gøre dem praktisk anvendelige for milliarder af mennesker.

Når det er sagt, kan vi nok ikke undsige os for, at det sportslige aspekt gør det hele en lille smule sjovere.

Med sport følger også strategi og taktik.

Ankomsten til Marrakech

Lambdabamserne ankom, ligesom de andre hold, til Marrakech næsten en uge inden den egentlige konkurrence.

For nogle hold var det vigtigt for at afhjælpe jetlag, men for os var det tid, vi kunne bruge på at træne. Eller var det smartere at slappe af mentalt og snakke med alle holdene fra de andre regioner?

Holdet fra Cape Town havde været med året før også - deres universitet har domineret regionen "Afrika syd for Sahara" så længe, nogen kunne huske.

Alligevel var deres mål langt mere beskedent end trofæet og de 16.500 dollars. De ville være afrikanske mestre!

Et hold fra Iowa var mindre ambitiøse, men de blev pisket frem af deres træner fra Bangladesh. I den anden ende af skalaen så vi næsten aldrig de russiske hold - bortset fra når de sad rundt om borde med adskillige trænere og analytikere og planlagde minutiøst.

Også det koreanske hold var velforberedte - de medbragte en hel sportstaske fyldt med kopnudler hjemmefra.

Dress rehearsal

Efter et par dage med sightseeing, pool, brætspil og tech talks fra IBM var det tirsdag tid til "dress rehearsal".

Vi skulle afprøve "indmarchen", røre ved trofæet "for good luck" og mest vigtigt: teste om alt på computeren virkede som det skulle.

Efterfølgende var der en del spørgsmål som "kan vi få mere end 8 MB java stack space?", "må vi få tasteturet med hjem og træne?" og "hvor er der kaffe".

Til hvilke svarene fra en noget træt professor gone tekniker lød: "Nej", "Nej, vi annoncerede modellen i februar, så I kunne købe jeres egen kopi" og "I downtown Marrakech".

Konkurrencen er i gang

Næste dag var vi klar. Da vi gik ind i konkurrencesalen så vi straks se at der ville være 13 opgaver at løse. Der var nemlig godt tusind oppustede balloner i 13 forskellige farver, som blev givet til holdene, der skulle løse et tilsvarende antal opgaver.

I ICPC formatet er det meget vigtigt at løse de nemmeste opgaver først, da man får "strafpoint" for hver opgave svarende til tiden fra start til opgaven blev accepteret.

Ballonerne hjælper med at opdage, hvad der er nemmest at løse, men de kan også nemt skabe en flokmentalitet, hvor mange hold aldrig læser faktisk nemme opgaver, fordi få andre har løst dem.

I løbet af de fem timer, konkurrencen varede, blev vi sat over for mange interessante problemer.

For eksempel at skrive et program, der skærer en hullet ost i lige tunge skiver, at finde tidspunktet hvor to asteroider har størst overlap (så de er nemmere at skyde ned), og at skrive et program, der udleder evolutionære hypoteser på baggrund af dna fundet i fossiler.

Osten gav os grå hår

Det var især opgaven med osten, der gav os grå hår. Vi havde et simpelt 50 linjers C++ program, der læste noget input og lavede et antal binære søgninger over en geometrisk formel, vi havde udledt.

Det er nemt at bevise korrekt og effektivt, og efter at have testet det på en række håndlavede testcases, smed vi det op på testserveren. Og ventede. Efter få sekunder fik vi svaret ... "Wrong Answer"!

Med træning er vi blevet temmelig effektive til at gennemskue og løse de forskellige opgaver, men lige som i den virkelige verden er det ekstremt frustrerende under en stram deadline at opdage en fejl og ikke have nogen ide om, i hvilke situationer den opstår.

Når det sker, forsøger vi typisk en kombination er følgende:

Print koden og debug den i hånden

Med de forskellige funktioners kontrakter og invarianter i tankerne, kan en anden person ofte fange de klassiske "off by one", "int overflow", "forkert initialiseret hukommelse" og så videre.

Skriv testkode

Det er typisk nemt at generere udtømmende eller tilfældige testcases i små størrelser. Hvis svarene kan tjekkes manuelt eller af et simplere program end det originale, virker denne metode ofte rigtig godt.

Læs problemet igen og start forfra, gerne i et andet programmeringssprog

Da de to første metoder ikke virkede i vores tilfælde, er dette nok, hvad vi burde have gjort. Det kan dog være frustrerende, når tiden er knap, og man kun har en computer til rådighed.

Beslutninger om fejlfinding er eksempler på de strategiske valg i konkurrencer som ICPC.

De russiske og kinesiske hold har deres egen kodesports-liga, hvor hold hver uge konkurrerer i samme format som den konkurrence, vi deltog i.

Fascinerende præcision

Måske af den grund var det mest facinerende for mig i Marokko ikke, at vinderholdet lykkedes at løse alle 13 opgaver, hvoraf flere var af en sværhedsgrad så de kunne være blevet udgivet ved en konference, men at se i pointsystemet, hvornår de gjorde det:

Hver opgave faldt med næsten præcis 20 minutters mellemrum. Kun to gange havde de fejl, og fejlene blev fundet og rettet inden for få minutter. Selv i den frygtede geometri med sine uendelige hjørnetilfælde. Respekt.

Spændende om de var mindre afslappede, da de forleden stod ret foran Putin i Kreml.

Kan det bruges?

Man fristes til at tænke, om man også kunne opnå mere tempo og præcision i større softwareprojekter med en mere matematisk kølig tilgang.

Google har lavet undersøgelser, der viser, at folk, der deltager meget i kodekonkurrencer, skriver kode, der er sværere at vedligeholde.

Alligevel bruger Google i høj grad deres egen "CodeJam" til rekruttering, og mange virksomheder har interview, hvor kombinationen af problemløsning og implementering minder meget om kodekonkurrencer.

Så burde endnu flere softwareudviklere tage kodesport op som hobby? Jeg håber i hvert fal, at nye kræfter vil tage over i Lambdabamserne og skaffe Danmark nogle guldmedaljer!