Door Peter de Boer

Doktersteam

Bericht van GoT: Programming Contest

Inleiding

Programming-forumNa het laatste Bericht van GoT over de overklokwedstrijd in het TCA-forum, besteden we ditmaal aandacht aan de 'Programming Contest' die in de afgelopen maanden in de Devschuur is gehouden. Het idee van een wedstrijd in het Programming-forum op GoT is niet nieuw. In het verleden zijn er diverse initiatieven geweest die of een vroege dood gestorven zijn, of juist geen duidelijk einde kenden. De Devschuur-crew besloot enige tijd geleden wedstrijden binnen Programming nieuw leven in te blazen.

De eerste wedstrijd 'nieuwe stijl' ging in november 2006 van start en kon op enthousiaste reacties rekenen. De bedoeling van deze wedstrijd was het schrijven van een Tetris-achtig programma zonder gebruikersinteractie. Het programma moest zelf zo goed mogelijk de aangeleverde blokjes wegspelen. Naast de uiteindelijke score zijn ook de kwaliteit en netheid van de code onderwerp van nauwkeurige inspectie door de devschuur-moderators geweest. Uiteindelijk leverden acht deelnemers voor de deadline een oplossing in. Na het draaien van alle programma's was er een duidelijke winnaar: Marcj had met ruim 2,8 miljoen punten een mijlengrote voorsprong op naaste concurrent zwippie. De vele uren die hij er in gestoken heeft leverden hem dus de beloofde roem op, temeer omdat zijn code ook met het hoogste cijfer werd gewaardeerd.

Tetris-voorbeeld Programming Contest I

Gezien de positieve reacties van zowel toeschouwers als deelnemers was het al snel duidelijk dat er een tweede wedstrijd georganiseerd zou worden.

Programming Contest II

Op 26 februari ging de tweede wedstrijd nieuwe stijl van start. Het was deze keer de bedoeling om te gaan puzzelen, puzzelen met woorden om precies te zijn. Door de organisatie werd een bestand met enkele duizenden woorden aangeleverd die als een kruiswoordpuzzel in elkaar gepast moesten worden. De woorden moesten zo efficiënt mogelijk geplaatst worden door letters meerdere keren te gebruiken, enigszins vergelijkbaar met het bekende bordspel Scrabble. Woorden moesten zowel horizontaal als verticaal en van links naar rechts en andersom geplaatst worden Het aantal overgebleven letters in de uiteindelijke grid bepaalde de score, waarbij degene met de laagste score uiteraard zou winnen.

Programming contest voorbeeld opdracht 2

De inzendingen - die in elke willekeurige programmeertaal gemaakt mochten zijn - moesten uiterlijk 30 april bij de organisatie binnen zijn. Naast de winnaar in de categorie 'minste punten' waren er nog enkele andere kansen op bewondering van mededevvers, zoals 'snelste code' en 'meest defensieve code'. De winnaars in deze categorieën werden door de crewleden van de Devschuur aangewezen.

Het verloop van de wedstrijd

Na de start was er uiteraard een aantal vragen van potentiële deelnemers, maar over het algemeen was de opdracht voor iedereen duidelijk. Er waren een hoop positieve reacties over de opzet van de wedstrijd, dus dat beloofde veel voor het aantal deelnemers. Ook de winnaar van de vorige wedstrijd meldde zich al snel. Al na een dag wist tomahawks de eerste resultaten te tonen: het filteren van dubbele woorden uit de lijst was hem al gelukt. Het bleek al snel dat meer mensen er voor kozen om eerst de aangeleverde lijst te ontdoen van woorden die ook door een ander woord gevormd konden worden. Het eerste volledige resultaat werd door MarcJ gepost.

