LIACS >Kristian Rietveld >Courses >Programmeermethoden NA, Najaar 2017
headerimg

Banner image by Sebastian Niedlich on Flickr, CC BY-NC-SA 2.0

Programmeermethoden NA 2017
Tweede programmeeropgave: Geheim

De tweede programmeeropgave van het vak Programmeermethoden NA in het najaar van 2017 heet Geheim.

De meest recente versie van deze opdracht (met eventuele aanvullingen en verbeteringen) is altijd te vinden op: http://liacs.leidenuniv.nl/~rietveldkfd/courses/prna2017/opdr2.html. Dit is versie 31okt2017.

Er is ook een printer-vriendelijke versie: http://liacs.leidenuniv.nl/~rietveldkfd/courses/prna2017/opdr2.pdf.

Staan er geheime boodschappen in teksten? En wat voor getallen staan in die boodschappen? Deze vragen gaan we beantwoorden!

Aan de gebruiker wordt eerst gevraagd of hij/zij een boodschap wil coderen of juist ontcijferen. Blijf de vraag herhalen totdat de gebruiker een correct antwoord geeft op de vraag. Daarna geeft hij/zij één of twee bestandsnamen: bij het ontcijferen één, bij het coderen twee. Verder geeft hij/zij in het geval van ontcijferen nog een geheim getal: k (geheel, minstens 1, hoogstens 20). Controleer of het gegeven getal geldig is, zo nee, laat dit de gebruiker weten en vraag nogmaals. Bij het coderen wordt deze waarde gegenereerd met de random generator en krijgt hij/zij deze waarde juist te zien. Stel eenvoudige vragen om deze gegevens van de gebruiker te weten te komen. Het programma leest dan eenmalig het opgegeven invoerbestand, en schrijft de uitvoer op de juiste wijze weg naar het uitvoerbestand (bij het coderen) of naar het scherm (bij het ontcijferen). Inlezen en wegschrijven van bestanden mag regel-per-regel gebeuren. Bij het verwerken van een regel mag elk symbool maar één maal gelezen worden.

Een geheime boodschap, evenals de bijbehorende codering, bestaat uit symbolen uit de ASCII-tabel vanaf nummer 32 (spatie) tot en met 125, en "LineFeed"s (LF, \n, 10). Als per ongeluk ook "CarriageReturn"s (CR, \r, 13) worden gebruikt is dat niet erg. De volgorde van de symbolen in de boodschap is dezelfde als de volgorde van de desbetreffende symbolen in het originele bestand. Maar wanneer hoort een symbool tot de boodschap? We leggen hieronder uit hoe het ontcijferen en coderen in zijn werk gaan.

Ontcijferen

Het is een goed idee om te beginnen met het schrijven van de code voor het ontcijferen. Er worden immers handige testbestanden aangeboden. Houd lopend door de tekst bij hoeveel klinkers er zijn gezien. Het eerste symbool na precies k klinkers is deel van de boodschap. Daarna wordt de teller weer op 0 gezet (ook als het symbool zelf een klinker is). Verder wisselt het symbool % (als het niet in de boodschap staat) om tussen het tellen van klinkers en medeklinkers, waarbij de teller ook meteen weer op 0 wordt gezet. Regelovergangen ("LineFeed"s; als ze niet in de boodschap staan) zetten de teller ook op 0, en vanaf dan worden er in alle gevallen weer klinkers geteld. We definiëren als klinker: a, e, i, o en u (kleine letters). Medeklinkers zijn de andere kleine letters.

Verder moet het programma tijdens het ontcijferen getallen in de geheime boodschap detecteren en bepalen of dit wellicht Lychrel-getallen zijn. Na afloop worden het kleinste en grootste getal afgedrukt, en het gemiddelde van de voorkomende getallen — afgerond naar het dichtstbijzijnde gehele getal. Houd alle getallen die worden gevonden in de boodschap bij in een lijst. Schrijf een enkele for-loop die zowel het kleinste, grootste getal en het gemiddelde kan bepalen. Voorkomende getallen hebben maximaal vier cijfers (en dat hoeft niet te worden gecontroleerd). We doen alleen positieve (> 0) gehele getallen. Zo bevat de boodschap 123abcd-"qqq 5"+++uvw-77.88ddd//vb5656p wat ons betreft de gehele getallen 123, 5, 77, 88 en 5656. De boodschap eindigt niet op een cijfer.

