Göm menyn

3. Dictionaries och rekursion

Från och med nu ska du använda ett Git-repo (ett filarkiv för versionshantering) som vi har skapat åt dig. Just nu behöver du inte förstå precis allt du gör med detta repo; det kommer vi till senare i kursen. Det räcker med att du följer med i de kommandon vi visar dig.

För att komma igång behöver man först klona repot, det gör man genom att:

  1. Förflytta sig till katalogen där man vill ha repot
  2. Ex: cd kurser/tdde23

  3. Köra följande kommando
  4. git clone [url till git-repo]

    Ex: git clone https://gitlab.liu.se/tdde23-2021/tdde23-2021-labbar-xx-xx-x-xx.git

URL till ditt eget Git-repo får du i eposten när repot har skapats. Det skapas av oss, genom ett script, en tid efter att du har gjort din första inloggning på gitlab.liu.se.

När du har kört git clone är det bara att jobba på som vanligt i filerna i den nya katalogen som har skapats. Om något känns oklart kan du ta hjälp av din labbassistent.

Laboration 3, 4, 5a, 5b och 5c ska, förutom att redovisas muntligt, även skickas in till assistenten, så att du kan få mer detaljerad återkoppling på din kod.

För att göra det utför du följande sekvens av kommandon:

  1. git add -A
  2. git commit -m "meddelande"
  3. Ex: git commit -m "finish lab 3"

  4. git push

Om något känns oklart kan du ta hjälp av din labbassistent.

3.1 Inledning

Studiematerial

Innan denna labb påbörjas bör följande studiematerial ha lästs:

I den andra laborationen övade du på iteration över tal och raka listor. I den här laborationen tränas iterativa och rekursiva sätt att bearbeta mer andra datastrukturer, som tupler (immuterbara listor) och dictionaries

Den här labbomgången innehåller fler övningar än du troligtvis kommer hinna med att göra. Du får själv prioritera vilka som är viktigast för dig, så att du hinner med uppgifterna som ska redovisas.

I detta avsnitt introduceras typerna tupel och dictionary, och ett par små men viktiga detaljer om tillåtna värden repeteras.

Övning 301 Tupler fungerar i princip på samma sätt som listor, men med två noterbara undantag. Den första skillnaden är att tupler står inom vanliga parenteser istället för hakparenteser. Den andra skillnaden kommer du att upptäcka i den här övningen. Tupler kan, precis som listor, innehålla vilka typer av data som helst. Här har vi ett par exempel på representationer av (x, y)-koordinater.

>>> pos_one = (5, 0) >>> pos_two = ('fem', 'noll') >>> pos_three = ([5], [0])

Skriv kommandon som tar fram x-koordinaten respektive y-koordinaten ur var och en av de tre tuplerna ovan. Hur ändrar man koordinaten för pos_one till (5, 5), om det överhuvudtaget är möjligt? Kan det ändras "på plats", utan att använda uttryck som pos_one = ... på liknande sätt som man ändrar enstaka element i en lista? Kan du göra motsvarande med de andra tuplerna?

Övning 302 I en dictionary parar man ihop en nyckel med data. Därefter kan man ta fram data genom att använda nyckeln. Man kan tänka på dem som en slags avancerade listor där man, istället för att använda ett tal som index, använder i princip vilken typ av data som helst. Prova att skriva in följande:

>>> numbers = {"one": 1, "two": 2, "seven": 6, "eight": 9} >>> numbers["one"] 1

För att bekanta dig med hur man använder dictionaries, skriv nu kommandon som gör följande:

  • lägger till nyckeln "three" kopplat till lämplig siffra i numbers.
  • ändrar så att numbers["eight"] ger siffran 8

Övning 303 Här nedanför ser du två sätt att försöka skapa dictionaries. Ett av dem fungerar, det andra gör det inte. Försök förutse vilket som fungerar. Pröva sedan att skriva in det vid Python-prompten och se om du hade rätt.

