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

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

Programmeermethoden NA 2016
Derde programmeeropgave: 2-in-1



Klik hier voor een wat print-vriendelijkere versie.

De derde programmeeropgave van het vak Programmeermethoden NA in het najaar van 2016 heet 2-in-1; zie (te zijner tijd) ook het achtste werkcollege, negende werkcollege, tiende werkcollege, elfde werkcollege, en lees geregeld deze pagina op WWW voor eventuele updates.
Spreek/Vragenuur in zalen 302 ... 309: dinsdag 1, donderdag 3, dinsdag 7, donderdag 10, dinsdag 14, donderdag 16, dinsdag 22, donderdag 24 november 2016, van circa 15:30 tot 17:00 uur; vrijdag 25 november 2016 vanaf circa 11:30 uur.

Deze laatste programmeeropdracht staat geheel in het teken van het oefenen met werken met NumPy en Matplotlib. De opdracht bestaat uit twee componenten, die allen worden aangestuurd via een menu-systeem. De twee componenten zijn Mini Game of Life en Angry Birds, en worden hieronder verder uitgelegd. De liefhebbers mogen voor een bonuspunt ook een derde component implementeren: snelheidstest.

Het programma start zoals altijd met het weergeven van het infoblokje (en vergeet ook het commentaar bovenaan het programma niet!). Daarna volgt een menu met drie keuzes: Game of Life, Angry Birds of afsluiten. (Voor het bonuspunt wordt hier een vierde keuze aan toegevoegd). Schrijf een handige functie die de gebruiker vraagt een keuze in te voeren als geheel getal (dus 1 t/m 3), deze omzet naar een int en controleert of de invoer een geldige keuze is. In het geval geen geheel getal of een ongeldige keuze was ingevoerd, laat dit de gebruiker weten en vraag opnieuw. De returnwaarde is de uiteindelijke, geldige keuze. We kunnen deze functie dan ook direct hergebruiken in de verschillende submenu's.

Bouw het programma op een gestructureerde en modulaire manier op. Maak gebruik van meerdere bestanden. Gebruik bijvoorbeeld drie bestanden: (1) een bestand voor Game of Life met een klasse LifeWereld, (2) een bestand met een klasse AngryBirds en (3) een bestand met de hoofdfunctie (main), alle menus en aansturing. Het laatste bestand is het hoofdbestand en zal imports bevatten voor functies en klassen uit de andere drie bestanden. Implementeer het infoblokje en alle menu's in het hoofdbestand. Roep na het maken van een menukeuze de juiste geimporteerde functie of methode op een klasse aan.

We verwachten boven elk bestand een korte uitleg wat er allemaal in dat bestand is geïmplementeerd, en de namen en studentnummers van de auteurs. Zet bovenaan het hoofdbestand tevens in commentaar: de versie van de gebruikte interpreter, NumPy en matplotlib modules.

Mini Game of Life

In Mini Game of Life kan de gebruiker Life spelen via een menu-systeem. Het is de bedoeling dat het nummer van de huidige generatie, gevolgd door de Life-wereld wordt afgedrukt op het scherm en dat daaronder het menu staat op 1 regel. De menu-opties zijn genummerd en voor de invoer en controle van gekozen opties kan de functie worden gebruikt die we ook al voor het hoofdmenu hadden geschreven.

Van Wiki Life is een cellulaire automaat, in 1970 bedacht door John Horton Conway. Zie verder Wikipedia of hier. We gaan uit van een klein 2-dimensionaal rooster: 20 rijen bij 80 kolommen. We noemen dit de wereld en beginnen met een eindig aantal levende vakjes oftewel cellen. We slaan het rooster op als een twee-dimensionale NumPy-array met als data type bool. True duidt een levende cel aan, False een dode. Een levend vakje met minder dan 2 of meer dan 3 buren van de 8 (horizontaal, verticaal en diagonaal) gaat dood (uit eenzaamheid of juist overbevolking), met precies 2 of 3 levende buren overleeft het. In een dood vakje met precies 3 levende buren ontstaat leven. Dit leidt tot de volgende generatie. Let erop dat dit voor alle vakjes tegelijk gebeurt!

Eigenlijk moet het geheel zich afspelen op een oneindig rooster, maar we kiezen voor de eindige variant. Om moeilijkheden te voorkomen, spreken we af dat de rand van onze wereld altijd uit dode cellen blijft bestaan.

