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).
Later komen hier nog eventueel twee files voor stapels bij.
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.
In geval van keuzes (bijvoorbeeld bij gelijke lengtes), mag je
zelf weten hoe je dat aanpakt.
Er worden alleen toegestane codes gevraagd,
maar liefhebbers mogen ook "foute" codes gokken:
misschien is dat wel beter ...
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?
Te gebruiken compiler: als hij maar C++ vertaalt;
het programma moet in principe zowel op een Linux-machine
(met
g++) als onder Visual C++ of Dev-C++ draaien.
Test dus in principe op beide systemen!
Het programma wordt doorgaans nagekeken met behulp van de compiler
die (uiteraard) in het commentaar bovenin het programma vermeld staat.
Normering: layout 1; verslag 1; commentaar 1; modulariteit (OOP, functies) 3;
werking 4.
Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde:
www.liacs.nl/home/kosters/pm/op4pm.php.