>>> coodinates_one = { (1, 0, 0): "x-axis", (0, 1, 0): "y-axis" } >>> coordinates_two = { [1, 0, 0]: "x-axis", [0, 1, 0]: "y-axis" }

Varför fungerar bara det ena? Försök också hitta en lista eller tupel (det av exemplen som fungerade här ovanför) som inte fungerar att ha som nyckel.

Övning 304 I den första övningen använde vi tupler för att lagra koordinater. Detta fungerar bra, men för att plocka ut x-koordinaten respektive y-koordinaten ur en sådan tupel behöver man indexera med ett inte särskilt informativt heltal -- man behöver komma ihåg vad som finns på index 0 och index 1. Om man har fler värden i en tupel kan det vara svårare att komma ihåg vad som finns var.

Ett alternativ är att använda dictionaries istället för tupler. Då kan de olika värdena namnges istället för att indexeras. Här har vi ett par exempel på representationer av (x, y)-koordinater i form av dictionaries.

>>> pos_one = { "x": 5, "y": 0 } >>> pos_two = { "x": 'fem', "y": 'noll' } >>> pos_three = { "x": [5], "y": [0] }

Skriv kommandon som tar fram x-koordinaten respektive y-koordinaten ur var och en av de tre dictionaries ovan. Hur ändrar man koordinaten för pos_one till (5, 5), om det överhuvudtaget är möjligt? Kan det ändras "på plats", utan att använda uttryck som pos_one = ... på liknande sätt som man ändrar enstaka element i en lista?

Att använda dictionaries på detta sätt kan i vissa fall vara "overkill", men ofta är det till stor hjälp att olika värden får *namn* istället för bara *index* -- inte minst när man ska läsa koden, felsöka den, eller gå in och ändra i tidigare skriven kod. Är person[7] eller person["birthdate"] lättare att förstå? Är de extra tecknen man behöver skriva värt detta?

3.1 Spelbräde

Uppgift 3A - Spelbräde

Låt oss nu säga att vi ska skriva ett spel där vi ska placera ut relativt få spelfigurer på ett väldigt stort bräde, säg en karta som bryts ned i 100 000x100 000 rutor.

En första tanke vore att göra som i det mindre problemet; att representera det hela som en matris med listor i listor. En tom plats blir en nolla i matrisen och en figur markeras med ett spelarnamn, till exempel. Det kan ha sina fördelar, men fungerar inte så bra när skalan ökas. Säg att vi har fem spelare med 200 figurer var på kartan ovan. Det blir totalt 1000 symboler och inte mindre än 99 999 000 tomma rutor att lagra.

För att slippa lagra en massa tomma rutor explicit kan ett alternativ vara att knyta ihop varje figur och dess position på något sätt. På det sättet får vi 1000 saker att lagra istället för 100 000 000. Alla rutor som inte explicit har någon markering antas då vara tomma, och vi har sparat massor av minnesutrymme.

Din uppgift är att med hjälp av denna insikt, och den nyligen introducerade dictionary-typen, hitta på ett sätt att representera spelbrädet på ett smart sätt. I praktiken innebär det att du ska konstruera följande funktioner: new_board (skapar en ny board), is_free (kollar om en viss plats är ledig), place_piece (placerar en figur på en plats), get_piece (returnerar pjäsen på en viss plats), remove_piece, move_piece, count, nearest_piece (returnera den närmsta pjäsen, och finns det fler pjäser på samma avstånd är det fritt att välja vilken som).

Ditt program ska fungera enligt det belysande exemplet nedan (där varje pjäs helt enkelt antingen är strängen "spelare1" eller "spelare2"):

Var noga med vilket av argumenten som representerar rad (y-koordinat) och vilket som representerar kolumn (x-koordinat).