Op het scherm wordt naast het desbetreffende getal in de boodschap tussen haakjes afgedrukt wat het aantal iteraties is om tot een palindroom te komen (voor 545 is dit 0, voor 113 is dit 1), of het nummer van de iteratie waarvan het resultaat boven een grens uitkomt. Als grens gebruiken we sys.maxint in het kwadraat (gebruik import sys). Als dit laatste gebeurt, wordt dit erbij vermeld, bijvoorbeeld als "196(81;grens)" als voor getal 196 na 81 iteraties het resultaat boven de grens is uitgekomen.

Coderen

Om een bestand te coderen moet steeds een random karakter worden getrokken totdat er k (mede)klinkers zijn weggeschreven. Het moment is dan daar om het volgende karakter uit de te coderen boodschap weg te schrijven. Het algoritme lijkt erg veel op dat voor het ontcijferen! Maak gebruik van een random-generator: import random en functie random.randint.

Tenslotte moet er bij het coderen voor elke letter worden bijgehouden hoe vaak deze in zowel de invoer (boodschap) als de random getrokken karakters voorkomt. Zet voor dit doeleinde hoofdletters om in kleine letters (doe dit niet in de boodschap zelf!). Tel hoe vaak iedere kleine letter voorkomt. Gebruik bijvoorbeeld lijsten om deze tellingen bij te houden en sla de telling voor a op onder index 0, b onder 1, enz. (Denk aan de functie ord). Als het coderen is voltooid wordt er een net histogram afgedrukt waarin is te zien hoe vaak de verschillende letters voorkomen, zie hieronder voor een voorbeeld. Een balk is maximaal 40 karakters breed. Bepaal de hoogste telling en zorg dat voor deze hoogste telling een balk van 40 karakters wordt getekend. Voor alle andere letters is de breedte van de balk in verhouding tot deze hoogste telling. Voor iedere letter worden twee balken over elkaar heen getekend. De balk voor de oorspronkelijke invoer bestaat uit +-karakters, de balk voor de random getrokken letters uit =-karakters. In het geval een letter niet voorkomt in zowel de oorspronkelijke invoer als de random getrokken karakters, dan wordt deze letter niet opgenomen in het histogram en wordt er geen regel afgedrukt.

Rechts van de balk moet de telling van die letter in de boodschap worden afgedrukt gevolgd door de telling van die letter in de random getrokken karakters.

Het histogram voor test2.txt gecodeerd op k=7 (zie hieronder) ziet er bijvoorbeeld als volgt uit: 

  a | +===================================     |     6 |   166
  b | ======================================   |     1 |   173
  c | =====================================    |     0 |   169
  d | +==================================      |     3 |   161
  e | +++++============================        |    25 |   153
  f | ====================================     |     0 |   166
  g | +=================================       |     3 |   157
  h | +====================================    |     3 |   167
  i | +======================================= |     4 |   183
  j | ==================================       |     0 |   155
  k | ===================================      |     0 |   162
  l | +====================================    |     6 |   170
  m | ===================================      |     2 |   159
  n | ++==================================     |     9 |   165
  o | ==================================       |     1 |   157
  p | ==================================       |     1 |   154
  q | ==============================           |     0 |   136
  r | +=================================       |     5 |   155
  s | +================================        |     6 |   151
  t | ++=================================      |    11 |   161
  u | =====================================    |     1 |   168
  v | ===================================      |     2 |   160
  w | ======================================== |     0 |   182
  x | ======================================   |     0 |   176
  y | ===================================      |     0 |   158
  z | =================================        |     0 |   151
Merk op dat de getallen in de meest rechterkolom bij verschillende runs van het programma zullen verschillen, deze karakters worden immers random getrokken. Voor lagere waarden van k, bijvoorbeeld 2, wordt het histogram wat interessanter: door de lagere waarde in de rechterkolom wordt de balk met +-karakters wat breder.

Testmateriaal

Een tweetal kleine voorbeelden:

  • Met k gelijk aan 2: tekst xxxaxxaGbbaaraaoaauQQaBBic%aaneeeBrhtto levert boodschap Groucho.
  • Met k gelijk aan 3: tekst a55aa1eee2iii3xyuu6uaz levert boodschap 123(1)a.
Een tweetal grotere voorbeelden bestaande uit meerdere regels:

Let op: bestanden van websites downloaden door met rechter muisknop op de links te klikken en dan "save link as ..." te kiezen, anders (met markeer-copy-paste) gaan spaties/tabs wellicht fout!

Een andere leuke manier om te testen is om gecodeerde boodschappen tussen verschillende koppels uit te wisselen! (Maar natuurlijk zonder je Python-programma erbij!)

