Nederland verovert vierde plaats in programmeerwedstrijd

Tijdens de jaarlijkse ACM-ICPC-wedstrijd heeft een team van de Universiteit Twente een verdienstelijke vierde plek veroverd en daarmee een gouden medaille en een geldprijs ter waarde van 3000 dollar gewonnen. Het Twentse team wist vijf van de tien programmeerproblemen op te lossen binnen de deadline van vijf en een half uur. Europa domineert de top tien met zeven universiteiten waarvan er maar liefst vijf uit Rusland komen. De eerste prijs werd gewonnen door een team studenten van de Russische Saratov State University, de tweede plek ging naar een team van de Poolse Jagiellonian University en de derde plek werd opgeëist door de Russische Altai State Technical University.

De tien opgaven waren vooral algoritmisch van aard en moesten in C/C++, Java of Pascal worden opgelost. De eerste opgave ging over het uitzoeken hoe het goedkoopst vliegtuigtickets gekocht konden worden, gegeven een of meer trajecten en tickets. Voor opgave twee moesten de minimum en maximum opbrengsten berekend worden voor een cateringbedrijf dat taart met een bolletje ijs levert. Opgave drie liet de studenten berekenen of een bepaald uit bollen opgebouwd kunstzinnig beeld zou blijven staan. De volgende opgave ging over het vinden van het kleinste tweedelige getal dat groter is dan een bepaalde positieve integer.

Voor opdracht vijf moest een bitcompressie-algoritme onderzocht worden op ambiguïteit en vervolgens moest een algoritme ontworpen worden dat op basis van een aantal tandwielen onderzocht of het mogelijk was een goed werkende klok te maken met een minimum aantal assen voor de tandwielen. Opgave zeven ging over het reconstrueren van de groepssamenstellingen van een reis op basis van een eenvoudig inkomsten- en uitgavenoverzicht. Opgave acht was gebaseerd op origami en de deelnemers moesten proberen te berekenen hoeveel holtes in een bepaald vouwproces werden gecreëerd. De maximale afstand tussen twee punten in een ongerichte graaf werd gevraagd in opgave negen en tenslotte werd in opgave tien gezocht naar het minimum aantal punten in een netwerk waarmee een veilig communicatiepad kon worden gemaakt. De opgaves kunnen hier worden gedownload als pdf-bestand.

	Positie		Naam		Land		Opgelost		Tijd
	1		Saratov State University		Rusland		6		917
	2		Jagiellonian University - Krakow		Polen		6		1258
	3		Altai State Technical University		Rusland		5		681
	4		University of Twente		Nederland		5		744
	5		Shanghai Jiao Tong University		China		5		766
	6		St. Petersburg State University		Rusland		5		815
	7		Warsaw University		Polen		5		820
	8		Massachusetts Institute of Technology		Amerika		5		831
	9		Moscow State University		Rusland		5		870
	10		Ufa State Technical University of Aviation		Rusland		5		980

Top-10 ACM-ICPC 2006

Reacties (70)

[davidem]

Europa domineert de top tien met zeven universiteiten...

Volgens mij hoort Nederland toch echt bij Europa en komt de uni teller daarmee op acht... (5 Russen + 2 Polen + 1 Nederlander = 8 Europeanen...)

Desalniettemin hulde voor Twente...

[tdn135]

Suriname ligt ook in Amerika. Dus in feite is suriname een amerikaans land.

Met europa bedoelen wij natuurlijk de leden van de europese unie.

Wat ik niet snap is dat grotendeels de oost europese landen gewonnen hebben. Ik bedoel: Het merendeel heeft daar echt geen computer.

[needless to say]

het heeft hem natuurlijk voor een groot deel met motivatie en organisatie te maken.

Ik denkd at je best in elk land een team kon samenstellen die al de vragen in eenr edelijke tijd kon oplossen.

Het probleem is de mensen mobiliseren en via voorrondes selecteren.

Ik denk persoonlijk dat in Oost-Europa de motivatie groter ligt dan in het rijke en lui West-Europa.

[Parasietje]

Heel sterke opmerking! Je moet ook even kijken wie er allemaal meedeed ;-). Ik denk niet dat de Katholieke Universiteit Leuven een team programmeurs liet meedoen. We hebben hier bijvoorbeeld ook geen team die meedoet aan de Robocup, we hebben het te druk met "serieuze" zaken

[Verwijderd]

Serieuz zou ik de meeste academische activiteiten niet noemen. Het blijft gesubsideerd hobbyen. Maar deze wedstrijd sloeg dan ook een beetje de plank mis: de uitdagingen lagen vooral in de beperkingen van de tools die gebruikt mochen worden om de genoemde problemen op te lossen. Zodoende niet eens relevant. De robocub lijkt me eigenlijk wel een nuttig soort wedstrijd: als het gaat om het echt meten van de pragmatische programmeerkunsten.

[Verwijderd]

Dus Zwitserland ligt niet in Europa?

En je hebt geen computer nodig om te kunnen programeren. En op CS afdelingen op universiteiten hebben ze altijd wel een computer. Dat de boer op de hoek het niet heeft boeit niet.

[alt-92]

Wat ik niet snap is dat grotendeels de oost europese landen gewonnen hebben. Ik bedoel: Het merendeel heeft daar echt geen computer.

Lichtelijk naieve beredenering.
Universitair niveau heeft vrij weinig van doen met het percentage computers bij mensen thuis.
Volgens jouw beredenering zou China dan niet eens in de top 10 moeten voorkomen.

[Verwijderd]

Ah, thuis breedbandinternet hebben verbeterd de skills voor het hardere programmeerwerk?

Merk dat de opdrachten zwaar algorithmisch zijn. Dan verwacht je goede scores van culturen met een sterke logische traditie. Schaakspel, anyone? Juist, heel oosteuropa. Verder is in rusland en veel van het voormalige oostblok (surprise surprise) ongelijk verdeeld --- de top is daar echt top; niet zoals in nederland waar er vrijwel equivalente universiteiten zijn [iemand die echt goed is in eindhoven is dat ook in amsterdam].

Merk ook dat hoe schaarser computer resources zijn, des te harder iedereen geselecteerd wordt op (a) efficient en (b) van de eerste maal goed programmeren...

[ConanTheB]

Rusland != Europa. dus 3 Europese universiteiten.

[Verwijderd]