EdwinG besloot een andere weg te volgen: hij schreef als eerste een validator om de output van zijn programma op geldigheid te kunnen controleren. Dat dit geen overbodige luxe was bleek wel toen RobIII enkele van de bestanden van MarcJ ging controleren: zonder op details in te willen gaan wist Rob te melden dat de uitkomst niet correct was. Reden genoeg voor Marcj om zelf ook eerst maar een validator te bouwen. Varienaja wist ook al snel enkele resultaten te halen; met een compressie van bijna 40 procent nam hij enkele dagen na de start de koppositie in de voorlopige klassering in. In de dagen daarna werden door veel verschillende mensen voorlopige uitslagen gepost. Het leek er dus al vroeg op dat het uiteindelijke deelnemersaantal dat van de vorige wedstrijd zou overstijgen.

Omdat er al enkele validators waren kon er naar hartelust getest worden met de geschreven code. Een week na de start waren er meer dan vijftien personen die een voorlopige uitkomst hadden. De scores werden ook snel beter: zo wist Soultaker al een compressie van ongeveer 64 procent te halen, een score die vergelijkbaar was met die van Serpie. Deze deelnemer wist en passant ook nog een filmpje te maken van het plaatsen van de woorden door zijn programma. Inmiddels had EdwinG een online validator gemaakt. Hierdoor werd het voor de deelnemers een stukje eenvoudiger om te controleren of de behaalde scores ook overeind zouden blijven na een kritische blik van de validator van RobIII. 6K kan hierover meepraten: zijn indrukwekkende compressie van 75 procent bleek bij nader inzien toch niet te kloppen. Een grote opluchting voor de overige deelnemers die bij het zien van deze score bijna de spreekwoordelijke handdoek wilden werpen.

Gedurende de eerste weken van maart werden steeds betere resultaten behaald door een groeiende groep deelnemers. Helaas verliep de wedstrijd niet voor iedereen probleemloos. Was voor KoW de diefstal van zijn laptop al zuur, nog erger was dat op de laptop ook het programma stond waar hij mee bezig was. Omdat ook de externe harde schijven met de backup deel uitmaakten van de buit, moest hij helemaal opnieuw beginnen. Wellicht traditioneel voor een programmeur is het vele werk dat bij het in zicht komen van de deadline nog verricht moet worden. Verschillende deelnemers moesten in de laatste dagen nog even doorhalen om de code inzendgereed te maken. Terwijl veel mensen in Nederland Koninginnedag vierden, werkten verschillende ploeteraars, zoals Arty_Shock, nog aan de laatste puntjes. Dacota stuurde vijf minuten voor de deadline als laatste deelnemer zijn programma in. Dat het wachten tot het laatste moment niet altijd verstandig is bleek wel voor hij. Hij was vergeten een testwaarde terug te zetten naar de echte waarde waardoor zijn programma slechts zes van de mogelijke 99 grids zou doorlopen.

De inzendingen

Toen de Devschuur-crew op 1 mei de postbus leegde, werd tevreden geconstateerd dat er uiteindelijk zeventien deelnemers waren: ruim het dubbele aantal van de vorige keer. Als die trend zich doorzet belooft dat veel voor de toekomst van de programmeerwedstrijden. Door de deelnemers zijn verschillende programmeertalen gebruikt, variërend van C/C++, C#, Java, PHP, VB.Net tot Visual FoxPro en het exotische R. De populairste taal, met vijf deelnemers, bleek Java.

TaalDeelnemers
C++Arjan, hij, Soultaker,H!GHGuY
C#Arty_shock, Fiander
Javacobratbq, DaCoTa, Nick The Heazk, wwwhizz, zwippie
PHPEdwinG
Visual FoxproKoW
CRobber
VB.NETSerpie
Rveldsla
Een overzicht van de deelnemers en de gebruikte talen.

Na het programmeren was het uiteraard tijd om de inzendingen te beoordelen. Gezien de hoeveelheid deelnemers had dit nog de nodige voeten in de aarde. Devschuur-admin -NMe- had de schone taak de verschillende programma's te draaien en de output te valideren. Dat zelfs een moderator van de Devschuur niet foutloos is, wist RobIII te bewijzen. De door hem geschreven validator moest nog enkele keren aangepast worden om de uiteindelijke scores te kunnen controleren.