Opmerkingen

  • We nemen aan dat de gebruiker zo vriendelijk is verder geen fouten te maken bij het invoeren van de bestandsnamen. Bij het invoeren van de keuze coderen/ontcijferen en bij ontcijferen het getal k moet de invoer worden gecontroleerd. Als deze niet klopt wordt de vraag opnieuw gesteld totdat een juiste invoer is gegeven.
  • Schrijf zelf in ieder geval geschikte functies voor de volgende zaken:
    • Het bepalen of een karakter een cijfer, klinker, medeklinker of letter is.
    • Het bepalen van het grootste, kleinste getal en het gemiddelde van een lijst van getallen. Gebruik hiervoor 1 for-loop.
    • En natuurlijk voor dingen als het vragen van invoer aan de gebruiker, het coderen en ontcijferen, bepaling Lychrel-getal, enz...
  • Gebruik zonodig de regelstructuur: elke regelovergang in een bestand bestaat uit een LineFeed (\n) (in UNIX) of een CarriageReturn (\r) gevolgd door een LineFeed (in Windows). Normaal gesproken gaat dit "vanzelf" goed. We nemen aan dat er voor het EndOfFile-symbool (wat dat ook moge zijn) een regelovergang staat.
  • Lezen uit bestanden mag regel-voor-regel, maar het bestand mag maar eenmaal worden ingelezen. Voor het verwerken van de tekst in een regel is slects het huidige karakter en enige kennis over de voorgaande karakters nodig — zie boven.
  • Als je karakters wilt schrijven naar het terminalvenster zonder dat print spaties toevoegt, dan zijn er twee mogelijkheden. Je kunt alle karakters eerst samenvoegeen in een string en vervolgens deze string afdrukken met print. Een andere manier is om gebruik te maken van sys.stdout.write("a"). Dit werkt ook voor bestanden, stel fh is een geopend bestand: fh.write("a").
  • Denk aan het infoblokje dat aan het begin op het scherm verschijnt. Zie de tips bij het vijfde werkcollege. Globale variabelen mogen worden gebruikt om constante waarden te definieren bovenaan het programma, maar zijn verder streng verboden.
  • Wat verwachten we in het verslag? Een korte uitleg van wat het programma doet, aan de hand van kleine eigengemaakte voorbeeldbestanden. Leg uit hoe deze bestanden precies worden gecodeerd. Laat ook het histogram zien dat wordt verkregen bij het coderen. We verwachten ook een definitie van Lychrel-getal en een toelichting hoe de bepaling van deze getallen is geïmplementeerd. Ook moet er een hoofdstuk worden geschreven waarin kort en duidelijk wordt aangegeven voor welke situaties het programma niet werkt, indien van toepassing. Tot slot een tijdsverantwoording, in uren per week voor beide partners. Gebruik een nette tabel en geef ook het totaal aantal gewerkte uren. En vergeet natuurijk niet de code van het programma in het verslag te plaatsen!
    Zie ook het zevende werkcollege.
  • Ruwe indicatie voor de lengte van het Python-programma, inclusief commentaar en eventuele witregels: circa 250 tot 350 regels.

Uiterste inleverdatum: vrijdag 3 november 2017, 17:00 uur.
Manier van inleveren:

  1. Digitaal zowel de Python-code (.py-bestand) als het verslag (in PDF-formaat). Inleveren via BlackBoard. Onder "Content / Course Documents" vind je een onderdeel "Opdracht 2". Geef de bestanden bij voorkeur de namen sXXXXXXX-sYYYYYYY-opdr2.py en sXXXXXXX-sYYYYYYY-opdr2.pdf met op de plekken van XXXXXXX en YYYYYYY de studentnummers van de makers ingevuld. De laatst voor de deadline ingeleverde versie wordt nagekeken.
  2. En ook een papieren versie van het verslag (inclusief de Python-code) deponeren in de speciaal daarvoor bestemde doos "Programmeermethoden NA (Python)" in de postkamer van Informatica, kamer 156 van het Snellius-gebouw.
    Overal duidelijk datum en namen van de twee makers vermelden, in het bijzonder als commentaar in de eerste regels van de Python-code.

Te gebruiken interpreter: Python 2.7. Het programma moet in principe zowel op een Linux-machine, als onder Mac en Windows draaien.
Normering: (consequente) layout 1; verslag 1; commentaar 2; overzichtelijkheid/modulariteit/functies 2; werking 4.