Programmeermethoden 2023
Derde programmeeropgave: Nonogram

De derde programmeeropgave van het vak Programmeermethoden in het najaar van 2023 heet Nonogram; zie ook het zevende werkcollege, achtste werkcollege en negende werkcollege, en lees geregeld deze pagina op WWW.

De opgave

Enigma 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 de menukeuzes op één of twee regels staan, 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 (tenzij er een optie Q is ...). 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 (rijen) bij n (kolommen) rooster. Elk vakje = pixel moet zwart (1/true) of wit (0/false) 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 één 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. 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 zien we steeds het "huidige pixel", ook wel de "cursor" genoemd, in het begin ongeveer in het midden van het rooster. (Zorg ervoor dat op de een of andere manier deze locatie duidelijk gemarkeerd is.) 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:

  1. Stoppen.
  2. Een klein submenu ingaan, waarin:
    • de grootte van de puzzel kan worden gewijzigd, waarbij beschrijvingen en pixels weer 0 worden;
    • de gebruiker de symbolen die voor witte en zwarte pixels gebruikt worden kan kiezen (uiteraard twee verschillende);
    • [OPTIONEEL] 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.
  3. Maak het huidige beeld leeg = schoon.
  4. Random vullen van het huidige beeld, met (ongeveer) het door de gebruiker gekozen random-percentage zwarte pixels. Gebruik de random-generator van sheet 10 van het achtste college.
    =============================================
  5. 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.
    Gebruik speciale symbolen voor de plek van de cursor, op zowel een wit als een zwart pixel.
  6. Toggelen: het huidige pixel wordt omgeklapt: 0 wordt 1, 1 wordt 0 (of preciezer: false wordt true, true wordt false).
  7. De beschrijvingen worden de beschrijvingen van het huidige beeld. Het beeld klopt dan dus precies met de beschrijvingen.
    =============================================
  8. 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;. Controleer ook of de file bestaat.
  9. Wegschrijven van de huidige beschrijving naar een file.
  10. [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 -resize 40x40 plaatje.pbm
       pnmtoplainpnm plaatje.pbm > invoer.txt
    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.
  11. [OPTIONEEL] Wegschrijven van het huidige beeld.
Steeds staat bij correcte lijnen een "V": het gaat dus om rijen (ernaast) en kolommen (eronder) waarbij het huidige beeld precies aan de huidige beschrijving voldoet; dit verandert wellicht als de gebruiker iets aan het huidige beeld wijzigt. Als dit onderdeel geheel ontbreekt, kost dat 1 punt.

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.

De bedoeling is een klasse (class) nonogram te maken, met daarin onder meer functies die ieder voor zich een menuoptie afhandelen, zoals vulrandom. 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: maandag 13 november 2023, 18:00 uur.

Manier van inleveren (één exemplaar per koppel, dat — ter herinnering — uit maximaal twee personen bestaat) is als volgt:

  1. Digitaal de C++-code inleveren via Brightspace > Course Tools > Assignments. Stuur geen executable's, LaTeX-files of PDF-files, lever alleen één C++-file digitaal in!
  2. En ook een papieren versie van het verslag (inclusief de C++-code) deponeren in de speciaal daarvoor bestemde doos "Programmeermethoden" bij kamer 159 van het Snellius-gebouw.
    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 korte beschrijving van het programma (inclusief definitie van Nonogram), een plaatje van het programma in werking, een beschrijving van punten waarop het programma faalt (indien van toepassing), en een tabel met gewerkte uren, uitgesplitst per week en per persoon. Geef ook minstens één nette referentie, bij de definitie van Nonogram, met \cite. Zie hier hoe je een plaatje verwerkt, en hoe een referentie gemaakt wordt (en zo ziet dat eruit). Te gebruiken compiler: als hij maar C++ vertaalt; het programma moet in principe zowel op een Linux-machine (met g++) als onder Code::Blocks draaien. Test dus in principe op beide systemen! Normering: verslag 1; layout 1; commentaar 2; modulariteit (OOP, functies) 2; werking 4. Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde: www.liacs.leidenuniv.nl/~kosterswa/pm/op3pm.php.