Se C++-koden: Sådan blev Lambdabamserne danske mestre i programmering

'Lambdabamserne' fra DIKU var overraskede over at vinde DM i Programmering 2010. Nu venter en europæisk programmeringskonkurrence på de tre studerende til november.

Det var en helt uventet sejr for holdet 'Lambdabamserne' fra Datalogisk Institut ved Københavns Universitet, DIKU, da de lørdag den 2. oktober løb med sejren i DM i Programmering 2010.

»Det var en glædelig overraskelse, for vi synes ikke selv, at det gik så godt,« siger ét af de tre medlemmer af Lambdabamserne, den 20-årige datalogistuderende Søren Dahlgaard, til Version2.

Lambdabamserne vandt den danske konkurrence med fire korrekte besvarelser på i alt 11 algoritmiske problemer, navngivet fra A-K.

**LÆS OGSÅ **Lambdabamserne vinder DM i Programmering 2010

Udover Søren Dahlgaard består holdet af Mathias Bæk Tejs Knudsen, 18 år, og Sebastian Paaske Tørholm, 22, der læser henholdsvis Matematik og Datalogi, og Matematik på DIKU.

Søren Dahlgaard fortæller, at holdet havde løst fire opgaver, A, D, F og G, korrekt efter at den første af konkurrencens i alt fem timer var gået.

Herefter gik tiden med at forsøge at løse de resterende problemer, som var mere komplicerede.

Decimalfejl forpurrede femte korrekte svar

Men en irriterende detalje viste sig at stå i vejen for flere korrekte besvarelser end de fire.

»Resten af tiden kløjes vi desværre i de andre opgaver. NCPC's (den konkurrenceansvarlige, red.) testsystem blev ved med at fortælle os, at den uploadede kode til opgave I ikke var korrekt. Efter konkurrencens afslutning fandt vi ud af, at vores løsning til opgave I nok var korrekt, men at vi havde glemt at angive output med tre decimaler, så det var ret ærgerligt,« siger Søren Dahlgaard.

De fire korrekte besvarelser, hvoraf A, D og F var de nemmeste opgaver, var dog nok til den samlede sejr på dansk jord i konkurrencen, der samtidig blev afholdt i Norge, Sverige og Finland som en del af konkurrencen Nordic Collegiate Programming Contest (NCPC) for studerende i hele Norden.

De tre tilladte programmeringssprog var C, C++ og Java, og Lambdabamserne løste opgaverne D, F og G i C++, som er to af de tre studerende favoritsprog, mens løsningen til opgave A blev skrevet i Java.

»Vi har ikke skrevet noget objektorienteret kode, men har alligevel brugt C++, fordi vi både kan skrive ren C i det, men samtidig har mulighed for eksempelvis at hente en prioritetskø eller andre funktioner fra C++'s standardbiblioteker,« siger Søren Dahlgaard.

Turen går til europæiske konkurrence

Pengepræmien på 10.000 kroner skal bruges til at dække rejseudgifterne, når de tre DIKU-studerende 19.-21. november befinder sig på Jacobs University i Bremen i Tyskland for at forsvare de danske farver ved konkurrencen Northwestern European Regional Programming Contest 2010.

Og navnet Lambdabamserne?

Det stammer fra 2010-udgaven af den årlige revy på DIKU, hvor figuren Highscore-Kaj snakker om sine 'lambdabamser', i stedet for de 'lamsebamser', Score-Kaj omtaler i det oprindelige DR-børneprogram af samme navn, fortæller Søren Dahlgaard.

Ordet Lambda er i sammenhængen en henvisning til lambda calculus ? en formel matematisk måde at beskrive funktioner på.

DM i Programmering blev arrangeret af it-virksomheden Netcompany og afholdt på Datalogisk Institut, Aarhus Universitet, og på DTU i Lyngby. I alt 27 hold med 2-3 personer deltog i konkurrencen.

Her følger formuleringen samt Lambdabamsernes svar på konkurrencens opgave G, 'Great Geek Game-show 3000!'

Yes! You've finally been chosen to participate in the "Great Geek Game-show 3000".

This is the moment you've been waiting for, ever since you puzzled out how to maximise your chances of winning. You will finally be rich, and able to buy all the algorithm books you want!

Of course you will have to share the winnings with the other contestants, but since your algorithm is vastly superior to the randomness of all the other numb-skulls you are certain you will be able to keep most of the prize money for yourself, in exchange for telling them how you can all maximise your chances of winning.

