 |
||||
|
Programmeermethoden 2014
Vierde programmeeropgave: Mastermind
De vierde programmeeropgave van het vak
Programmeermethoden
in het najaar van 2014
heet Mastermind;
zie ook het
twaalfde werkcollege,
en lees geregeld deze pagina op WWW.
Spreekuur in zalen 302 ... 309:
dinsdag 18, woensdag 19, donderdag 20,
dinsdag 25, woensdag 26, donderdag 27 november,
dinsdag 2, woensdag 3, donderdag 4 en vrijdag 5 december 2014, van circa
15:30 tot 17:00 uur.
Voor I&E-studenten (Den Haag)
is er een vragenmiddag in zaal Paleistuin/Malieveld op donderdag 4 december 2014, 14:00-17:00 uur.
De opgave
Voor deze programmeeropgave gaan we het spel Mastermind
programmeren.
De ene speler (Klaas) neemt een code in gedachten die dan door de
andere (Henk) geraden moet worden, liefst in zo weinig mogelijk beurten.
De code bestaat uit een N-tal verschillende "kleuren" = getallen,
waarbij de kleuren uit de verzameling {1,2,...,K}
gekozen zijn. De volgorde van de kleuren is van belang.
Hierbij zijn N en K ≥ N maximaal 10 (een const int).
Henk doet steeds een gok; een gok bestaat uit een
N-tal verschillende getallen uit bovengenoemde verzameling.
Klaas moet dan vertellen hoeveel getallen er
op de juiste plaats staan ("zwart"), en hoeveel getallen er goed zijn,
maar zich op een verkeerde plaats bevinden ("wit").
Een voorbeeld (het gewone Mastermind). Neem N = 4, K = 8. Stel dat de geheime code 3--5--1--6 is, en dat Henk 7--5--3--1 raadt. Er staat dan één getal, namelijk 5, op de juiste plaats, terwijl er twee, te weten 3 en 1, wel goed zijn, maar op de verkeerde plaats staan. Klaas antwoordt dus zwart: 1 en wit: 2. Henk weet dan (bijvoorbeeld) dat de code niet 3--5--1--7 kan zijn, want dan had Klaas zwart: 1 en wit: 3 moeten zeggen. Nogmaals, de getallen in de geheime code zijn verschillend, evenals die in een gok.
Het probleem zit erin uit de binnengekregen gegevens de geheime code af te leiden, en de slimste vragen te stellen. Dit is de kern van het te schrijven C++-programma.
Op ieder moment, na een aantal vragen, is gelet op eerdere antwoorden nog een aantal codes mogelijk; dit noemen we de "toegestane" codes. Aan het begin van het spel zijn alle K(K-1)(K-2)...(K-N+1) codes nog toegestaan (de functie aantal (n,k) uit perm.h, zie verderop). De bedoeling is het aantal toegestane codes snel zo klein mogelijk te maken: als er nog één over is, is het doel bereikt. In bovenstaand voorbeeld kan Henk de code 3--5--1--7 uit de lijst met toegestane codes verwijderen. Uiteraard is er een controle-functie nodig die bij gegeven geheime code en gok de twee getallen wit en zwart uitrekent.
Het is de bedoeling een klasse mastermind te maken, die onder meer memberfuncties heeft als drukaf en doeeengok. Uiteraard heeft deze klasse ook een constructor en een destructor. Verder moeten gedane vragen met behulp van een stapel ongedaan gemaakt kunnen worden, zie verderop.
De mogelijkheid bestaat om gebruik te maken van een aantal voorbeeldfiles, van waaruit de opgave stap voor stap kan worden gedaan. Liefhebbers mogen ook eigen files met andere functies maken, maar gesplitst moet er worden, en niet-gebruik van onderstaande files heeft in principe geen invloed op het cijfer. De files zijn (zie verderop voor gebruik met Code::Blocks):
- File met kleine main: hoofd.cc.
- Headerfile met klassen: mastermind.h.
- Bijbehorende C++-file: mastermind.cc.
- En een file met handige hulp-functies: perm.h.
- Bijbehorende C++-file: perm.cc.
- En de bijpassende makefile (let op de TABs; en noem de file makefile, dus niet makefile.txt).
De handige hulp-functies mogen gebruikt worden, het hoeft niet. Aanpassen ervan is ook toegestaan, mits goed gedocumenteerd. De in perm.h geleverde functie void depermutatie (int nummer, int n, int k, int A[ ]) geeft in het array A de nummer-de toegestane code.
We spelen het spel als volgt. Allereerst wordt bepaald of Henk mens of computer is; dit levert dus al twee varianten. Dan moeten N en K gekozen worden, beide maximaal 10. Tot slot zijn er voor de computer strategieën mogelijk; een mens speelt naar eigen inzicht, waarbij wel wordt gecontroleerd of alle getallen in een gok verschillen.
De te implementeren (en te kiezen) strategieën zijn:
- Computer-Klaas-dom: Kies in het begin als de geheime code een random code.
- Computer-Klaas-slim: Klaas neemt helemaal geen code in gedachten! Als hem een gok wordt aangeboden, geeft hij het (preciezer: een) antwoord dat de toegestane lijst zo lang mogelijk houdt. Schrijf hiertoe een functie sluw (gok,wit,zwart,lengte) die waardes wit en zwart oplevert waarbij zo veel mogelijk codes (lengte stuks) uit de toegestane lijst horen, bij de gegeven gok.
- Computer-Henk-dom: Kies uit de toegestane codes een random-code.
- Computer-Henk-slim: Henk gebruikt ook de functie sluw en kiest een gok, die de kleinste lengte oplevert.
Als een speler aan de beurt is, wordt de situatie —in eenvoudig formaat— op het scherm getoond (als in het "echte" Mastermind), en kan de menselijke speler zijn/haar gok wagen. De eerste maxaantal toegestane codes worden afgebeeld (een door de gebruiker in te stellen aantal), En het programma stopt als de code geraden is (de toegestane lijst bevat nog precies één code), of iemand er genoeg van heeft. Computerzetten worden altijd direct gedaan.
Schrijf een constructor voor de klasse mastermind die een dubbelverbonden pointerstructuur aanlegt, waarbij ieder vakje, naast een array code als inhoud, tevens twee pointers naar voorganger en opvolger heeft. In deze lijst komen de toegestane codes.
[Als dit gedeelte ontbreekt, kost dat 1 punt:] Alle "gokken" moeten op een stapel worden bijgehouden, en gokken van de menselijke speler kunnen daarmee teruggenomen worden. Zodra de speler een gok doet, wordt de gehele oude toestand opgeslagen. Deze wordt, als de speler dat wil, weer hersteld. Liefhebbers: een copy constructor.
Het is de bedoeling om een zes/achttal files te produceren:
de eerste bevat main en het menutje,
de tweede (zeg mastermind.h) bevat de klasse-definitie voor mastermind,
en de derde (zeg mastermind.cc) bevat de functies uit die klasse.
Evenzo zijn er, indien van toepassing,
files stapel.h en stapel.cc.
En dan natuurlijk perm.h en perm.cc.
Stuur ook de makefile mee.
Code::Blocks-gebruikers: doe dit gedeelte liever op een Linux-machine.
Maar het kan wel: open een nieuw project via
"File -- New project -- Empty project", vul wat in,
en voeg de losse files toe via "Project -- Add files",
en daarna het project compileren op de gebruikelijke manier.
Of, op eigen risco, lees
over projecten.
Opmerkingen
Gebruik geschikte (member)functies.
Bij deze opgave mogen wederom bij
elke functie (zelfs main) tussen begin-{ en
eind-} hooguit circa 30 niet al te volle regels staan!
Elke functie dient van commentaar voorzien te zijn.
Let op goed parametergebruik: alle parameters, met uitzondering van membervariabelen, in de heading doorgeven, en de
variabele-declaraties zowel bij main als bij de
andere functies aan het begin.
De enige te gebruiken headerfiles zijn in principe
iostream, cstdlib en ctime
(voor de random-generator).
Zeer ruwe indicatie voor de lengte van de gezamenlijke C++-files: 500 regels.
Denk aan het infoblokje.
Uiterste inleverdatum: vrijdag 5(!) december 2014, 17:00 uur.
Manier van inleveren:
- Digitaal de C++-code
inleveren: stuur een email naar
pm@liacs.leidenuniv.nl.
Stuur geen executable's, lever alleen de drie/vijf/zeven C++-files en de makefile digitaal in! Noem de file mastermind.cc hier bij voorkeur zoiets als garfunkelsimonmastermind4.cc, dit voor de opdracht van het duo Simon-Garfunkel, en analoog de andere files. De perm-files, mits niet gewijzigd, hoeven niet te worden meegestuurd. Zorg dat de makefile werkt met de gebruikte filenamen! De laatst voor de deadline ingeleverde versie wordt nagekeken. - En ook een papieren versie van het verslag
(inclusief de C++-code van alle files, en de makefile) deponeren
in de speciaal daarvoor bestemde doos "Programmeermethoden" in de postkamer
van Informatica, kamer 156 van het Snellius-gebouw.
I&E-studenten (Den Haag) mogen de pdf-versie per email meesturen.
Overal duidelijk datum en namen van de (maximaal twee) makers vermelden, in het bijzonder als commentaar in de eerste regels van de C++-code.
Het verslag (uiteraard weer in LaTeX, zie de eerdere opgaven) moet het volgende bevatten: een zeer korte beschrijving van het programma, een beschrijving van punten waarop het programma faalt (indien van toepassing), en een tabel met gewerkte uren, uitgesplitst per week en per persoon. En een referentie betreffende Mastermind. En tekst en grafiekjes (zie het bijbehorende werkcollege voor tips) die laten zien hoe de verschillende strategieën zich verhouden, bij variërende N en K. Beantwoord ook de volgende vraag: is het verstandig om altijd alleen toegestane codes te gokken?