Rusland is niet EU, maar wel Europa. Verwarrend? Ja. Het wereldeel Europa bevat ook Rusland. De politieke organisatie genaamd Europese Unie bevat Rusland niet. Die zijn niet lid. Maar dit staat los van het wereld-deel. Pak er maar een kaart bij!

[Verwijderd]

zie CIA factbook: rusland = azie en europa; grens bij ural.

[davidem]

En ik altijd maar denken dat Europa (geografisch gezien) in het westen begint bij de Atlantische Oceaan kust en stopt bij de Russische Oeral... Ik herhaal; Russische Oeral....

[hcd320]

-te laat-

[Verwijderd]

Juist tellen, en suriname heeft er niets mee te maken.

Gegeven, zoals opgemerkt eerder:
rusland ten westen van Ural = in Europa,
rusland ten oosten van Ural = in Azie.
Dus van de hele lijst zijn enkel MIT, Shangai en Altay niet in Europa.

[De meeste plekken zijn ieder bekend, behalve:
*Altay= dicht bij Novosibirsk, 52uur trein van Moskow, richting Baikalmeer.
*Saratov=recht onder Moskow, dus wel europa.
*Ufa= op de westelijke hellingen van de Ural, dus (grensgeval, maar toch) in europa.]

[gamepower2005]

Niet slecht die vierde plek. Congrats dan ook aan het team.

Ik vind programmeerwedstrijd wel een beetje een groot woord. Zoals ik het nu lees is het meer een wiskunde wedstrijd, wat de prestatie natuurlijk er niet minder op maakt.

Project Euler is een soortgelijke wedstrijd, en er aan te raden:
http://mathschallenge.net/index.php?section=project

[martijnvanegdom]

Dit ben ik niet met je eens. Er zijn van die problemen die zijn wiskunde vrij eenvoudig op te lossen, maar omdat het even met een pc te doen is een heel ander verhaal. Daarnaast gaat de Euler Contest er omdat dat een antwoord aanlevert. Hoe je dat gedaan hebt maakt niet uit. Dus al bereken je het met de hand. Hier gaat het om code die moet werken en waarbij ik vermoed er een andere dataset word gebruikt door de jury als door de programmeeurs

Een paar hele trivale voorbeelden. Als ik jou 10 cijfers geef om te sorteren dan is daar geen kunst aan. Maar een computer heeft geen besef van volgorde dat zul je hem dus moeten leren. Dingen als Radix Sort zijn best grappig

Ik weet van de Delfste Programmeer Kampioenschappen dat het niet alleen draait om correctheid en snelheid maar ook om resources.

[VelhaChica]

Ik heb nooit een hoge pet opgehad van de Nederlandse programmeerkunsten. Ik wil hierbij de UT van harte feliciteren. Dit haalt mijn vooroordeel onderuit.

[Verwijderd]

Dit is zeker een indrukwekkende prestatie. Zeker gezien de beperking welke programmeertalen je mocht gebruiken. Het waren slechts imperatieve talen.

Terwijl bijna alle opgaven toch neer kwamen op constraint-satisfaction. Ik ben dan ook benieuwd voor welke programmeertaal van de gegeven 3 ze uiteindelijk gekozen hebben en of ze de constraints expliciet hebben gemodelleerd. Dit is dan ook meteen mijn kritiek op de wedstrijd: de persoon die de opgaven bedacht heeft heeft een nogal eenzijdige kijk op het soort programmeer-problemen dat ingewikkeld zou moeten zijn.

Je moet zulke wedstrijden niet vergelijken met het schrijven van een grote desktop applicatie (ala Word of Firefox). Dit soort problemen vereisen veel abstractie en intelligentie: zoals een iq-test. Grote pragmatische desktop projecten vereisen vaak geen intelligentie, maar discipline en ervaring: om de boel schaalbaal te houden. Dan is je grootste vijand de boel beheersbaar te laten houden. Dit vereist dus geen intelligentie, maar juist een bureacratische instellingen. (zeker als je moet samenwerken met een groot aantal mensen)

Overigs kun je dat soort kennis niet testen op zo'n wedstrijd, maar een aantal opgave die meer op AI hadden geleunt had ik wel toepasselijk gevonden. Er is more in this world than CSP. (constraint-satisfaction-problem).

De enige opgave die een beetje anders was, was die over compressie. Een opgave omtrend leer-algoritmes cq data-mining was ook wel op z'n plaats geweest. En elke webstrijd hoort 1 opgave te hebben waar je een compiler moet schrijven

Nouja, congrats aan de Twente. Gezien de nadruk op CSP en de beperke keuze uit programmeertalen een hele grote prestatie! Ik zou er persoonlijk niet aan durven, CSP problemen op te lossen in een imperatieve programmeertaal.

[Verwijderd]

Imperatieve taal? Leg uit: Java en C++ is toch objectgeorienteerd?

Ik ben geen informatica, dus ik kan het mis hebben hoor...

[Verwijderd]

Talen kunnen zowel imperatief als object-georienteerd zijn. Eigenlijk is dat ook een hele logische combinatie.
Met First-class-citizen bedoel ik dat je iets een volwaardig element is in een programmeertaal: je kan het opslaan in variabelen en rondgeven als argument aan functies.

In een notendop, je hebt de volgende paradigma's:

1. Imperatief

Expliciete scheiding tussen statements en expressies. Meestal gecombineerd met een dom type-systeem dat alleen expressies (en niet statements) van een type voorziet. Om zo'n dom type-systeem te compenseren doe je er verstandig aan dit te combineren met OO. Voorbeelden van puur imperatief: Pascal, Basic, C. Voorbeeld van een combinatie met OO: Java.

2. Object Georienteerd

De scope van variabelen en functies is een first-class-citizen en zoiets noem je een object omdat scope domme programmeurs zou verwarren. Statements bestaan in puur object georienteerde talen niet. Voorbeelden van puur object-georienteerde programmeertalen: Smalltalk.

3. Functioneel

Functies zijn first-class-citizen en houden zich aan de wet van de referntiele transpariteit. De volgorde van berekening volgt logisch uit de relaties tussen functies en de compiler heeft genoeg informatie om daar zelf een idee over te vormen. Dit lijkt errug op wiskunde. De compiler mag van alles met de linkerkant van een gelijkteken doen, mits het hetzelfde doet met de rechterkant. De compiler kan op deze manier vaak ontdekken dat hele stukken computatie kunnen worden overgeslagen. Statements zijn functies die de wereld als argument mee krijgen en de (geupdate) wereld weer terug-geven: statements zijn dus wel mogelijk met referentiele transpariteit. Voorbeelden van puur functionele programmeertalen: Haskell, Clean (nederlands), Miranda.