>>> board = new_board() >>> is_free(board, 500, 100) # Är plats (500, 100), d v s platsen på kolumn 500 och rad 100, ledig? True >>> place_piece(board, 500, 100, "spelare1") # Placera en figur från "spelare1" på position (500, 100). True >>> place_piece(board, 1, 100, "spelare2") True >>> place_piece(board, 500, 100, "spelare2") # Försök placera en figur på en redan upptagen position. False >>> place_piece(board, 500, 200, "spelare2") True >>> is_free(board, 500, 100) False >>> get_piece(board, 500, 100) 'spelare1' >>> get_piece(board, 666,666) False >>> remove_piece(board, 500, 100) # Ta bort figuren på plats (500, 100). True >>> remove_piece(board, 1, 1) # Det fanns ingen figur på den platsen. False >>> is_free(board, 500, 100) True >>> move_piece(board, 500, 200, 500, 100) # Flytta pjäsen på (500, 200) till (500, 100). True >>> get_piece(board, 500, 100) 'spelare2' >>> count(board, "column", 500, "spelare2") # Räkna antalet figurer av typen "spelare2" på rad 500. 1 >>> count(board, "row", 100, "spelare2") 2 >>> nearest_piece(board, 500, 105) # Hitta figuren närmast position (500, 105). (500, 100)

För att räkna ut avståndet mellan två koordinater i den sista funktionen ovan, använd Pythagoras sats. Du kan räkna med att de absolut vanligaste kommandona som spelet använder är is_free och get_piece.

Några tips

  • Läs genom listan på funktioner i exemplet ovan ordentligt. De visar vad du behöver kunna göra med spelbrädet. Testa dina idéer på representation mot dem. Funktionerna ska returnera precis det som står i exemplet. Försöker du använda samma nyckel flera gånger? Går det att se till att man behöver leta genom färre figurer? (Det finns många sätt att resonera här!)
  • När det finns en funktion som utför en viss sak, ska den funktionen alltid användas för att utföra denna sak. Till exempel är det alltid is_free som ska användas om man vill veta om en viss position är ledig, inte bara i "utomstående" kod utan även i de övriga funktionerna som du skriver i denna uppgift. Detta har (minst) tre fördelar. För det första slipper man upprepa kod som implementerar en viss funktionalitet. För det andra bygger man upp sin kod med meningsfulla begrepp som is_free istället för att gå direkt på en intern representation på låg nivå. För det tredje blir det oftast enklare att ändra koden om allt som har med "lediga platser" att göra ligger i en enda funktion, istället för att vara utspritt över många funktioner.
  • Om du har skrivit och testat en funktion, använd när du bygger vidare (istället för att upprepa samma kod igen).

OBS! Denna kurs behandlar inte objektorientering. Om det är något du sysslat med tidigare (eller har råkat läsa om i boken), lägg inte tid på att kapsla in bräden och dylikt i klasser. Det ingår inte i uppgiften!

Testning För att se till att din funktion klarar av uppgiften finns det ett Pythonprogram som kör automatisk testning på din kod. Programmet ligger i filen test3.py och finns redan i ditt Git-repo. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 3A.

3.2 Upprepning med rekursion

I förra laborationsomgången använde vi oss av iteration för att utföra upprepningar. Nu ska vi lösa samma övningar, fast genom att utnyttja rekursion.

Övning 304 Definiera rekursiva funktionen "upphöjt till". Kalla den power och låt den ta två heltalsargument. Funktionen ska vara rekursiv, d.v.s. du får inte använda konstruktioner som for eller liknande.

>>> power(2, 3) 8 >>> power(5, 2) 25

Du kan testa att du gjort rätt genom att jämföra med den inbyggda operatorn ** som beräknar just "upphöjt till". (Givetvis får du inte använda dig av den i funktionen power.)

Övning 305 Definiera en rekursiv funktion sum_first som adderar ihop de första n heltalen. Summan av de n första heltalen kan också beräknas med formeln n(n+1)/2 men i den här övningen vill vi att du summerar talen ett i taget med hjälp av någon form av upprepning (rekursion). Funktionen ska även här vara rekursiv, d.v.s. du får inte använda konstruktioner som for eller liknande.

