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

Programmeermethoden NA 2016
Tweede programmeeropgave: DeCode

De tweede programmeeropgave van het vak Programmeermethoden NA in het najaar van 2016 heet DeCode; zie ook het vierde werkcollege, vijfde werkcollege, zesde werkcollege, zevende werkcollege, en lees geregeld deze pagina op WWW voor eventuele updates.
Spreek/Vragenuur in zalen 302 ... 309: dinsdag 27, donderdag 29 september, dinsdag 4, donderdag 6, dinsdag 11, donderdag 13, dinsdag 18, donderdag 20 oktober 2016, van circa 15:30 tot 17:00 uur; vrijdag 21 oktober 2016 vanaf 11:15 uur.

De compressietechnieken GIF en JPEG dreigen steeds duurder te worden. We gaan het nu dus maar zelf doen. Voor de tweede programmeeropgave moet een programma worden geschreven dat een file kan coderen en decoderen. En staan er "Lychrel-getallen" in de file?
Aan de gebruiker wordt gevraagd of het om coderen of decoderen gaat en hoe de originele (bestaande) file en de "doelfile" heten. De veranderde invoerfile komt in deze doelfile terecht; de invoerfile zelf blijft onveranderd. Stel eenvoudige vragen om deze gegevens van de gebruiker te weten te komen. Het programma leest dan eenmalig, symbool voor symbool, de opgegeven invoerfile, en schrijft de uitvoer, eveneens symbool voor symbool, weg naar de uitvoerfile. Elk symbool uit de invoerfile mag en moet precies één maal (met invoer.read(1)) gelezen worden.

Na het coderen moet de compressierate (de verhouding tussen het totale aantal karakters van doelfile en oorspronkelijke file) in gehele procenten (netjes afgerond) op het beeldscherm afgedrukt worden, evenals het totaal aantal regels dat is verwerkt. (Overigens, het aantal ingelezen karakters kan wat schelen tussen verschillende systemen.)

Het coderen geschiedt regel voor regel (hoe detecteer je een regelovergang?), en gaat als volgt. Iedere opeenvolging van k (groter dan of gelijk aan 2) dezelfde karakters binnen een regel wordt vervangen door dat karakter onmiddellijk gevolgd door het getal k. Een enkel karakter blijft gewoon zichzelf, evenals regelovergangen. Zo wordt de te coderen regel
Eet meer          zeeegels gecodeerd als Eet me2r 10ze3gels (in de originele zin staan blijkbaar tien spaties tussen meer en zeeegels).

Om later te kunnen decoderen hadden we moeten aannemen dat er geen cijfers in de regel staan, immers wat zou anders de codering e434 betekenen — vier e's en vier 3-en of 434 e's? Om dat probleem op te lossen worden gecodeerde cijfers voorafgegaan door een \ (backslash). De backslash zelf wordt met twee backslashes gecodeerd. Zo moet ABC11123ddd\efG\\\1 gecodeerd worden als
ABC\13\2\3d3\\efG\\3\1. Deze codering heet officieel run-length encoding.

Verder moet het programma van elk geheel getal dat bij het coderen in de invoerfile voorkomt controleren of dit wellicht een Lychrel-getal is. Op het scherm wordt het desbetreffende getal afgedrukt, en daarnaast 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 sys.maxint (gebruik import sys) uitkomt (voor 196 is dit (waarschijnlijk) 18 op 32-bit systemen, 40 op 64-bit systemen). Als dit laatste gebeurt, wordt dit erbij vermeld. We gebruiken dit limiet om de berekening niet uit de hand te laten lopen ...

De tekst 123abcd-"qqq 5"+++uvw-77.88ddd//vb5656 bevat de gehele getallen 123, 5, 77, 88 en 5656; deze moeten dus gecontroleerd worden. Je mag aannemen dat de getallen in de tekst zelf hooguit sys.maxint zijn.

Tenslotte moet er bij het decoderen voor elke kleine letter ('a' tot en met 'z') worden bijgehouden hoe vaak elk van deze in de uitvoer terecht komt. Gebruik bijvoorbeeld een lijst en sla de telling voor a op op index 0. Als het decoderen is voltooid, wordt er een net histogram afgedrukt waarin is te zien hoe vaak de verschillende karakters in de uitvoer voorkomen. Teken voor elk karakter een balk bestaande uit =-karakters. Zorg ervoor dat de balk voor de letter die het vaakst voorkwam een lengte heeft van 40 karakters. Voor alle andere karakters is de lengte van de balk in verhouding tot de letter die het vaakst voorkwam. Sla alle karakters die niet in de uitvoer voorkomen over en druk hiervoor geen regel af. Het histogram ziet er bijvoorbeeld als volgt uit:

  a | =========                                | 28
  b | ===                                      | 9
  c | =                                        | 4
  d | =====                                    | 15
  e | ======================================== | 118
  f | =====                                    | 16
  g | ====                                     | 12
  h | ====                                     | 11
  i | =========                                | 26
  j | ===                                      | 9
  k | =======                                  | 20
  l | ========                                 | 25
  m | ========                                 | 24
  n | ================                         | 46
  o | ==================                       | 52
  p | ==                                       | 7
  r | ===============                          | 45
  s | =====                                    | 14
  t | ================                         | 47
  u | ====                                     | 13
  v | ===                                      | 9
  w | ==                                       | 6
  z | =                                        | 2