3. Logisch

Je defineert logische waarheden als relaties. Vergelijkbaar met functioneel alleen is er geen expliciete input en output meer. De compiler gebruikt deductie en inductie om een antwoord op een probleem te vinden die de gestelde regels 'waar' vinden. Dit gebruikt dus de logica zoals gedefineerd in de filosofie. Voorbeelden van een logische programmeertalen: Prolog, Mercury.

4. Constraint Satisfaction.

Omdat logica vaak erg traag is (omdat je alleen gegeven en antwoord kunt controleren of het waar is), kun je het beste de compiler wat hints geven over de volgorde om achter de waarheid te komen. Hier komen CSP's om de hoek. Hier defineer je problemen als relaties tussen maximaal 2 argumenten en geef je een expliciet voorkeur voor een bepaalde 'soort' volgorde. Zo'n volgorde gebruikt de compiler dan om te weten waar hij het 'eerst' naar de waarheid moet gaan zoeken. Zo'n volgorde komt voort uit een heuristiek. Er zijn geen programmeertalen die alleen met CSP's werken (volgens mij).

De meeste programmeertalen combineren of omvatten dan ook vaak verschillende paradigma. In logische talen kun je ook functioneel programmeren (alhoewel logische talen stiekem een vaste heuristiek hebben en daardoor er niet altijd even goed voor geschikt zijn, zoals Prolog). Pure functionele talen omvatten per defintie ook imperatief: mits je de wereld maar kan rondgeven als argument. Er bestaan ook talen die alle paradigma's mengen, zoals Oz.

En dan is er nog het gekke buitenbeentje C++. Het is imperatief, object-georienteerd (dmv pointers) en functioneel (dmv templates). Maar OO en functioneel zijn een beetje lelijk en hun computatie vindt per defintie plaats tijdens compile-tijd. Maar dat maakt C++ wel de taal waarmee je de snelste programma's kunt schrijven. (naast het feit dat het een b*tch is om te debuggen: het is ook de taal waar het programmeren zelf zo ongeveer het langst duurt).

Ik heb de boel hier een beetje versimpelt. Ik zou zeggen Wikipedia er op los. En besef: je kan in elke taal een compiler/interpreter voor een andere taal schrijven.

En omdat subjectiviteit er altijd toe doet vermeldt ik maar even mijn 'kleur'. Ik ben een fervent Haskell programmeur en ben (stiekum) van mening dat Java een uit-de-hand-gelopen 1 april grap is.

[Verwijderd]

Ik moet toegeven dat Pascal mij erg onbekend is. Mijn excuses voor de vergissing omtrend OO van Pascal.

En ja, je kan met constraints werken in die talen. Je kan ook in elke taal een prolog interpreter schrijven. Maar de talen zijn niet ontwikkeld voor _dit_ doel. De talen zijn bedoeld voor grote bureacratische desktop applicaties die veel dingen moet kunnen, maar waar geen van wat ze zouden moeten kunnen zo ingewikkeld is dat je een theorie prover of constraint solver nodig hebt.

Voor de soort problemen die hier beschreven worden zijn er talen (zoals bijvoorbeeld Haskell) meer geschikt die weer voor je standaard desktop proggie minder geschikt zijn.

Dat het kan? Tuurlijk kan het. Alles kan, waterkan, ijskan. Maar is het zo bedoeld? Nee. Is het wat het bedrijfsleven zou moeten doen? Nee. Als die een erp applicatie willen maken doen ze er verstandiger aan prolog of haskell, of een expert-tool te pakken dan Java of C++. Wil je Word maken, Winamp of MSN maken dan liggen de zaken weer anders.

Mijn kritiek was dan ook dat de wedstrijd geen realistische puzzels gaf omdat de c++/java beperking nogal vreemd is gezien de soort problemen die gegeven waren. Alsof je een wedstrijd huizen bouwen zou houden maar zou verplichten dat je alleen hamers en zagen zou mogen gebruiken. Hamers en zagen hebben een doel, en huizen bouwen is zich is goeie wedstrijd, maar de combinatie makes no sense.

[justice strike]

c++ is gebaseerd op c welke imperatief is. Het heeft welk een object georienteerde uitbreiding op c

voor java geld inderdaad dat het object georienteerd is, maar de implementatie van die objecten is weer wel imperatief. Wat java ook enigszins imperatief maakt. Sterker nog, je zou java kunnen gebruiken zonder objecten en alleen imperatief te werk kunnen gaan.

[Verwijderd]

Pascal is niet louter imperatief. Borland pascal is net zo OO als Java of C++.

Voor de rest zie ik geen enkele reden waarom constraint-satisfaction in een van deze talen niet zou kunnen. Het zeggen dat je de problemen uit dit voorbeeld niet zou willen oplossen in C++, Pascal of Java, geeft aan dat je die talen danwel onderschat danwel niet voldoende beheerst.

[Verwijderd]

Natuurlijk kun je constraint satisfaction problemen oplossen mbv een imperatieve taal net als dat je de complete software van een boeing in assembly kan schrijven. Het punt is hier meer dat imperatieve talen niet het beste gereedschap zijn voor de klus. Dat heeft weinig te maken met hoe goed je een taal kent of beheerst. Veel it'ers hebben de neiging om bijna alles in hun meest geliefde taal op te lossen. Toch is dat niet altijd het meest verstandig of efficient.

[TGEN]

Hezik, dat noemen we Delphi.

[Verwijderd]

TGEN: Nope. De taal is gewoon Pascal. De IDE is Delphi.

[dmantione]

@meneer r

Bedoeling bij een dergelijke programmeerwedstrijd is dat je een oplossing zelf verzint; als je een opgave indentificeert als het oplossen van een randvoorwaardeprobleem is het de bedoeling dat je zelf een oplosser schrijft voor dat randvoorwaardeprobleem.

Het is niet de bedoeling dat je een kant-en-klare oplosser gebruikt en alleen de randvoorwaarden invoert.