Na heel wat uurtjes woorden plaatsen op de computer van -NMe- was het tijd de balans op te maken. Van de zeventien inzendingen wisten er zes alle aangeleverde bestanden binnen de gestelde limiet van een uur te verwerken. Zeven inzendingen moesten afgebroken worden omdat ze niet op tijd klaar waren, en vier programma's leverden een foutmelding op.

Een deelnemer moest helaas gediskwalificeerd worden. De eerste inzending van 'hij' werkte niet goed; er was dus een tweede inzending nodig. Dat is volgens de regels niet toegestaan. Ook de inzending van Soultaker werd in eerste instantie gediskwalificeerd omdat zijn programma er vanuit ging dat de lege outputbestanden al aanwezig zouden zijn. Dit staat niet vermeld in de regels, waardoor besloten werd Soultaker alleen buiten mededinging mee te laten doen. Nadere beschouwing van de regels leerde echter dat het al of niet al bestaan van de outputbestanden onvoldoende duidelijk beschreven was. Na lang overleg werd dan ook besloten de inzending van Soultaker gewoon mee te laten tellen.

In de dagen na het sluiten van de inzendtermijn werd door de deelnemers uitvoerig over de gekozen wegen gediscussieerd. Juist deze discussies zijn natuurlijk een leuke bijkomstigheid van een wedstrijd zoals deze. Opvallend was dat veel van de deelnemers gelijksoortige algoritmes hadden bedacht. Wie uiteindelijk de beste implementatie gemaakt had bleef nog even spannend.

De uitslag

Nadat alle 841 gegenereerde grids door de inmiddels goed werkende validator van RobIII gevoerd waren kon de uitslag bepaald worden. Op de derde plaats is zwippie geëindigd met een score van 470 punten. De deelnemer met de een na hoogste score is KoW geworden, met een totaal puntenaantal van 448. En de winnaar van de tweede GoT Programming Contest Nieuwe Stijl is geworden: Soultaker, met een score van 331 punten en een gemiddelde compressie van ruim 24 procent. Soultaker, van harte gefeliciteerd!

De complete uitslagenlijst ziet er als volgt uit:

NaamScore
Soultaker331
Kow448
zwippie470
wwwhizz626
Arjan694
Marcj714
Arty_Shock757
Fiander764
EdwinG899
cobratbq1282
H!GHGuY1453
hij *1673
Nick The Heazk1728
hij1780
DaCoTa1864
Robbbert1881
Serpie1881
veldsla1881
*) buiten mededinging

Hoewel door de organisatie met nadruk is vermeld dat het bij de wedstrijden vooral gaat om het deelnemen, en er geen prijzen te winnen zijn, heeft het MT van Tweakers.net onafhankelijk van de Devschuur-crew toch besloten eenmalig een prijs ter beschikking stellen. Soultaker kan zijn volgende programma's waarschijnlijk een stuk ruimer zien op zijn nieuwe Samsung 22" breedbeeldmonitor.

Na het draaien van alle programma's zijn door de deskundige jury vervolgens de winnaars in de overige categorieën bepaald. Voor de winnaars in deze categorieën stelt het MT een Tweakers.Net-jaarabonnement beschikbaar.

De snelheid is uiteraard van belang voor het functioneren van een applicatie, degene die dat goed begrepen heeft – en dus de winnaar in de categorie ‘snelste code’ is geworden – is wwwhizz. Een ander belangrijk aspect van het schrijven van goede programma’s is de mate van robuustheid van de code. In dit geval is onder meer gekeken naar de wijze waarop het programma omgaat met het ontbreken van invoerbestanden en corrupte invoer. Niet iedereen hield hier voldoende rekening mee, maar de code van EdwinG, MarcJ, Robbert en KoW was op veel onverwachte zaken voorbereid. De laatste in dit rijtje heeft dit veruit het beste gedaan. We kunnen KoW dus feliciteren met de overwinning in de categorie ‘meest robuuste code’. Als laatste is gekeken naar de algemene kwaliteit van de code. Ieder van de juryleden heeft een cijfer gegeven voor de opzet van de code, de hoeveelheid commentaar en een aantal andere zaken. Dat de totaaloverwinning van Soultaker geen toevaltreffer was blijkt wel uit zijn code. Zijn inzending is in de categorie ‘netste code’ met het hoogste cijfer gewaardeerd. Iedereen van harte gefeliciteerd! De volledige uitslag met de bijbehorende opmerkingen is in het topic op het forum te vinden.

