(klik voor opgave 1 of opgave 2) opgave 3 in pdf
Let op: Willem van der Vegt, de wedstrijdleider, geeft op aparte pagina's antwoord op vragen en opmerkingen. Soms geeft hij ook verduidelijkingen en correcties.
Inleiding
Bij deze opgave gaat het om het schrijven van een programma dat in staat is het spel Pillars te spelen. Je programma moet voldoen aan de specificaties die hieronder beschreven staan. In tegenstelling tot opgave 1 en opgave 2, mag je de naam van je programma zelf kiezen.
Pillars is een spel dat gespeeld wordt tussen twee spelers op een 10x10 bord. Een van de spelers speelt met de rode tegeltjes; de andere speller met de blauwe tegeltjes. Het doel van het spel is om je tegenstander de laatste zet te laten uitvoeren.
Het bord
Op het bord worden 10 pilaren op willekeurige manier neergezet. Dat kan per spel anders zijn. De pilaren zijn geplaatst in 10 verschillende rijen en in 10 verschillende kolomen.
De zetten
De rode speler begint. Hij moet een rechthoek van tegeltjes plaatsen op een niet-bezet stuk van het bord. De rechthoek mag een 1x1 vierkant zijn.
Een voorbeeld van een mogelijke zet is: “BdCh”. De linker bovenhoek moet eerst genoemd worden.
Joker
Bij iedere beurt mag een speler de overwinning claimen. Als hij dat doet kan hij extra punten winnen of verliezen. Je mag de overwinning maar één keer claimen.
Een speler kan dat doen door een uitroepteken voor de zet te plaatsen: “!BdCh”.
Het spelen van het spel
Je programma moet met de software van de jury communiceren via standard-input (stdin) en standard-output (stdout). Je leest informatie van stdin en je schrijft je zetten naar stdout. Je speler begint met het lezen van een regel invoer van stdin. Beide spelers moeten eerst de posities van de 10 pilaren inlezen. Iedere pilaar staat beschreven op een nieuwe regel. De rode speler krijgt vervolgens het woord “Start” te lezen en de blauwe speler de eerste zet van rood. Als jij aan de beurt bent om te zetten, bedenk dan een zet en schrijf die naar stdout. Nadat je een zet hebt gedaan lees je de zet van je tegenstander van stdin. Iedere zet die je van de jurysoftware doorkrijgt is gegarandeerd een geldige zet.
Als één van beide programma’s een ongeldige zet doet of gewonnen heeft, lees je het woord “Quit” van stdin. Dit betekent dat je je programma normaal moet afsluiten.
Puntentelling
Als een speler de overwinning claimt, dan worden het aantal niet-bezette vel
den geteld voordat de zet wordt uitgevoerd. Dat aantal wordt gedeeld door 10 en naar beneden afgerond. Als bijvoorbeeld 49 niet-bezette velden geteld worden dan is zijn joker 4 punten waard. Als de blauwe speler de overwinning meteen claimt in de eerste ronde, dan wordt zijn joker het maximum aantal van 9 punten waard.
Als een speler wint, krijgt hij 18 punten plus het aantal punten van de joker. Als hij verliest krijgt hij 9 punten min het aantal jokerpunten. Als een speler een ongeldige zet doet, het programma crasht of teveel tijd gebruikt, wint de tegenstander met 18-0 vermeerderd met de jokerpunten. Als de tegenstander nog geen jokerpunten had geclaimd, worden de jokerpunten erbij opgeteld op basis van de stelling die op dat moment bereikt werd.
Voorbeeld spelverloop
De volgende tabel toont het begin van een spel.
speler |
Input |
output |
rood |
Aa |
|
rood |
|
AcBd |
blauw |
Aa |
|
blauw |
|
!AeAj |
rood |
AeAj |
|
rood |
|
... |
Tijdlimieten
Je programma heft een totale speeltijd van 5 seconden. De wedstrijdcomputers maken gebruik van een 2,8 GHz Pentium IV processor. Je mag maximaal 64 MB aan geheugen gebruiken.
Je mag zelf uitmaken hoe je de rekentijd van 5 seconden gebruikt.
Alleen de tijd tussen het lezen van stdin en het schrijven naar stdout wordt gerekend.
Over de CodeCup
De CodeCup is een wedstrijd bij opgave 3 van de eerste ronde van de Nederlandse Informatica Olympiade. De wedstrijd wordt online gespeeld en is live te volgen op het Internet.
Programmeurs vanuit de hele wereld mogen meedoen aan de CodeCup. Zie ook de website http://www.codecup.nl. De organisatoren van de NIO doen buiten mededinging mee met hun programma’s.
Inzenden
Je zendt je programma in door je aan te melden op de CodeCup-site en het programma daar te submitten. Op submit.informaticaolympiade.nl kun je melden dat je een inzending voor opgave 3 van de eerste ronde Nederlandse Informatica Olympiade hebt gedaan en onder welke naam (zie ook de algemene informatie over het inzenden van je oplossingen).
Windesheim Digitalis prijs
De beste leerling of docent uit het voortgezet onderwijs wint de Windesheim Digitalis prijs ter waarde van 250 euro. Deze prijs is beschikbaar gesteld door de School of Education, Marktgroep Voortgezet Onderwijs van de Christelijke Hogeschool Windesheim te Zwolle.
Punten voor deze opgave
Als je een werkend programma inzendt dat wordt toegelaten tot het toernooi om de CodeCup en als je programma tijdens het toernooi om de CodeCup niet crasht, geen ongeldige zetten doet en de tijd niet overschrijdt komen krijg je 20 punten.
Omdat je op de CodeCup-site al kant en klare voorbeeldspelers aantreft zal dat geen probleem moeten zijn. We willen graag dat je programma enige intelligentie bevat. Daarom laten we het een klein toernooi spelen tegen vijf andere min of meer toevallig spelende concurrenten. Van de score die je programma in dat toernooi haalt trekken we 120 punten af; wat je resteert delen we door 3. Zo kun je maximaal 50 punten halen.
Op basis van de volgorde in het eindklassement van de CodeCup worden nog maximaal 30 extra punten per inzending gegeven; hoe hoger je programma eindigt, des te meer punten krijg je. Iedereen van wie het programma niet volledig onderaan eindigt krijgt tenminste 1 punt.