Bovendien zijn er zeer strikte timingseisen aan een oplossing. De opgave zijn zo gemaakt dat als je een minder efficiënt algoritme gebruikt dan de bedoeling is, je gelijk met een factor heel veel over de beschikbare rekentijd heen gaat.

Om die reden heb je exacte controle nodig over op wat voor manier het antwoord berekend wordt en kom je dus uit op een imperatieve taal.

De taal zelf is niet de enige reden waarom voor de klassieke talen C, Pascal en Java gekozen wordt. Gezien de beperkte tijd die voor het oplossen beschikbaar is (normaalgesproken 5 uur), zul je zeer efficiënt je idee in een werkend programma moeten kunnen omzetten. Een goede programmeeromgeving en ook debugger zijn dan ook van levensbelang om de wedstrijd tot een goed einde te kunnen brengen. Het zijn vaak de traditionele talen waar deze programmeeromgevingen het best voor beschikbaar zijn.

[Verwijderd]

"Bovendien zijn er zeer strikte timingseisen aan een oplossing. De opgave zijn zo gemaakt dat als je een minder efficiënt algoritme gebruikt dan de bedoeling is, je gelijk met een factor heel veel over de beschikbare rekentijd heen gaat."

Dus draait alles om de heuristiek (bij dit soort opgaves) en niet om de snelheid van de genegeerde ASM code van de 'inner' loop. Juist bij dit soort exponentieel groeiende problemen is de uitdaging _algoritmisch_ van aard. De constante factors kunnen geen grote toegevoegde waarde hebben.

"Het is niet de bedoeling dat je een kant-en-klare oplosser gebruikt en alleen de randvoorwaarden invoert."

Akkoord. Maar zou je een declaratieve programmeertaal een kant en klare oplosser noemen? Waar ligt dan de grens? Je kan prolog als templates in C++ doen? Mag template programming dan ook niet? Het onderscheid tussen oplosser en randvoorwaarde is nogal grijs. Welk onderdeel van een programma is geen randvoorwaarde? En mag dat onderdeel een primitief van de gebruikte programmeertaal zijn? Haskell, Lisp en Prolog zijn nog geen automatische solvers ofzo. Maar het schrijven van een solver is wel even wat makkelijk. Terwijl je nog alle controle hebt over het precieze algoritme.

Daarnaast zou je dus wel 1 oplosser kunt schrijven (dan wel niet zelf meenemen) zodat je je alsnog alleen op de randvoorwaarden en gebruikte heuristiek zou hoeven te richten. Dat zouden ze wel accepteren? It makes no sense. Belangrijkste lijkt mij is dat je inziet wat je nodig hebt om het probleem op te lossen en dat je in staat bent dat te implementeren. En waarom zou je dan voor alle opgaven dezelfde design-pattern (CSP) nodig moeten hebben? Ze hadden het net zo goed CSP-implementatie-wedstrijd kunnen noemen ipv de algemene naam 'programmeer-wedstrijd'. Geen van de opgaven vereiste leeralgoritmes, noch real-time decisions (zoals in robotics), noch datamining, noch parsers, noch dynamisch programmeren. De set opgaves was gewoon heel eenzijdig.

"gezien de beperkte tijd die voor het oplossen beschikbaar is (normaalgesproken 5 uur), zul je zeer efficiënt je idee in een werkend programma moeten kunnen omzetten."

Vandaar dat een taal als Java of C++ juist _niet_ het meest voor de hand ligt. Een prolog interpreter is ongeveer 30 regels Haskell code. Een general purpose constraint solver ongeveer 15 regels. De imperatieve talen die ik ken die door soort _productiviteit_ benaderen zijn slechts Python en Ruby. (en niet te vergeten LISP natuurlijk, alhoewel je die moeilijk als imperatief kunt classiferen).

Beweren dat je juist _snel_ in Java of C++ kunt programmeren is onzin. Je hebt zowieso al veel en veel meer code nodig om hetzelfde te bereiken. Daarna moet je testen en debuggen om dingen te controlen die in een declaratieve taal tijdens compile-tijd kunnen worden gecontroleerd. Zelfs de makers van deze talen hebben deze talen niet ontwikkeld met _dit_ doel. (rapid prototypping). Maar juist om langdurig onderhoudbare code te schrijven met een groep mensen. Waarbij C++ meer rekening houdt met de mogelijkheid performance tweaks toe te passen.

Ik zeg ook niet dat die talen geen doel dienen. Ik beweer alleen dat de combinatie van opgaven en programmeertalen irreel zijn.

"het zijn vaak de tradionele talen waar deze programmeeromgevingen het best voor beschikbaar zijn."

Ik vermoed dat je weinig ervaring hebt met declaratieve talen. Daar debug je niet, daar gebruik je een theorem-prover die eigenschappen van je software controleert. Dat werkt sneller en vollediger. Debuggen is juist een ramp met imperatieve talen: wat weer voorkomt uit slechte type-systemen, wat weer een gevolg is van het niveau controle dat een imperatieve taal je geeft. De C familie is met ster de grootste bitch om te debuggen. Met name als je ook nog templates gaat gebruiken. Wat voor zulke opgaven juist weer aan te raden is. Al helemaal als je het in zo'n korte tijd moet ontwikkelen.

Mijn commentaar blijft dan ook: de opgaven meten niks reeels. Het bedrijfsleven zou nooit zulke talen voor zulk doeleinde gebruiken. En als snelheid van een inner loop al een issue zou zijn, is hardware upgraden altijd goedkoper dan langer programmeren. Daarnaast poepen moderne
compilers behoorlijk snelle code uit, vergis je niet!.

Programmeer technisch behoren de talen waar je uit kon kiezen tot de lagere legioenen, dus de uitdaging is ook niet theoretisch van aard te noemen. Zeker ook gezien het feit dat alle opgave opgelost diende te worden met het CSP design pattern.

Wat er uiteindelijk gemeten wordt is wie er het best iets kan doen waar geen vraag naar is, op een manier die niet voor de hand ligt...en dan met verschillende opgaven die allemaal op hetzelfde neerkomen.

In de categorie van: wie kan het snelst geblindoekt hardlopen met 2 handen op mijn rug gebonden?

De uitdaging zit dan ook niet in de opgaven, maar in de beperkingen die je worden opgelegd om ze op te lossen. Vandaar ook dat ik dit een grote prestatie vindt.