De nieuwe opgave

Omdat de tweede wedstrijd weer een succes genoemd mag worden, zal deze ook een vervolg krijgen. De plannen voor de derde wedstrijd zijn al weer uitgewerkt door de immer actieve crew.

BungalowHet is deze keer de bedoeling de optimale indeling voor de vakantiehuisjes van de crew tijdens de MOAM te maken. Deze meeting neemt een heel weekend in beslag, en er moet uiteraard 's avonds ook geslapen worden. Dit gebeurt in verschillende huisjes in een bungalowpark. Er zijn verschillende typen huisjes te verdelen, en een groot aantal mensen die allemaal hun eigen voorkeuren hebben. Zo zijn er huisjes voor zuipschuiten en huisjes voor mensen die het na elven wat rustiger aan willen doen. Crewleden kunnen ook aangeven met wie ze wel of juist niet in de kamer willen slapen. Het programma dat door de deelnemers van de derde wedstrijd gemaakt moet worden, moet de crewleden zo goed mogelijk over de huisjes verdelen. Hoe beter aan alle voorwaarden voldaan wordt door het programma van de deelnemers hoe meer punten er gescoord worden. De volledige opgave met alle details is te vinden op het forum. We hopen uiteraard op veel deelnemers.

Reacties (30)

Wijzig sortering
Intressanter lijkt mij om leerkrachten met voorkeuren voor bepaalde dagen te verbinden met lesroosters voor bepaalde klassen uit verschillende richtingen. Rekeninghoudend met de capaciteiten van de leerkracht (vakken).
En in welke zin is dat anders dan de opdracht die we al uitgeschreven hebben? En dan bedoel ik in programmeertechnisch opzicht, niet cosmetisch. ;)
Hij is anders omdat voorkeuren van personen voor bepaalde personen zo éh onmeetbaar zijn terwijl leerkrachten maar vijf parameters hebben (weekdagen) en hooguit pak em beet drie vakken kunnen geven. Terwijl je met personen het totaal aantal paartjes aan variabelen hebt. A -> B = 55% , B->A = 30% , B -> C = 20% , C -> A = 80% en het lijkt mij gewoon nogal moeilijk om zoveel data te verzamelen aangezien als ik mij goed herinner jullie met een veertigtal zijn ofzo :)
Ruim 100 zelfs, doorgaans. ;)

Verder zijn er ook wat dingen die het juist weer een stuk makkelijker maken. De verschillende voorkeuren zijn gewogen door verschillende scores, dus dat is gewoon een kwestie van in de meest optimale volgorde overal doorheen lopen. :)
Dat is juist, en punten telling aan de hand van hoe lang het duurt en ...
Anoniem: 196208
23 mei 2007 16:11
Leuk zeg! Ik ga kijken of ik met deze contest wel mee kan doen, want de vorige waren te moeilijk voor me :+ . Trouwens, is een compressie van -288,52 niet vrij laag voor EdwinG? :P
Trouwens, is een compressie van -288,52 niet vrij laag voor EdwinG?
Dat komt, als ik me goed herinner, omdat een aantal grids op een (behoorlijk) negatieve compressie uit kwamen.
Hmm, ik heb nog niet gemerkt dat mijn programma woorden dubbel is gaan plaatsen. Met een behoorlijk negatieve compressie zou ik trouwens nooit het totaal van 899 hebben bereikt.
De nieuwe opgave klinkt een beetje als een van de Spoj opdrachten.
Opzich bedenken we alle contests zelf. Tuurlijk kijken we ook om ons heen maar zaken van anderen zomaar gebruiken doen we niet. Daarnaast is deze opdracht in meerdere varianten uit te voeren o.a. het bekende rooster probleem (die Mr SIS) blijkbaar interresanter vindt. Maar dit komt grotendeels op hetzelfde neer.
Wel stoer: KoW met Visual Foxpro op de 2e plaats én de meest robuuste code geschreven!
:)
Die 2e plaats had ik eigenlijk niet verwacht. Voor mijn gevoel zou ik ergens in de middenmoot uitkomen.
Ik had meer verwacht van mijn algoritme hoewel ik natuurlijk de testomstandigheden niet ken...

