Programmeermethoden 2016
Derde programmeeropgave: Nonogram

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

Spreek/Vragenuur in zalen 302 ... 309: dinsdag 18, donderdag 20 oktober, dinsdag 1, donderdag 3, dinsdag 8, donderdag 10 en vrijdag 11 november 2016, van circa 15:30 tot 17:00 uur. (Vrijdag zelfs vanaf circa 11;15 uur.)
BinnenhofVoor I&E-studenten (Den Haag) is er een vragenuur in zaal Paleistuin op donderdag 10 november 2016, vanaf circa 14:45 uur.
 

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 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:

  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 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.
  5. Maak alle beschrijvingen 0.
    =============================================
  6. 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.
  7. Toggelen: het huidige pixel wordt omgeklapt: 0 wordt 1, 1 wordt 0 (of preciezer: false wordt true, true wordt false).
  8. De beschrijvingen worden de beschrijvingen van het huidige beeld. Het beeld klopt daarna dus precies met de beschrijvingen.
    =============================================
  9. 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;.
  10. Wegschrijven van de huidige beschrijving naar een file.
  11. [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.
  12. [OPTIONEEL] Wegschrijven van het huidige beeld.
Steeds staat bij correcte lijnen een "V": het gaat dus om rijen en kolommen waarbij het huidige beeld precies aan de huidige beschrijving voldoet; dit verandert wellicht als de gebruiker iets aan het huidige beeld wijzigt. Gebruik voor zwarte pixels in het huidige beeld een X, voor witte een spatie, en speciale symbolen voor de "cursor", die op een wit of zwart pixel staat.
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, 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: vrijdag 11 november 2016, 17:00 uur.

Manier van inleveren:

  1. 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.
  2. 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.
    BinnenhofI&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).

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! Het programma wordt doorgaans nagekeken met behulp van de compiler die (uiteraard) in het commentaar bovenin het programma vermeld staat. 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.