SIDENOTE: Bestaan er trouwens wedstrijden waar het de bedoeling is om de meest maintainable code te schrijven? Dat lijkt mij nou ook een erg intressante factoor om mee te wegen in de beoordeling.

[dmantione]

Laten we even een verschil maken tussen een functionele taal (Haskell) en een taal als Prolog. Bij de eerste bepaal je zelf het algoritme, en heb je controle over de tijdscomplexiteit. In Prolog kun je een deel van (want niet alle problemen kun je in Prolog invoeren) de problemen gemakkelijk oplossen, maar bepaalt Prolog het zoekalgoritme en heb je geen controle over de tijdcomplexiteit. Dat diskwalificeert wat mij betreft Prolog als bruikbare taal.

In Haskell zou je de opgaven kunnen programmeren, en kun je je inderdaad concentreren op het algoritme. Maar niet te vroeg gejuicht, die lijst die je in Haskell gebruikt hebt zou je in Pascal wellicht als array geïmplementeerd hebben en misschien had je daarmee een factor n kunnen besparen; Haskell heeft zo zijn voor- maar ook nadelen ten opzichte van de imperatieve talen, en er is bij mijn weten geen goede ontwikkelomgeving voor, wat de bruikbaarheid beperkt.

Op deze wedstrijden mag je overigens de meest ranzige code schrijven die je maar wilt, als 't maar werkt.

[Verwijderd]

Geen goede ontwikkelomgeving? Er is Eclipse support voor Haskell, maar je zou natuurlijk gewoon de console kunnen gebruiken. De eclipse support komt inclusief code completition, en compile-time checking as you type in the background. (foute stukken worden dan rood onderlijnt, net als in Java)

Persoonlijk gebruik ik een plugin voor gnome-edit (de standaard gnome editor) die een console eronder tovert. Syntax highlighting zat er al in. En hoogle (de haskell-api search engine op basis van types) zoek ik gewoon via m'n deskbar-applet. Maar misschien is het op linux gewoon wat makkelijker. Daarnaast is er ook nog hIDE, ( de haskell ide ) maar die is alleen voor windhoos vermoed ik. Maar komt waarschijnlijk niet in de buurt van Eclipse, qua features. Als je geen moeite ermee hebt dat Java-monster op te starten zou ik vooral Eclipse gebruiken.

Overigens ondersteunt Haskell ook arrays hoor. Zelfs mutable ones. En mits je al je code netjes als monad schrijft is de transistie naar een echte array niet zo moeilijk. Grappig trouwens dat de lijst-monad eigenlijk gewoon op Prolog stijl backtracking neer komt :-). Dus als Prolog niet mag, dan mag je in Haskell lijsten niet als Monads gebruiken, want dat is ook de prolog-search. Kijk:

colors = ["red","blue","white"]
shapes = ["square","circle"]
coloredShapes = do
c <- colors
s <- shapes
return "a " ++ c ++ " " ++ s

Nu is coloredShapes een lijst met alle combinaties van colors & shapes, depth first stijl. In feite is de monad join vervangen met (++) en de return met (:[]). Zo'n algoritme dan later weer switchen naar BFS is dan ook een eitje. Maar van je lijsten een eigen datatype (zodat je de monad zelf kunt overloaden) en implementeer de monad-join niet met (++) maar met (reverse (++)) en je hebt BFS.

Oftewel, waarom mag haskell wel, als haskell impliciet prolog heeft ingebouwd ?

Anderson is ook waar, Prolog heeft weer impliciet Haskell ingebouwd. Een lambda solver schrijven in prolog is ook maar een regeltje of 30 :-) En ook BFS is mogelijk dmv eerst een lijst te vullen en die daarna met je eigen algoritme weer af wandelen. Dat kost je ongeveer 2 a 3 predicaten. DFS is gewoon de default. Denk de variable-matching en bindings even weg, en je hebt gewoon functioneel programmeren zonder lazy evaluation: wat weer neerkomt op imperatief programmeren.

Mijn punt: het is een nogal grijs gebied. Het zijn allemaal turing-talen: het verschilt alleen in de wijze waarop je je algoritme defineert. (of aan de hand van functies, of aan de hand van predicaten, of voor imperatief: aan de hand van procedures).

[dmantione]

Omdat je in Haskell niet verplicht bent je oplosmethode te beperken tot hoe goed de compiler een algoritme weet te verzinnen voor het backtrackprobleem, terwijl dat in Prolog wel het geval is.

Neem bijvoorbeeld van deze set de eerst opgave (Nomen est Omen): http://inter-actief.cs.ut...p2003/opgaven/opgaven.pdf

Backtracking is nooit een acceptabele oplossing op een wedstrijd, veelal zul je een cache in moeten programmeren of op de één of andere manier de zoekruimte beperken. Zo ook bij deze opgave, je kunt de recursieboom cachen op basis van de twee (of waren het er drie?) voorgaande recursieslagen. Alleen ademende en vooral denkende wezens hebben het inzicht om te bepalen hoe die cache toegepast moet worden.

Wat betreft arrays in Haskell, uiteraard kun je in Haskell arrays gebruiken, en zelfs dingen waar functionele talen niet goed in zijn (in-/uitvoer) zijn redelijk opgelost. Desondanks zijn de basisprincipes van functionele talen veelal recursie en lijsten, terwijl dat in imperatieve talen lussen, procedures, pointers en arrays zijn. Het is een andere manier van programmeren.

[Verwijderd]

Prolog biedt backtracking aan, maar je kan er dus net zo goed andere soort algoritmes mee schrijven. In plaats van niet gecontroleerde pseudo code hier te gooien heb ik maar even gegoogled:

http://www.cs.nps.navy.mi...lty/rowe/book/chap10.html

Breadth-first search predicaat in prolog. Hier zie je een prolog implementatie van breadth-first-search. Je kan ook monads en beta-reductie uitdrukken in prolog:

http://logic.csci.unt.edu...h/PapersHTML/monadic.html

Zelfs object-georienteerd programmeren is mogelijk in Prolog. Prolog is immers turing-waardig. Ja kan ook alle mogelijke sorteer-algoritmes programmeren in prolog. Dus ook caching zou heel goed mogelijk zijn om te implementeren in Prolog. Alleen backtracking krijg je cadeau. Net zo als dat je beta-reductie in Haskell cadeau krijgt.