Volgende keer beter dan maar.

* H!GHGuY is nog altijd trots op zijn boost::multi_index container driven grid
Niet vergeten dat überhaupt in de uitslagen tabel terechtkomen al een hele prestatie is hoor. Gewoon blijven meedoen!
Leuk dat er extra aandacht aan dit soort projecten wordt gegeven. Gefeliciteerd aan de winnaars! :)

Nu ik bijna klaar ben met afstuderen heb ik misschien eindelijk eens tijd om zelf mee te doen met een wedstrijd. Had bij beide wedstrijden wel ideeen, maar de tijd ontbrak helaas volledig.

* IntToStr gaat vast graven in geheugen mbt lineaire algebra en clustering en zo :9
Leuke wedstrijd en leuk verslag!
Bericht van GoT
Donder-en-bliksem, "Femme is jullie nieuwe spirituele leider." werd er vanuit des hemels geschreeuwd
Leuk idee die programming contests. Zal is kijken of ik wat in elkaar kan knutselen.

Kies score Let op: Beoordeel reacties objectief. De kwaliteit van de argumentatie is leidend voor de beoordeling van een reactie, niet of een mening overeenkomt met die van jou.

Een uitgebreider overzicht van de werking van het moderatiesysteem vind je in de Moderatie FAQ

Rapporteer misbruik van moderaties in Frontpagemoderatie.



Op dit item kan niet meer gereageerd worden.


Nintendo Switch (OLED model) Apple iPhone SE (2022) LG G1 Google Pixel 6 Call of Duty: Vanguard Samsung Galaxy S22 Garmin fēnix 7 Nintendo Switch Lite

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2022 Hosting door True

Tweakers maakt gebruik van cookies

Tweakers plaatst functionele en analytische cookies voor het functioneren van de website en het verbeteren van de website-ervaring. Deze cookies zijn noodzakelijk. Om op Tweakers relevantere advertenties te tonen en om ingesloten content van derden te tonen (bijvoorbeeld video's), vragen we je toestemming. Via ingesloten content kunnen derde partijen diensten leveren en verbeteren, bezoekersstatistieken bijhouden, gepersonaliseerde content tonen, gerichte advertenties tonen en gebruikersprofielen opbouwen. Hiervoor worden apparaatgegevens, IP-adres, geolocatie en surfgedrag vastgelegd.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Toestemming beheren

Hieronder kun je per doeleinde of partij toestemming geven of intrekken. Meer informatie vind je in ons cookiebeleid.

Functioneel en analytisch

Deze cookies zijn noodzakelijk voor het functioneren van de website en het verbeteren van de website-ervaring. Klik op het informatie-icoon voor meer informatie. Meer details

janee

    Relevantere advertenties

    Dit beperkt het aantal keer dat dezelfde advertentie getoond wordt (frequency capping) en maakt het mogelijk om binnen Tweakers contextuele advertenties te tonen op basis van pagina's die je hebt bezocht. Meer details

    Tweakers genereert een willekeurige unieke code als identifier. Deze data wordt niet gedeeld met adverteerders of andere derde partijen en je kunt niet buiten Tweakers gevolgd worden. Indien je bent ingelogd, wordt deze identifier gekoppeld aan je account. Indien je niet bent ingelogd, wordt deze identifier gekoppeld aan je sessie die maximaal 4 maanden actief blijft. Je kunt deze toestemming te allen tijde intrekken.

    Ingesloten content van derden

    Deze cookies kunnen door derde partijen geplaatst worden via ingesloten content. Klik op het informatie-icoon voor meer informatie over de verwerkingsdoeleinden. Meer details

    janee