In het Life-menu zijn de volgende opties aanwezig:

  1. Stoppen. Life stoppen en teruggaan naar het hoofdmenu.
  2. Schoon. Maak de wereld leeg (alle cellen in de wereld gaan dood).
  3. Random. Maak de wereld schoon en vul deze met random dode en levende cellen.
  4. Glider. Plaats een Glider in de wereld: 
    xx.
x.x
x..
    (Kies zelf een nuttige locatie).
  5. Een. Er wordt één generatie gedaan.
  6. Gaan. Er wordt een hele serie generaties (bijvoorbeeld 50 of misschien zelfs 300, maak zelf een keuze) gedaan — en allemaal achterelkaar getoond (zonder Enter's).

De bedoeling is een klasse (class) LifeWereld te maken, met daarin onder meer functies (methoden) die ieder voor zich een menuoptie afhandelen. Als het spel begint wordt er dus een klasse LifeWereld geïnstantieerd en worden er voor de gekozen menu-opties de juiste methoden op dit object aangeroepen. Bij Tips is enige inspiratie te vinden voor deze klasse.

Om de code flexibel te houden verwachten we in de klasse member-variabelen voor het volgende: het karakter te gebruiken voor dode cellen, het karakter te gebruiken voor levende cellen en het percentage levende cellen dat moet worden opgeleverd bij het random vullen van de wereld. Kies zelf redelijke standaardwaarden voor deze variabelen die je instelt in de __init__ methode.

Voor de liefhebbers: er zijn natuurlijke vele uitbreidingen mogelijk. Maak bijvoorbeeld een submenu waarin verschillende parameters kunnen worden ingesteld (zoals de karakters en het percentage hierboven). Je kunt ook een optie toevoegen om een Glidergun in de view te plaatsen. Of een veel grotere wereld ondersteunen en de mogelijkheid inbouwen om een view (het op het scherm zichtbare deel van de wereld) te verschuiven ... Maar vergeet niet eerst de rest van de opdracht te maken.

Angry Birds

In het Angry Birds component is het mogelijk Angry Birds te "spelen" door kogelbanen van afgeschoten vogels te plotten. Het spel kan worden gespeeld op verschillende planeten. De data van de planeten moet worden ingelezen uit een bestand, dat hier (planeten.txt) kan worden gedownload. De datapunten per regel zijn gescheiden door tabs (hint: zie ook dictaat, hoofdstuk 8. Regels die beginnen met een # moeten worden beschouwd als commentaarregels en dienen te worden overgeslagen bij het inlezen. De gebruikte eenheden voor de datapunten vind je terug in de commentaarregel van elk bestand. Let erop dat je misschien de datapunten moet omrekenen naar een andere eenheid voor de rest van de opdracht.

Na het kiezen van de optie "Angry Birds" in het hoofdmenu moet de data betreffende de planeten worden ingelezen. De beschikbare planeten worden dan op het scherm gezet en de gebruiker wordt gevraagd op welk van de planeten de vogels zullen worden afgevuurd. Daarna wordt er gevraagd om een bestandsnaam op te geven van een bestand dat de af te vuren vogels bevat. Een voorbeeld kan hier (vogels.txt) worden gevonden. Het programma moet bestanden met een arbitrair aantal vogels aankunnen. Wanneer het bestand niet kan worden gelezen, wordt een nette melding op het scherm gezet en wordt er teruggekeerd naar het hoofdmenu. Schrijf een nette klasse AngryBirds waarin de benodigde functionaliteiten zijn geïmplementeerd.

Vervolgens worden voor de vogels ingelezen uit het gegeven bestand de kogelbanen voor de gegeven planeet berekend. We gaan uit van het volgende:

  • Per planeet worden de massa van de planeet en de radius (de afstand van het middelpunt van de planeet tot de oppervlakte) gegeven. Met deze gegevens kan de valversnelling g worden berekend, welke geldt voor objecten vlakbij de oppervlakte van de planeet: g = GM ⁄ r2. Hiervoor hebben hiervoor de gravitatieconstante nodig: G = 6.67384 × 10-11 N ⋅ m2 ⁄ kg2
  • De vogels hebben geen last hebben van de luchtweerstand en zijn in een vrije val. Per vogel is er een startsnelheid v0 en lanceerhoek θ0 opgegeven. De volgens worden gelanceerd vanaf een lanceerplatform dat zich op 5 meter van de oppervlakte van de planeet bevindt. Hierdoor gaan we ervan uit dat de vogels alleen versnelling ondervinden in de verticale richting (zwaartekracht). De zwaartekracht is een versnelling g die voor een specifieke planeet is berekend. Op basis hiervan kunnen we de volgende (vereenvoudigde) formules gebruiken:
    x - x0 = (v0 cos θ0)t
    y - y0 = (v0 sin θ0)t - 1⁄2gt2

    (x0, y0) is de startpositie van de kogel (de locatie van het lanceerplatform). Voor gegeven tijdstippen t kan met deze formules een locatie (x, y) worden berekend.

    Let op: np.cos verwacht radialen en geen graden. Om graden om te zetten naar radialen kun je gebruik maken van np.deg2rad.
  • Gebruik voor t een tijdspanne van 0 tot en met 20 seconden en genereer 50 tijdstappen (Hint: np.linspace). Bereken voor elk tijdstip de locaties (x, y) voor elke vogel. Hierna kunnen alle banen worden geplot; markeer elk datapunt met een teken (bijvoorbeeld een stip) en zorg voor verbindende lijnen tussen de stippen. Vang de "handles" op zodat je later een legenda kunt maken.

    Opmerking: door slim gebruik te maken van NumPy arrays kun je de locaties voor alle vogels voor 1 tijdstip in 1 keer berekenen. Je past dan dezelfde formule eenmaal toe op een array van N elementen.

Schrijf voor natuurkundige formules die je gebruikt aparte functies. Maak ook netjes de constanten aan. Werk zoveel mogelijk met NumPy arrays en maak gebruik van de eigenschappen hiervan!

De resulterende plot moet op het scherm worden afgebeeld (klik hier voor een voorbeeldplot), waarna er wordt teruggekeerd naar het hoofdmenu. Denk bij de plot aan de titel, labels op de assen en legenda. Ook willen we graag een stippellijn y = 5 zien, dat de hoogte aangeeft waarvan de vogels zijn afgevuurd. Als bereik mag je voor de x-as [0, 150] gebruiken en voor de y-as [0, 80]. De liefhebber mag ook aan de hand van de resultaten geschikte bereiken voor de assen berekenen!

Bonus: Snelheidstest

Het programma bevat twee spellen, Game of Life en Angry Birds, en we moeten de mogelijkheid hebben om na te gaan of de computer snel genoeg is om deze spellen te kunnen spelen. Hiervoor bouwen we een eenvoudige snelheidstest gebaseerd op matrixvermenigvuldiging. Voor matrices van oplopende grootte bepalen we hoe lang de berekening van het product duurt. De resultaten worden weggeschreven als nette plot.

Schrijf een functie om random testmatrices (N-bij-N, N als parameter van de functie) te genereren met gehele getallen tussen 0 en 100. Denk aan np.random.randint! En zorg dat de returnwaarde van het type np.matrix is.

Vervolgens zijn er twee testfuncties nodig die een matrixproduct uitvoeren op matrices A en B en als returnwaarde het resultaat van het product opleveren. De ene past de NumPy operator * toe op twee matrices en gebruikt dus de ingebouwde implementatie van het dot-product. De andere is jullie eigen implementatie van matrixvermenigvuldiging met behulp van for-loops.

De benchmark wordt uitgevoerd door een functie die eerst een zelftest uitvoert: komt het resultaat van onze eigen matrixvermenigvuldigingscode overeen met dat van de NumPy dot-product operator? Daarna worden er voor matrices A en B benchmarks uitgevoerd met verschillende waarden N. Neem bijvoorbeeld N = 22, 23, ..., 26. Bepaal hoe lang elke berekening duurt (zie hiervoor de Tips hieronder). De resultaten moeten worden afgedrukt in een nette plot die het tijdverschil tussen de NumPy operator en zelfgemaakte matrixvermenigvuldiging laat zien. Neem executietijd (run-time) als y en de verschillende N-waarden als x. Vraag de gebruiker om een bestandsnaam waar de plot moet worden weggeschreven. Zorg voor labels bij de assen, een titel en een legenda.

Voor de echte liefhebbers:schrijf ook een matrixvermenigvuldiging die werkt op geneste Python-lijsten (au) en neem deze mee in de benchmark.

Verslag

We verwachten een verslag (uiteraard weer in LaTeX) dat het volgende bevat:

  1. Een korte omschrijving van het programma.
  2. Een beschrijving van punten waarop het programma faalt (indien van toepassing)
  3. Een tabel met gewerkte uren (per week en per persoon).
  4. Een klein onderzoekje waarin een interessante Life-configuratie (bijvoorbeeld van internet; uiteraard met een nette citatie = referentie ("\cite") en twee plaatjes met screenshots van het eigen programma) wordt bestudeerd.
  5. Een interessante plot van Angry Birds. Kies zelf een planeet. Je mag de "standaard"-vogels gebruiken, of zelf een lijstje vogels afvuren. Ook hier weer een korte discussie over iets dat je opviel of interessant is. Om de plot te verkrijgen: maak tijdelijk een aanpassing aan het programma om de plot weg te schrijven ipv op het scherm te laten zien, of gebruik de "Save"-knop in het plot-window. Voor de plots in PDF formaat kun je gebruik maken van de graphicx-package, zie ook het elfde werkcollege.
  6. Voor het bonuspunt: Een plot van de snelheidstest en een (hele) korte discussie van het resultaat.
  7. Voeg de Python code toe door gebruik te maken van LaTeX listings. Graag elk bestand in een aparte sectie en zorg dat het duidelijk is wat de naam is van elk bestand.

Opmerkingen & Tips

  • Zeer ruwe indicatie voor de lengte van het Python-programma, inclusief infoblokje en commentaren: 450 - 500 regels.
  • Hoe kunnen we zien of het omzetten naar een int (bijvoorbeeld voor menukeuzes) goed gaat? 
    juist = True
try:
    keuze_als_int = int(ingevoerde_keuze)
except ValueError:
    juist = False
  • Ter inspiratie een beginnetje van een klasse LifeWereld: 
    class LifeWereld(object):
    '''Bevat alle data van de huidige wereld en methoden om een nieuwe
    generatie uit te rekenen en de wereld aan te passen.'''
    def __init__(self, hoogte, breedte):
        self.hoogte = hoogte
        self.breedte = breedte
        self.generatie = 0

        self.wereld = np.zeros( (..., ...), dtype=np.bool8)
        # enz ...

    def afdrukken(self):
        '''Drukt de wereld af naar standard output.'''
        pass

    def schoon(self):
        '''Verschoon de wereld: alle cellen worden gedood.'''
        pass

    def random(self):
        pass

    def plaats_glider(self, rij=10, kolom=30):
        '''Plaats een glider op positie (rij, kolom); dit is de linkerbovenhoek
        van de glider.'''
        pass

    # TODO: enzovoort
  • Hoe kunnen we de executietijd van een stuk code bepalen? 
    import timeit

def doeVeelWerk(A, B):
    # TODO
    pass

def benchmark():
    A = ...
    B = ...

    # Doe het experiment: 10 herhalingen
    resultaat = timeit.timeit(lambda: doeVeelWerk(A, B), number=10)

    # 'resultaat' bevat de tijd in seconden om de code 10 keer uit te voeren.
    # Vergeet dus niet door 10 te delen. Eventueel omzetten naar
    # milliseconden.

Inleveren

Uiterste inleverdatum: vrijdag 25 november, 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-bestanden digitaal in! Stuur bij voorkeur een zip of tar.gz bestand dat alle Python-bestanden met een naam als sXXXXXXX-sYYYYYYY-opdr3.tar.gz, waarbij XXXXXXXX en YYYYYYY de studentnummers zijn van de makers, en opdr3 voor de tweede opdracht. Als dat niet lukt, is het ook prima alle Python-bestanden als losse attachments op te sturen. Gebruik geen spaties in de bestandsnamen. .pyc-bestanden hoeven niet te worden meegestuurd. 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 alle 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.
Te gebruiken interpreter: Python 2.7.

Normering: layout 1; verslag en commentaar 2.5; modulariteit (OOP, functies) 2; werking 4.5.

Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde: http://liacs.leidenuniv.nl/~rietveldkfd/prna2016/opdr3.html.