"..waar functionele talen niet goed in zijn (in-/uitvoer) zijn redelijk opgelost"

Redelijk? Je kan voor OO een monadje aanmaken en dan OO programmeren, bijvoorbeeld. Als je je echt in de monad's verdiept is het juist zo mooi dat het executie model zelf kunt aanpassen. Deze code is echt niet ondenkbaar:

main = do
x <- new pizza
y <- new salami
z <- new person
x AddToPizza y
x Consume y
z IsHappy

Bijvoorbeeld door gebruik te maken van IORef's en data constructoren aan te maken voor de methode-namen. (Je zou ook de methode namen strings kunnen maken)

Niet dat Haskell veel op deze manier gebruikt wordt, maar het zou dus gewoon kunnen. In het algemeen is de translantie van OOP naar Haskell eerder:
- maak voor elke klasse een datatype aan
- maak voor elke klasse een monad-instantie aan

Gebruik monad transformaties om de verschillende monads aan elkaar te rijgen. Daarnaast kun je heel veel routines polymorph maken tov monads. Dat je dus een routine hebt die met alle soorten monads kan werken.
Zie ook:

http://www.nomaware.com/monads/html/

Dus heb je een object waarvan de state bijvoorbeeld een array bevat, dan zou je de state-monad gebruiken om een array vast te houden. De routines die de array bewerken zou je dan liften naar de monad. Ik denk dat je het tekort doet als je doet alsof het normale IO zou benaderen. Op zijn eigen manier overtreft het juist de gebondenheid van het executie model van traditionele IO. Denk ook bijvoorbeeld aan de monadische parsers: (google op parsec)

helloWorldParser = do
string "Hello"
whitespace
string ","
x <- many1 alphaNum
return "Well, Hello! Who told you my name is " ++ x ++ "?"

In een imperatieve taal zou jede backtrack functionaliteit van dit soort parsers niet (gemakkelijk) mogelijk!

[JeroenB]

Ik vind het een beetje kort door de bocht als je stelt dat software engineering te verdelen is in enerzijds algoritmische complexiteit en anderzijds bureaucratie. Het schrijven van omvangrijke applicaties die goed evolueren en daarbij schaalbaar en onderhoudbaar blijven, vereist meer dan ervaring en een bureaucratische instelling. Maargoed, ik neem aan dat je chargeerde.

[Verwijderd]

Ik overdreef inderdaad. Het feit is dat ik de eigenschap die tot maintainable en schaalbare software zou leiden niet echt zou kunnen benoemen (anders dan een bureacratische houding en ervaring). Als jij een betere omschrijving weet, dan zou ik dat graag horen :-)

Alle applicaties vereisen van alles een beetje. Maar je kunt voor de meeste projecten toch stellen dat de uitdaging (de nadruk) in een van de twee hoeken ligt.

Of op algoritmische complexiteit, of op schaalbaarheid/maintainable. Maar soms zijn beide een uitdaging. Neem bijvoorbeeld een uitgebreid mail-software, waar ook een spamfilter in zit verwerkt zoals Evolution/Thunderbird, of een RTS spel met een 3d engine.

Maar het zijn zodoende wel twee aparte disciplines. De meeste programmeurs/informatici blinken toch meestal maar in een van de twee zaken uit. (of in geen van de twee zaken :-P)

[Verwijderd]

Ik ben het niet met je eens dat het met een CSP taal anders zou zijn. Tuurlijk is de manier van programmeren anders, maar dat maakt de problemen niet makkelijker. Sterker nog, ik denk dat je met een CSP taal de problemen niet eens kunt oplossen.

De opgaven moeten namelijk niet alleen opgelost worden, maar de programma's moeten de oplossingen ook nog eens heel snel vinden. Het volstaat dus nooit om gewoonweg brute-force de oplossing te zoeken. Aangezien je met een CSP taal veel moeilijker het zoekalgoritme kunt bepalen biedt het dus geen voordeel t.o.v. een imperatieve taal.

[Verwijderd]

CSP en bruteforce? Ik denk dat je een beetje in de war bent. Met CSP kun je zelf de heuristiek bepalen, al hoewel het meestal al voldoet om gewoon de constraints gewoon in de meest handige volgorde te zetten. En of je het nou doorhebt of niet, je C++/Java implementatie zal of CSP of misschien A* search implementeren, of iets wat daar op lijkt. De beperking die zulke algoritmes je opleggen, zijn niet inherent aan die algoritmes maar aan de gehele informatica. Een sneller algoritme dan A* om gegeven een heuristiek te zoeken bestaat niet. En CSP is gegeven de juiste volgorde van de constraints ook de snelst _mogelijke_ implementatie. Je doet net alsof kennis van het probleem niet in CSP of in een A* heuristiek is uit te drukken, maar wel in je C++ of Java code. Dat is gewoon onzin.

"Aangezien je met een CSP taal veel moeilijker het zoekalgoritme kunt bepalen biedt het dus geen voordeel t.o.v. een imperatieve taal."

Ja je kunt het niet zelf bepalen. Je wordt gedwongen het bewezen sterkste algoritme te gebruiken. Extra handig voor mensen als jou die denken dat ze in C++/Java of welke taal dan ook, een sneller zoek algoritme kunnen schrijven. OF je hebt meer informatie over het probleem domein (en zou die informatie ook in een heuristiek kunnen verwerken) of je algoritme is gewoon _niet_ sneller. En zowel dan kan je puur op dat algoritme afstuderen en promoveren, want dan staat de hele informatica op z'n kop.

Het is net zo iets als beweren dat je met een imperatieve taal zelf een sorteer routine kan schrijven die sneller dan O(log n) werkt. Je kan het wel zelf een algoritme schrijven, maar A* en CSP raken al de 'bottom' van algoritmische performance. Het enige wat de performance kan vergroten is meer kennis _over_ het probleem. Kennis die altijd om te zetten is in een heuristiek. Pas met onvolledige kennis of de verplichting real-time een keuze te maken zouden deze algoritmes niet meer voldoen. Maar zulke opgaven zaten dus niet bij! (waar ik weer over zat te zeuren ja!)

Overigens doelde ik niet perse op CSP talen, eerder op declaratieve talen. Talen waarmee een CSP implementatie een kwestie van 10 minuten is ipv 2 uur. Puur CSP talen bestaan helemaal niet overigens: ze worden altijd gemengd met andere paradigma's. Of met logic-programming, of met functioneel en soms zelfs met imperatief. (of gewoon met alles: zie de taal Oz)