Ter verdere inspiratie, zie het vijfde werkcollege en het zesde werkcollege. De volgende testinvoeren kunnen worden gebruikt om het uiteindelijke programma te testen. Maak bij het ontwikkelen van het programma zelf testinvoeren die steeds een stapje moeilijker worden.

• Eenvoudige testinvoer: test2016.txt met bijbehorende uitvoerfile test2016uit.txt; invoerfile 975 bytes; uitvoerfile 630 bytes; 37 regels; compressie 65%.
• Moeilijke testinvoer: moeilijk2016.txt met bijbehorende uitvoerfile moeilijk2016uit.txt; invoerfile 1168 bytes; uitvoerfile 1229 bytes; 50 regels; compressie 105%.

Let op: download het bestand en sla deze op in je home-directory door met rechter muisknop op de hyperlinks te klikken! Anders (met markeer-copy-paste) gaan spaties/tabs wellicht fout!

Opmerkingen (belangrijk!)

• 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/decoderen moet de invoer worden gecontroleerd. Als deze niet klopt wordt de vraag opnieuw gesteld totdat een juiste invoer is ingegeven.
• Gebruik geen Python-libraries. Alleen sys mag worden gebruikt voor sys.maxint. Schrijf verder zelf geschikte functies voor de volgende zaken (om te oefenen met programmeren en te begrijpen wat er gebeurt):
  • Het omkeren van een gegeven string.
  • Het bepalen of een gegeven karakter een cijfer is.
  • Het bepalen of een gegeven karakter een kleine letter is.
  • En natuurlijk voor dingen als het vragen van invoer aan de gebruiker, het coderen en decoderen, bepaling Lychrel-getal, enz...
  Bij het inlezen van invoerbestanden moeten er getallen worden gedetecteerd (zowel bij het coderen als decoderen). Schrijf ZELF de benodigde code om de ingelezen cijfers om te zetten in een integer getal. We staan in dit geval niet toe dat een conversiefunctie zoals int() wordt gebruikt om een string naar een integer om te zetten.
• Gebruik zonodig de regelstructuur: elke regelovergang in een bestand bestaat uit een LineFeed (\n) (in UNIX) of een CarriageReturn gevolgd door een LineFeed (\r\n) (in DOS/Windows). Normaal gesproken gaat dit "vanzelf" goed. We nemen aan dat er voor het EndOfFile-symbool (wat dat ook moge zijn) een regelovergang staat.
• Voor het lezen en verwerken van de tekst is slechts het huidige karakter en enige kennis over de voorgaande karakters nodig. Uit een file mag alleen met invoer.read(1) gelezen worden, vergelijk Hoofdstuk 8 uit het Collegedictaat Python. Binnen de hoofdloop van het programma staat bij voorkeur maar één keer een read(1)-opdracht, vergelijk het voorbeeldprogramma uit dit hoofdstuk (daar staat twee keer read(1), één maal vóór de loop, uiteraard). Karakters mogen niet worden teruggezet in de oorspronkelijke file.
  
• Denk aan het infoblokje dat aan 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. Ruwe indicatie voor de lengte van het Python-programma: circa 250 tot 350 regels.

Uiterste inleverdatum: vrijdag 21 oktober 2016, 17:00 uur.
Manier van inleveren (één exemplaar per koppel, dat — ter herinnering — uit twee personen bestaat):

1. Digitaal de Python-code inleveren: stuur een email naar prna2016@handin.liacs.nl.
   Lever alleen de Python-file digitaal in! Noem deze bij voorkeur zoiets als sXXXXXXX-sYYYYYYY-opdr2.py, waarbij XXXXXXXX en YYYYYYY de studentnummers zijn van de makers, en opdr2 voor de tweede opdracht. Gebruik geen spaties in de bestandsnaam. Vermeld in de e-mail ook de namen en studentnummers van de makers. 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" 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. Lees bij het zevende werkcollege hoe het verslag eruit moet zien. Zijn spaties/tabs goed verwerkt?

Te gebruiken interpreter: Python 2.7. Het programma moet in principe zowel op een Linux-machine, als onder Mac en Windows draaien. Update 18 oktober 2016: Normering: (consequente) layout 1; verslag 1; commentaar 2; modulariteit/overzichtelijkheid 2; werking 4. Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde: http://liacs.leidenuniv.nl/~rietveldkfd/prna2016/opdr2.html.