Hjem
Click

Algoritmer

# Hash Code by Google ved UiB

Problemløsning for YouTube

Studentene satte profesjonelle fra IT-bransjen helt i skyggen da Google Hash Code 2017 gikk av stabelen torsdag. Det er første gang programmeringskonkurransen, som er åpen for alle i Europa, Midtøsten og Afrika, blir arrangert ved UiB. Konsentrasjonen i rommet er til å ta og føle på det ene øyeblikket; et vilt jubelbrus høres plutselig det neste. - Vi leder! Vi leder! ropes det. Når Hash Code omsider er over har det vært en reise gjennom endeløs frustrasjon, forsiktig optimisme, plutselige åpenbaringer av egen utilstrekkelighet, og sist men ikke minst: adrenalin-kick og overstadig lykkerus.

Moomin, Google Hash Code UiB 2017

Moomin konsentrer seg. Fra venstre: Adrian Reithaug, Jan Knížek og Andreas Vikne.
Moomin konsentrer seg. Fra venstre: Adrian Reithaug, Jan Knížek og Andreas Vikne.
Foto:
Fredrik Lygre Bergesen

 - En programmeringskonkurranse utenom det vanlige
Temaet for årets konkurranse var optimering for YouTube. For å klare å spille av film hurtig til tusenvis av folk i forskjellige områder, er YouTube avhengig av å lagre filmene i nærheten av hvor dem som ønsker å se filmen befinner seg; filmer som nordmenn kunne tenke seg å se er det lurt å lagre i Norge, mens filmer på Swahili er lurere å lagre i Afrika. Å bestemme nøyaktig hvilke filmer som er lurest å lagre hvilke steder er imidlertid ikke helt enkelt å bestemme, siden det er begrensninger på hvor stor lagringsplass de ulike datasentrene har, og ulike filmer har ulike filstørrelser. Oppgaven til deltakerne går ut på å bestemme i hvilke datasentre det er best å lagre de forskjellige filmene, gitt informasjon om hvem som ønsker å se dem.

 - Hash Code er en programmeringskonkurranse litt utenom det vanlige, forteller 3. års-student Kristian Rosland. - Dette er første konkurranse vi deltar i hvor løsningen ikke nødvendigvis er den optimale løsningen, men som heller gir poeng etter hvor gode svar løsningen gir. Det var som om konkurransen var generert for å etterligne realistiske data.

Strategiene var mange og kreative, og inkluderte alt fra en tilfeldig tilordning og såkalt "grådige" algoritmer, til avanserte adapsjoner av "Knapsack," en lur algoritme for å angripe et generelt sett svært vanskelig problem. Mange opplevde at de beste svarene tok alt for lang tid å regne ut, så man måtte klare seg med et dårligere svar på kortere tid. Ett lag ventet på programmet sitt over én time før de gav opp håpet om at et svar ville dukke opp før konkurransen var over. 2. års-student Knut Anders Stokke fra laget BingFanclub forteller at mye tid gikk med på å endre parametere manuelt og så vente på at resultatet ble klart. - Hadde vi implementert en modul som regnet ut poengsummen inne i programmet vårt, kunne vi latt algoritmen selv bestemme de beste parameterne, for eksempel ved hjelp av binærsøk. Kanskje en idé å ha i mente til neste år?

Gode resultater
Det beste laget fra Bergen ble likevel nettopp BingFanclub, som endte som nest beste lag i Norge med hele 1 998 651 poeng, usle 24 789 poeng bak vinneren TrollPick. En fellesnevner for de beste lagene var at teamarbeidet fungerte godt. - Først delte vi laget i to, forklarer lagmedlem Kristian Rosland. - To av oss begynte å implementere innlesing og passende datastrukturer, mens de to andre begynte å tenke på mulige løsninger. Så implementerte vi den beste ideen vi hadde så langt. Med litt finjustering av parametere klarte vi til slutt å klatre helt til topps.

Den gode innsatsen gjorde også at GDG Bergen + Universitet i Bergen utmerket seg som beste hub i landet, med både bedre oppmøte og bedre resultater enn erkerivalene i GDG Oslo. - Vi er svært fornøyde med resultatene, forteller arrangør Torstein Strømme, stipendiat ved Institutt for Informatikk. Han måtte selv se seg slått av flere studentlag. - Jeg er utrolig stolt når jeg ser hvor flinke studentene blir av å studere her. Det er bare å applaudere. Vi er heldige som har et godt studentmiljø slik at arrangement som dette blir vellykkede og lærerike.

Samarbeid med IT-bransjen
Arrangementet var et samarbeid mellom Institutt for Informatikk og GDG Bergen (Google Development Group), og lag fra både IT-bransjen og studenter deltok. Øverst på resultatlisten dominerte riktignok studentene, og man måtte ned til sjetteplass for å finne det første laget med profesjonelle. - Jeg var flink til å programmere en gang, men etter mange år i arbeidslivet har nesten alt kokt ned til anvendelse av boilerplate. Man slutter å tenke like kreativt, sier en av de yrkesaktive deltakerne. Samtidig var stemningen god, og flere av lagene var revansjelystne. - Det var vanskelig, utfordrende og gøy. Utrolig flinke studenter. Til neste år skal vi forberede oss enda bedre, oppsummerer arrangør Håkon Nilsen fra GDG Bergen.