Ik constanteerde slechts dat alle opgave (muv 1) neer kwamen op een CSP en dus nogal eenzijdig waren. De uitdaging lag daardoor toch voorial de beperking van de tools (C++ of Java). Waarmee je juist niet snel een werkend prototype kan maken voor dit soort problemen. In Haskell, Prolog of zelf Python of Ruby zou dit even wat sneller gaan.

[mawashigeri]

Het is net zo iets als beweren dat je met een imperatieve taal zelf een sorteer routine kan schrijven die sneller dan O(log n) werkt.

Ik zou de ondergrens wat minder optimistisch op O(n log n) stellen. De enige winst die je nog kunt behalen is geheugengbruik en/of het aantal element swaps.

[kuifware26]

De ICPC wedstrijden zijn algoritmisch van aard. Eén gevolg daarvan is overigens dat de problemen wiskundig van aard zijn. De voorronde hier in de Benelux heet dan ook BAPC: Benelux Algorithm Programming Contest. (Voorheen heette het NKP, Nederlands Kanpioenschamp Programmeren, maar sinds vorig jaar heet het BAPC [helaas bleek dat er toch alleen Nederlandse teams waren gekomen]).

Bij het NKP in 2004 in Utrecht was Haskell overigens wel toegestaan als programmeertaal, maar daar waren toen niet erg veel inzendingen voor.

Er zijn ook westrijden waar je eerder dingen vindt zoals patroonherkenning. Vb.: de Challenge24 in Budapest (waar je 24 uur achter elkaar aan de slag gaat met z'n drieën).

De Google Code Jam heeft ook weer z'n unieke spelregels (na afloop krijgt iedereen de gelegenheid elkaars programma's onderuit te halen d.m.v. een falend testgeval).

Het probleem met patroonherkenning e.d. is natuurlijk dat je programma soms niet een goed antwoord geeft. Bij de ICPC moet je programma juist alle testgevallen voor een opgave correct hebben opgelost. Bij andere wedstrijden krijg je weer punten per testcase. Dit geldt bijvoorbeeld ook voor de IOI's [International Olympiad in Informatics].

Applicaties maken, zie je ook niet in elke wedstrijd terugkomen. Bij de Challenge24 heb ik wel dergelijke dingen gezien; maar daar heb je dan ook 24 uur de tijd; en de jurering gebeurde met de hand. (dit levert altijd iets aan subjectiviteit in)

Kortom: er zijn veel programmeerwedstrijden, elk met hun eigen karakteristieken: sterke kanten, leuke kanten, kanten die het spannend maken, en onvermijdelijk ook wat minder sterke kanten. Maar dat drukt de pret toch niet? Als u vind dat er te weinig of geen wedstrijden zijn van een bepaalde categorie, nodig ik u van harte uit een wedstrijd te organiseren die dit gat kan opvullen!

Zijn bedrijven geïnteresseerd zijn in de (algoritmische) programmeertalenten van studenten? Ze sponsoren in ieder geval wel veel wedstrijden, en soms moet je zelfs je CV bij je inschrijving meesturen. Net zoals een academische studie van waarde wordt geacht, worden ook deze theoretischer vaardigheden op prijs gesteld. En: zelfs in Winamp of in Word kom je op onverwachte momenten algoritmische problemen tegen!

[Verwijderd]

Zeer intressante info allemaal. Overigs vond ik niet dat er niet genoeg wedstrijden waren: ik vond alleen dat de opgaven van deze wedstrijd .. zelfs voor de titel van 'algoritmisch' nogal eenzijdig waren.

En dat in Utrecht Haskell wel mocht lijkt mij meer dan logisch: Utrecht heeft declaratief programmeren behoorlijk hoog in het vaandel (gelukkig). Maar de Java/C++ beperking blijf ik vreemd vinden... Haskell had niet perse gehoeven, maar zelfs Python of Ruby had ik al 100 keer logischer gevonden dan Java of C++ zijn ook veel meer mainstream voor de purpose van rapid-prototyping. De beperking zegt volgens mij meer over de achtergrond van de jury dan over de kennis en kunnen van de voornamelijk academische geschoolde deelnemers.

Maar intressante info .. ik zal even gaan google-en...

[TD-er]

Nederland heeft in het verleden wel vaker redelijk hoog gestaan in dergelijke wedstrijden.
Maar of ze in de top10 zijn geweest weet ik niet meer uit het hoofd. In de top 20 ken ik in elk geval een groepje wat dat een paar jaar geleden gehaald heeft (11e plek meen ik)

[needless to say]

Bah, geen Belgische deelnemers...

De opdrachten leken mij nochtans goed te doen.

[Verwijderd]

Wij doen niet mee aan programmeerwedstrijden tegen de klok. Wij schrijven kwaliteitsvolle code.

[dmantione]

In Nederland is er op iedere universiteit een bepaalde club die ieder teams ronselt en voorrondes houdt. Bovendien wordt er jaarlijks een Nederlands kampioenschap georganiseerd.

In België is deze traditie er niet. Ik heb regelmatig aan de Noord-West Europese kampioenschappen meegedaan, als er al Belgische teams waren, dan deden deze zonder voorronde direct mee. Het gevolg is dat er veel (in mijn jaren: alleen maar) teams mee doen die het talent niet hebben. Bijgevolg valt er van de Belgen (helaas) niet veel te verwachten.

België is niet het enige land wat dit probleem heeft. In Duitsland is de situatie hetzelfde. Men (enkele universiteiten) probeert daar al jaren een landelijk kampioenschap van de grond te krijgen aan de hand van het Nederlandse voorbeeld, het lukt erg moeilijk om de club van deelnemende universiteiten te laten groeien.

Landen waar het wel erg leeft zijn de Scandinavische landen, en dat is te merken: De teams uit die landen zijn extreem gevaarlijk.

[Verwijderd]

Ik heb regelmatig aan de Noord-West Europese kampioenschappen meegedaan, als er al Belgische teams waren, dan deden deze zonder voorronde direct mee. Het gevolg is dat er veel (in mijn jaren: alleen maar) teams mee doen die het talent niet hebben.

Geen voorronde hoeft niet persee te betekenen dat je geen kans maakt.