The rules of the game are the following:

There is a stage with N boxes, each containing the name of one of the N contestants, and such that each contestant has their name in exactly one box. The contestants enter the stage one at a time, and each one is allowed to peek inside K of the boxes. If they find their own name inside one of these boxes they can get off the stage, and the game continues with the next contestant. If all contestants find their own name, everyone wins.

But if one contestant fails to find theirs, everyone loses. After the game has begun, no communication between the contestants is allowed. However you are all allowed to agree upon a strategy before the game begins, and this is where you explain to all the others that the algorithm of everyone choosing K boxes at random is a very bad one, since it gives a chance of winning only equal to (K/N)^N.

Instead you suggest the following algorithm:

Assign to each player and each box a unique number in the range 1,?, N. Then each player starts with opening the box with the same number as themselves. The next box the player opens is the box whose number is found inside the first box, then the box whose number is found inside the second box, and so on. The process goes on until the player has opened K boxes, or found their own number.

Now to bring home your point of how superior your algorithm is, you will need to calculate the exact odds of winning if all the contestants follow your directions. Unfortunately, this is the only thing you haven't figured out yet?

Input specifications
One line with the following numbers:
1 <= N <= 10000000 - the number of contestants.
1 <= K <= N - the number of boxes each contestant may check.

Output specifications
The chances you have of winning if everyone follows your algorithm.

Lambdabamsernes svar på opgave G (C/C++):

#include  #include  #include  #include  using namespace std; **int **main() {         **int **N;         **int **K;         cin >> N;         cin >> K;         **if**(N == K) { cout << 1 << endl; **return **0; }         queue<**double**> koe;         **for**(**int **i=1;i<=K;i++) {                 koe.push(1.0);         }         **double **s = (**double**) K;         **int **i = 1;         **while**(1) {                 **double **t = s/((**double**)(i+K));                 **if**(i+K == N) { cout << t << endl; **return **0; }                 **double **b = koe.front();                 koe.pop();                 s = s-b+t;                 koe.push(t);                 ++i;         } }

De tre resterende, korrekte besvarelser kan ses her: Opgave A, opgave D og opgave F.

Det samlede scoreboard kan ses her, og opgaveformuleringerne her.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (5)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Kurt Mielke

Løsningen er meget elegant, da den er økonomisk med pladsen, men denne linje:

s = s-b+t;

giver problemer. Hvis man kører programmet på et belastende input som 1000000 1000, så giver den en negativ sandsynlighed, Det skyldes, at i starten er s tæt på 1, lad os i decimaltal sige 1/3 så er det ca 0,333..3 i alt 18 tretaller. Men når vi når ud og regner de helt små tal omkring 10^-20, så mangler vi "de tretaller vi smed væk". Sagt på en anden måde, for at dette skal virke, og man kan beregne en lille sandsynlighed, skal man have lidt flere betydende cifre i sin "double" end der er cifre efter decimalkommaet i det endelige resultat.

Jeg kan ikke lige se en vej, uden at gemme alle "t'erne" i koden ovenfor. Men for de sample values der var i opgaven, virker koden jo fint:-)

  • 0
  • 0
#2 Simon Friis Vindum

... gives a chance of winning only equal to K^N/N.

Nogen der kan forklare den udregning? Jeg kan ikke få den til at give mening. F.eks. hvis K er 4 og N er 15, får jeg 4^15/15 til 71582788,2666667..

  • 0
  • 0
#3 Torben Mogensen Blogger

Der skulle nok have stået K^N/N^N: Hver deltager har (ved tilfældige valg) K/N chance for at finde eget navn. Chancen for at alle deltagere finder deres navn ved tilfældige valg er derfor (K/N)^N = K^N/N^N.

Problemet er i øvrigt en variant af "de hundrede fanger" (http://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_p...), og man kan på samme side finde formler til beregning af sandsynligheden.

  • 0
  • 0
#5 Deleted User

Hej Simon -

Undskyld. Det er min fejl. Kopiering af tekst fra et PDF-dokument (opgaveformuleringen) til vores CMS var ikke bare så nemt som ctrl+c, ctrl-v, og jeg er efterfølgende kommet til at 'rette' artikelteksten forkert til.

Det er ganske rigtigt (K/N)^N, og ikke K^N/N. Jeg har nu rettet teksten.

Mvh Mikkel, v2.dk.

  • 0
  • 0
Log ind eller Opret konto for at kommentere