 |
||||
|
Programmeermethoden 2013
Derde programmeeropgave: Nonogram
De derde programmeeropgave van het vak
Programmeermethoden
in het najaar van 2013
heet Nonogram;
zie ook het
achtste werkcollege,
en lees geregeld deze pagina op WWW.
Spreekuur in zalen 302 ... 309:
dinsdag 15, woensdag 16, donderdag 17,
dinsdag 29, woensdag 30, donderdag 31 oktober,
dinsdag 5, woensdag 6, donderdag 7,
dinsdag 12, woensdag 13, donderdag 14 en vrijdag 15 november 2013, van circa
15:30 tot 17:00 uur.
Voor I&E-studenten (Den Haag)
is er een vragenuur in zaal Paleistuin op donderdag 14 november 2013, vanaf circa 14:00 uur.
De opgave
Het is de bedoeling om een C++-programma te maken dat de gebruiker
in staat stelt een Nonogram te maken en op te lossen via een menu-systeem.
Dat betekent dat de gebruiker van het programma kan kiezen
uit een aantal mogelijkheden, de zogeheten opties.
Er is één submenu, waarin ook weer opties zijn.
De bedoeling is dat het hele menu op één of twee
regels staat,
onder de puzzel (zie verderop).
De opties worden gekozen door de eerste letter van de betreffende optie in te toetsen (gevolgd door Enter), bijvoorbeeld een s of S om te stoppen. Uiteraard wordt een en ander duidelijk en ondubbelzinnig aan de gebruiker meegedeeld. Gebruik geen recursie!
Alle door de gebruiker ingetoetste symbolen moeten gecontroleerd worden, dat wil zeggen dat er binnen redelijke grenzen geen foute invoer geaccepteerd wordt. Zo zal het intoetsen van bijvoorbeeld q of & in het hoofdmenu genegeerd worden. Verder moet bij getalleninvoer karakter voor karakter ingelezen worden (met cin.get ( ); als je elders ook nog cin >> ... gebruikt krijg je overigens soms problemen met "hangende Enter's"; gebruik dus overal cin.get ( )). Er moet ook op gelet worden dat er geen te grote getallen worden ingevoerd. Schrijf dus een geschikte functie leesgetal die de gelezen karakters (cijfers) omzet in een getal (tip: negeer alle "voorloop-Enter's"; verwerk alles tot en met de eerstvolgende enter, en maak hiervan zo goed mogelijk een getal, van een maximale grootte; zo kan abc123defg999h, als je een getal kleiner dan 10000 wilt, bijvoorbeeld verwerkt worden tot 1239), en een functie leesoptie die netjes één karakter inleest en Enter's afhandelt! Aan de gebruiker mogen "redelijke" beperkingen worden gevraagd, bijvoorbeeld dat de in te voeren getallen maximaal vier cijfers hebben. Het programma moet dan echter wel bestand zijn tegen pogingen meer dan vier cijfers in te voeren. Ook het invoeren van letters in plaats van cijfers moet geen problemen opleveren. Houd het simpel!
Een Nonogram, ook bekend als
een Japanse puzzel, en niet te verwarren met Sudoku,
is een puzzel waarbij een zwart-wit plaatje moet worden
gereconstrueerd uit zogeheten beschrijvingen.
Het gaat om een rechthoekig m bij n
rooster. Elk vakje = pixel moet zwart (1) of wit (0) worden.
Naast alle rijen en boven alle kolommen staat
een rijtje gehele getallen: de lijn-beschrijving. Zo'n beschrijving geeft, in volgorde, de
lengtes van de aaneengesloten rijtjes zwarte pixels aan.
Zo betekent 3 1 dat er eerst nul of meer witte pixels
komen, dan 3 zwarte, dan een of meer witte, dan 1 zwarte
en tot slot nul of meer witte.
De puzzel bestaat uit het vinden van een plaatje
dat aan alle beschrijvingen voldoet. Een goede
puzzel heeft precies één oplossing.
Zie Wikipedia voor meer informatie,
of maak zelf een puzzel.
We nemen aan dat de hoogte en breedte maximaal 50 zijn.
In ons programma hebben we steeds de zogeheten huidige
totaal-beschrijving en het huidige beeld. In het begin zijn
hier alle lijnbeschrijvingen 0 en alle pixels wit.
Verder hebben we steeds het huidige pixel (de "cursor"), in het begin
ongeveer in het midden van het rooster.
De beschrijvingen staan rechts naast de rijen
en onder de kolommen (dit is makkelijker te doen
dan er voor en er boven, zoals meer gebruikelijk).
Als je wilt kun je nog extra karakters definiëren (een
punt bijvoorbeeld)
voor pixels die, tijdens het puzzelen, zeker wit moeten zijn.
De gebruiker kan nu een aantal zaken doen:
- Stoppen.
- Een klein submenu ingaan, waarin:
- de grootte van de puzzel kan worden gewijzigd, waarbij beschrijvingen en pixels weer 0 worden;
- de gebruiker kan instellen of bij verplaatsen van de "cursor" het nieuwe punt wit of zwart wordt, of niet verandert;
- het random-percentage (zie verderop) kan worden gewijzigd, tussen 0 en 100 procent.
- Maak het huidige beeld leeg = schoon.
- Random vullen van het huidige beeld, met (ongeveer) het door de gebruiker gekozen random-percentage zwarte pixels. Gebruik de random-generator van sheet 6.
- Maak alle beschrijvingen 0.
============================================= - De gebruiker kan de "cursor" één positie omhoog, omlaag, naar links of naar rechts bewegen, uiteraard binnen het rooster. Hierna wordt er opnieuw afgebeeld; het plaatje scrollt dus steeds omhoog.
- Toggelen: het huidige pixel wordt omgeklapt: 0 wordt 1, 1 wordt 0 (of preciezer: false wordt true, true wordt false).
- De beschrijvingen worden de beschrijvingen
van het huidige beeld.
Het beeld klopt daarna dus precies met de beschrijvingen.
============================================= - Inlezen van de huidige beschrijving uit een file.
Formaat: de eerste regel bevat hoogte m
en breedte n, gescheiden door
een spatie.
Daarna komen m regels met rij-beschrijvingen
en n regels met kolom-beschrijvingen.
Elke beschrijving wordt afgesloten met een 0;
zo wordt 3 1 in de file 3 1 0 (met een spatie tussen
de getallen). De beschrijving 0 wordt als 0 gerepresenteerd.
Aangenomen mag worden dat de
files wel het goede formaat hebben.
Zie hier een (lastig) voorbeeld
en nog een
en nog een.
Tip: lees getallen gewoon in met invoer >> getal;. - Wegschrijven van de huidige beschrijving naar een file.
- [OPTIONEEL] Inlezen van het huidige beeld uit een file. Formaat: de eerste regel bevat hoogte m
en breedte n, gescheiden door
een spatie.
Daarna m regels met een rij van het plaatje, met een 1 voor zwart en een 0 voor wit.
Zie hier een voorbeeld.
Wil je van een willekeurig plaatje plaatje.jpg een bestand in (bijna) dit formaat maken, doe dan het volgende (in Linux):
convert plaatje.jpg plaatje.pbm
pnmtoplainpnm plaatje.pbm > invoer.pbm
Uiteraard kan de gebruiker de filenaam kiezen. Als deze niet bestaat: een foutmelding, maar het programma komt weer in het menu terecht. Aangenomen mag worden dat de files wel het goede formaat hebben. - [OPTIONEEL] Wegschrijven van het huidige beeld.
============================================= - Elementair oplossen. Bijvoorbeeld: voor lijnen waarvoor
de beschrijving uit
precies één getal bestaat worden alle pixels zwart gemaakt
die zeker zwart moeten zijn; dit onder de aanname dat het nog "kan".
NB Hier zijn veel mogelijkheden; liefhebbers kunnen hier een master-scriptie over schrijven! Eén punt van de werking is hiervoor gereserveerd. Als deze optie geheel ontbreekt: -1.
Als er in de beschrijvingen getallen met twee of meer cijfers staan, is dit lastig bij de kolommen. Druk dan bijvoorbeeld 10 als A af, 11 als B, enzovoorts. Dat geeft ook wel problemen, overigens.
De bedoeling is een klasse (class) nonogram te maken, met daarin onder meer functies die ieder voor zich een menuoptie afhandelen. De parameters zijn typisch membervariabelen. Gebruik nog geen eigen headerfiles, alles moet deze keer in één file staan.
Opmerkingen
Gebruik geschikte (member)functies.
Bij deze opgave mogen 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, bij voorkeur
één regel boven de functie.
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, fstream, cstdlib en string.
Zeer ruwe indicatie voor de lengte van het C++-programma: 500 regels.
Denk aan het infoblokje.
Uiterste inleverdatum: vrijdag 15 november 2013, 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 C++-file digitaal in! Noem deze bij voorkeur zoiets als jansentilanus3.cc, dit voor de derde opdracht van het duo Jansen-Tilanus. De laatst voor de deadline ingeleverde versie wordt nagekeken. - En ook een papieren versie van het verslag
(inclusief de C++-code) 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 kort eigen onderzoekje waarin een interessante eigen puzzel (uiteraard met een plaatje) wordt bestudeerd, een beschrijving van punten waarop het programma faalt (indien van toepassing), en een tabel met gewerkte uren, uitgesplitst per week en per persoon. Bij het onderzoekje wordt ook verwacht dat er iets staat over mogelijke oplossingsmethoden. Geef ook minstens één nette referentie met \cite. Zie hier hoe je een plaatje verwerkt, en hoe een referentie gemaakt wordt (en zo ziet dat eruit).