>>> sum_first(6) 21 >>> sum_first(0) 0

Övning 306 Skriv en funktion sum_numbers som summerar de element på en lista som är tal. Allt annat som finns på listan ska ignoreras. Denna övning ska lösas rekursivt.

Så här kontrollerar du om något är ett tal:

import numbers def is_number(x): return isinstance(x, numbers.Number)

Nu kan du testa om saker är tal med anrop som is_number(5.324).

>>> sum_numbers(["a", 1, "b", 2, [["b", 4], 2], 3]) 6

Övning 307 Skriv en funktion find_letter som returnerar ett sant värde (True) om en given bokstav (egentligen en sträng) finns i ett ord, annars ett falskt värde (False). Ordet representeras som en lista. Denna övning ska lösas rekursivt.

>>> find_letter("u", ["h", "u", "s"]) True >>> find_letter("a", ["b", "i", "l"]) False

Övning 308 Skriv en funktion remove_vowels som tar en lista med bokstäver (egentligen strängar) och returnerar en ny lista med vokalerna borttagna. Det kanske går lättare om du föreställer dig att du ska skapa en ny lista med endast konsonanter snarare än att ta bort vokalerna. Denna övning ska lösas rekursivt. Tips: Använd dig av find_letter som du definierat ovan!

>>> remove_vowels(["b", "i", "r", "g", "i", "t", "t", "a"]) ['b', 'r', 'g', 't', 't']

Övning 309 Skriv en rekursiv funktion range_product som beräknar produkten av alla heltal från nmin till nmax. Produkten av heltal från 2 till 5 räknas inklusive gränserna, och är alltså 2 * 3 * 4 * 5 = 120. Denna övning ska lösas rekursivt.

>>> range_product(5, 10) 151200

Övning 310 Skriv en funktion factorial som beräknar fakulteten av ett heltal n. Fakulteten av 0 definieras som 1. Funktionen ska vara rekursiv, och får gärna anropa funktioner du definierat tidigare.

>>> factorial(5) 120 >>> factorial(0) 1

Uppgift 3B - Pokerhänder

En pokerhand består av 5 kort och en kortlek har 52 kort. Hur många olika pokerhänder kan dras ur en vanlig kortlek? Mer allmänt, på hur många sätt kan man välja k element bland n stycken, utan återläggning och utan ordningen bland de k elementen spelar roll? Som man får lära sig i grundkurser i diskret matematik är svaret (n k) vilket utläses "n över k" och definieras så här:

Din uppgift är att skriva en rekursiv funktion choose som tar två positiva heltal n och k (n >= k) och ger (n k). Lösningen ska vara strikt funktionell, och du får inte använda konstruktioner som for eller liknande.

En klurighet är att din funktion ska klara relativt stora tal. Om man inte tänker efter kan detta göra att delberäkningar blir väldigt - till och med ohanterligt - stora, även om det slutliga svaret är hanterbart.

>>> choose(5, 3) 10 >>> choose(1000, 1) 1000 >>> choose(52, 5) 2598960 >>> choose(1000, 4) 41417124750 >>> choose(1000, 800) 661715556065930365627163346132458831897321703017638669364788134708891795956 726411057801285583913163781806953211915554723373931451847059830252175887712 457307547649354135460619296383882957897161889636280577155889117185 >>> choose(1000, 999) 1000

Ledning: Skriv ned - på papper - hur du beräknar (10 3), (10 5), (10 7), (10 1). Finns det några förenklingar eller omskrivningar som du kan göra? Finns det några tal som blir likadana, men där den ena beräkningen är mycket lättare att göra?

Testning För att se till att din funktion klarar av uppgiften finns det ett Pythonprogram som kör automatisk testning på din kod. Programmet ligger i filen test3.py och finns redan i ditt Git-repo. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 3B.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03