Bericht van GoT: Programming Contest

Inleiding

Na 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.

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.

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.

	Taal		Deelnemers
	C++		Arjan, hij, Soultaker,H!GHGuY
	C#		Arty_shock, Fiander
	Java		cobratbq, DaCoTa, Nick The Heazk, wwwhizz, zwippie
	PHP		EdwinG
	Visual Foxpro		KoW
	C		Robber
	VB.NET		Serpie
	R		veldsla

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:

	Naam		Score
	Soultaker		331
	Kow		448
	zwippie		470
	wwwhizz		626
	Arjan		694
	Marcj		714
	Arty_Shock		757
	Fiander		764
	EdwinG		899
	cobratbq		1282
	H!GHGuY		1453
	hij *		1673
	Nick The Heazk		1728
	hij		1780
	DaCoTa		1864
	Robbbert		1881
	Serpie		1881
	veldsla		1881

*) 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.

Het 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)

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 ...

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?

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

Leuke wedstrijd en leuk verslag!

Bericht van GoT

Donder-en-bliksem, "Femme is jullie nieuwe spirituele leider." werd er vanuit des hemels geschreeuwd

Leuk

Leuk idee die programming contests. Zal is kijken of ik wat in elkaar kan knutselen.