Ik heb zelf eens aan de North-West European Programming Contest meegedaan, en dat bestond toen uit 2 dagen. De eerste dag zaten we tijdens de lunch tegenover een Pools team. Deze jongens hadden niet eens een voorronde op de universiteit of nationaal gehad, terwijl wij allebei hadden overleefd. Toch wonnen zij, en wij gingen roemloos ten onder in het programmeergeweld.

@dmantoine: Nee, in Amsterdam op de VU, en dit was alweer jaren geleden ... 1995 of iets dergelijks.

[dmantione]

Dat was in Den Bosch zeker? Ik ben toen vierde geworden en was inderdaad onaangenaam verast door hoe sterk het Poolse team was.

[martijnve]

ik vind de puntentelling een beetje vreemd. als je naar 2 en 3 kijkt zou ik toch zeggen dat 3 het beter heeft gedaan?

[T.T.]

Allereerst wordt gekeken naar het aantal correcte antwoorden, pas daarna werd gekeken naar de tijd die het team over de oplossingen deed. Team 2 heeft 6 vragen goed beantwoord, team 3 heeft 5 vragen goed. Wanneer je een foutief antwoord aan de jury voorlegt, krijg je een penalty van 20 minuten. Daarom zijn de tijden waarschijnlijk zo verschillend.

[TD-er]

Ze rekenen qua tijd het aantal minuten na het begin van de wedstrijd dat een opgave goedgekeurd is.
Dus als je alles 5 mins voor het eind instuurt en het is allemaal goed, heb je er "het langst" over gedaan, maar als je het meeste aantal opgaven goed hebt, kun je alsnog winnen.

[Verwijderd]

ik vind de puntentelling een beetje vreemd. als je naar 2 en 3 kijkt zou ik toch zeggen dat 3 het beter heeft gedaan?

Ik neem aan dat alle teams de volledige vijf en een half uur hebben volgemaakt en geprobeerd zoveel mogelijk opgaven op te lossen.

Daarbij hebben zowel team 2 als 3 in ieder geval vijf vragen goed, team 2 misschien nog wel sneller dan team 3. Maar team 3 heeft de rest van de tijd tevergeefs geprobeerd vraag 6 op te lossen, terwijl team 2 dit binnen diezelfde tijd wél is gelukt.

[H3llrais3r]

Ik denk niet dat ze gekeken hebben naar de tijd, Maar alleen naar het verullen van de opdrachten.

Pos 3 heeft de snelste tijd, maar 1 vraag minder goed dan de 1e en 2e plaats. Plaats 1 = de snelste met het zelfde aantal goede antwoorden als plaats 2.

[Verwijderd]

Pos 3 heeft de snelste tijd,

Dat hoeft dus helemaal niet, misschien hadden team 1 en team 2 die eerste vijf vragen wel sneller af dan team 3.

[legofanaten]

te laat

[Verwijderd]

Mooi werk! Als student Informatica aan de UT klinkt dit natuurlijk erg gaaf.

In ons colloquium zit een vak dat veel aandacht besteedt aan dit soort problemen. Nou vind ik wel dat programmeren veel meer inhoudt dan puur efficiente algoritmes bedenken. Zoals eerder opgemerkt zou een data mining vraag bijvoorbeeld niet misstaan. Sterker, ik had graag gezien dat een dergelijke programmeer wedstrijd bredere vragen zou hebben. Zo zijn er in de informatica faculteit een aantal leerstoelen, en slechts 1 houdt zich full-time bezig met vragen zoals in deze test (leerstoel Formal Methods and Tools, FMT).

Desalniettemin een goede prestatie van de jongens die waarschijnlijk hoge cijfers gehaald hebben op het vak Algoritmen, Datastructuren en Complexiteit

[edit]
[quote]
De maximale afstand tussen twee punten in een ongerichte graaf werd gevraagd in opgave negen.
[/quote]

Volgens mij is dit een bekend probleem, waarvan niemand tot dusver een oplossing voor bedacht heeft. Valt dit probleem niet in de NP-klasse? Het vak wat ik twee zinnen eerder noemde stipt dit geloof ik aan.

Het vinden van een langste pad tussen twee punten in een gerichte graaf valt wel in de klasse NP-complete. Ik zie zo snel even niet of het in een ongerichte graaf ook een NP-complete probleem is...

Wat NP problemen zijn? klik -> http://en.wikipedia.org/wiki/NP-complete

[needless to say]

lol, wij hadden ook gerust twee zo een vakken aan de universiteit in Gent .

Ik denk dan ook dat dat basisleerstof is in elke informatica-richting die zichzelf respecteert.

[Verwijderd]

'Het vinden van een langste pad tussen twee punten in een gerichte graaf valt wel in de klasse NP-complete. Ik zie zo snel even niet of het in een ongerichte graaf ook een NP-complete probleem is..."

Haha. Dus algoritmisch gezien zou je het net zo goed bruteforce doen dus. Er valt helemaal niks te prunen. Of hopen ze stiekem dat iemand een tijdige oplosser voor NP-complete problemen uitvindt. Dat zou wel groot nieuws zijn inderdaad.

(sarcasme aan)

Ja, maar je kan Java of C++ gebruiken en dan kan het wel sneller want met imperatieve talen kan je zelf het zoekalgoritme schrijven!

(sarcasme uit)

Het was dus een strikvraag.

[Verwijderd]

dit zegt toch weinig over de universiteit zelf, t'is gewoon een kwestie van enkele hoogbegaafde gekken in je team te hebben die vrij goed zijn in deze materie

[Verwijderd]

Het valt me nog mee in hoeverre je je een denkwijze als hierboven nodig is kunt leren hoor! Ik ben ook absoluut geen hoogbegaafde gek hierin, maar met behulp van de kennis die je opdoet tijdens een studie Informatica aan de UT kom je toch veel verder, dan als je die kennis niet hebt. Je kunt problemen sneller plaatsen in een bepaalde categorie denk ik...

[dasiro]

vierde plek veroverd en daarmee een gouden medaille en een geldprijs ter waarde van 3000 dollar gewonnen

vreemd, ik dacht altijd dat je goud kreeg als je eerste was en géén medaille als je vierde was

[SlowikPL]

Shit, Polen op tweede plek. Had meer verwacht.

[Vectrox]

Mm ik snap de vierde vraag nog niet eens, hoe wil ik dat dan programmeren