Uke 8 — Problemløsning ====================== Eksempler --------- Vi skal se på noen eksempler på hvordan man kan løse problemer ved hjelp av programmering. Fokusen denne uken ligger på identifisering av programmeringsstrukturer: if-setninger, for-løkker, etc. Eksempel 1 .......... Først skal vi jobbe sammen i grupper for å løse oppgaven i denne lille teksten: Du jobber med et prosjekt hvor du må sortere en gruppe mennesker i to grupper: eksperter og ikke-eksperter, basert på et egenrapportert nivå av kompetanse i et biologitema fra 0 (ikke kunnskapsrik) til 5 (ekstremt kunnskapsrik). De som har sagt nivå 4 eller 5 burde bli plassert i gruppen "eksperter" mens resten burde bli plassert i gruppen "ikke eksperter." Beskriv for hverandre hvordan du vil løse oppgaven med programmering. Hva er forventet input? Hva skal du skrive ut? Hvor vil du bruke for-løkker, if-setninger eller funksjoner? **Det er nok å skissere en løsning, du trenger ikke å programmere noe.** Eksempel 2 .......... Vi skal løse `Problem 2 fra projecteuler.net `_: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: .. math:: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. Dette problemet kan deles opp i to deler: først må vi finne alle tall i Fibonaccisekvensen som er mindre enn fire millioner, så summerer vi alle av disse som er partall. For å beregne Fibonaccisekvensen må vi gjøre samme ting (å addere de to forrige tallene) mange ganger. Dette er hva en loop er til for. Vi vet ikke hvor mange ganger vi må beregne nye tall, vi vet bare at vi skal slutte når vi får et tall som er større enn fire millioner. Derfor bruker vi en while-løkke. Vi må også lagre alle tallene på noen måte. Til dette bruker vi en liste. Så vår kode skal være noe slikt: .. code-block:: python fib = [] # Fibonaccisekvensen fib.append(1) # Vi må ha de første to tallen i sekvensen før løkken fib.append(2) while n < 4000000: # n er det seneste tallet i sekvensen # Beregne neste tall i sekvensen # Putte tallet i slutten av fib For å beregne neste tall i sekvensen skal vi addere de to forrige tallene. Derfor må vi hele tiden lagre de to forrige tallene sånn at vi kan bruke dem i neste omgang av løkken. La :math:`m` være tallet før :math:`n`, og la :math:`l` være tallet før :math:`m`. Så for eksempel, i begynnelsen er :math:`l=1` og :math:`m=2`. I neste omgang er :math:`l=2` og :math:`m=3` etc. Vi bruker så disse for å beregne :math:`n` . Vår kode blir da noe slikt: .. code-block:: python fib = [] # Fibonaccisekvensen l = 1 m = 2 fib.append(l) # Vi må ha de første to tallen i sekvensen før løkken fib.append(m) n = 0 # n må være definert før løkken while n < 4000000: # n er det seneste tallet i sekvensen n = l + m fib.append(n) l = m # l og m må oppdateres m = n Nå har vi alle tall i Fibonaccisekvensen som er mindre enn fire millioner. Nå må vi beregne summen av alle av disse som er partall. Her passer det også å bruke en løkke fordi vi vil gå gjennom hele listen ``fib`` og gjøre noe: sjekke om tallet er partall, og (hvis det er et partall) addere det til summen. Når vi vil gjøre noe for alle elementer i en liste bruker vi en for-løkke. Koden blir: .. code-block:: python fib = [] # Fibonaccisekvensen l = 1 m = 2 fib.append(l) # Vi må ha de første to tallen i sekvensen før løkken fib.append(m) n = 0 # n må være definert før løkken while n < 4000000: # n er det seneste tallet i sekvensen n = l + m fib.append(n) l = m # l og m må oppdateres m = n sum = 0 # Summen må være definert før løkken for n in fib: if n % 2 == 0: sum += n print(sum) # Sånn at vi får vite hva summen er Du kan finne hele koden her: :download:`eksempel_fibonacci.py`. Diskuter andre løsingsforslag. Kan vi løse oppgaven uten lister? Hva er fordeler / ulemper med ulike løsninger? .. Eksempel 2 .......... Vi skal løse `Problem 14 fra projecteuler.net `_: The following iterative sequence is defined for the set of positive integers: .. math:: \begin{align*} &n \rightarrow n/2 &(\text{n is even}) \\ &n \rightarrow 3n + 1 &(\text{n is odd}) \end{align*} Using the rule above and starting with 13, we generate the following sequence: .. math:: 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (`Collatz Problem `_), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? **Note:** Once the chain starts the terms are allowed to go above one million. Vi skal beregne nesten en million sekvenser: for hvert tall :math:`n < 1000000` skal vi beregne sekvensen som begynner på :math:`n`. Så skal vi beregne lengden på alle disse sekvensene og se hvilken startverdi som produserer den lengste listen. Dette kan vi dele opp i ulike deler. Én del er koden som beregner sekvensen fra en startverdi. Når vi beregner en sekvens vil vi gjøre samme ting mange ganger. Derfor skal vi bruke en løkke. Siden vi ikke vet hvor mange ganger løkken skal kjøres, men vi vet når den skal avsluttes (når vi kommer til :math:`1`), bruker vi en while-løkke. Vi lagrer sekvensen i en liste, slik som i eksempel 1. Koden blir:: def colz_seq(n): seq = [] seq.append(n) # n er startverdien while n != 1: if n % 2 == 0: n = n // 2 else: n = 3 * n + 1 seq.append(n) return seq Vi vil nå beregne lengden av sekvensen for alle startverdier under én million. Dette gjør vi med en for-løkke over ``range()`` og lagrer alle lengdene i en liste (vi må ikke lagre alle sekvensene, bare lengdene):: lengths = [] for n in range(1, 1000000): lengths.append( len(colz_seq(n)) ) # colz_seq(n) er en funksjon som beregner sekvensen fra startverdien n Vi vil nå vite hvilken startverdi som gir lengst lengde. Derfor må vi beregne maksimum av ``lengths`` og finne startverdien som gav den lengden. Startverdien er én mer enn index av lengden i listen ``lengths``. Vi kan bruke ``.index()`` for å finne index for maksimum i listen ``lengths``. Koden blir:: m = max(lengths) start_value = ( lengths.index(m) + 1 ) # Om flere startverdier gir samme lengde får vi her bare det første av disse tallene Du får nå selv sette dette sammen til en kodefil som gir deg svaret på spørsmålet. Hva er svaret? Diskuter andre løsingsforslag. Kan vi løse oppgaven uten lister? Hva er fordeler / ulemper i de ulike løsninger? Eksempel 3 .......... Her skal vi lage en enkel simulasjon av en populasjonsmodell. På en liten øy finnes :math:`x=400` sauer og :math:`y=20` ulver. Uten ulver vokser antallet av sauer eksponensielt over tid. Uten sauene forsvinner alle ulvene etter en stund. Når begge finnes på øyen, går antallet ulver litt opp i hvert tidsskritt, og antallet sauer går ned avhengig av hvor mange ulver og sauer det finnes. I vårt eksempel skal tallene forendres slikt etter et tidsskritt :math:`\Delta t`: .. math:: \Delta x = \left( \frac{2}{3}x - \frac{1}{15}xy \right) \Delta t\\ \\ \Delta y = \left( \frac{1}{400}xy - y \right) \Delta t På hvert tidspunkt vil vi vise hvor mange ulver og sauer vi har. Vi kan bruke ``print`` for å lage et enkel søylediagram ved å skrive ut ulike antall ``'x'`` og ``'.'`` i hvert tidsskritt. Prøv å skissere en løsning, og diskuter med andre i din gruppe. Så kan du se på vårt løsningsforslag her: :download:`wolf_sheep.py`. .. .. literalinclude:: wolf_sheep.py (De som er interessert kan finne mer om denne typen ligningssystemer under stikkordet `Lotka-Volterra equations `_. ) Oppgaver -------- .. note:: Oppg.1 og 2 er obligatoriske. I tillegg velg **to** fra oppg. 3, 4 og 5 å levere. Totalt må du levere inn *4* av oppgavene. Om du vil kjøre pytests lokalt (tilgjengelig for 1,2,4 og 5) kan du laste ned zip-filen her: :download:`uke_08_tests.zip` Oppgave 1 ......... **Pearsons korrelasjonsligning** er gitt av: .. math:: r = \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_i(x_i - \bar{x})^2 \sum(y_i - \bar{y})^2}} :math:`(x, y)` er tidsserier (hver er en liste med målinger) og :math:`(\bar{x}, \bar{y})` er de tilsvarende gjennomsnittene av hver liste. I filen ``uke_08_oppg_1.py`` implementer Pearsons korrelasjonsligningen som funksjonen ``pearson_corr(x,y)`` som tar som argumenter to lister `x` og `y` og returnerer koeffisienten :math:`r` hvor :math:`-1 \leq r \leq 1`. Fremgangsmåten: 1. Ta gjennomsnittet av :math:`x` i variabelen ``mean_x`` og :math:`y` i variabelen ``mean_y``. 2. Lag listene ``dx`` and ``dy`` som inneholder forskjellene :math:`(x_i - \bar{x})` og :math:`(y_i - \bar{y})`. 3. Multipliser hvert sitt element sin forskjell fra gjennomsnittet i x -listen med forskjellen fra gjennomsnittet i y -listen ``dx[i] * dy[i]``. Summer disse multipliserte verdiene og lagre dem i variabelen ``sum_dxdy``. .. note:: **TIPPS:** Du kan bruke `sum()` og `zip()` for å hjelpe med beregningen til produktet av forskjellene for hvert parvis listeelement for å oppsummere disse resultatene. 4. Lag nye variabler ``dx2`` og ``dy2`` som summen av de kvadrerte forskjellene: ``dx2`` :math:`= \sum_i(x_i - \bar{x})^{2}` og ``dy2`` :math:`= \sum_i(y_i - \bar{y})^{2}`. 5. Multipliser ``dx2`` og ``dy2`` og ta kvadratroten til produktet. Lag resultatet i variabelen ``sqr_dx2dy2``. 6. Til slutt, beregne korrelasjonskoeffisienten ``r`` som divisjon av ``sum_dxdy`` med ``sqr_dx2dy2``. Variabelen ``r`` er resultatet som funksjonen returnerer. Du kan teste funksjonen din med disse verdiene: .. code-block:: python x1_ls = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] y1_ls = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] y2_ls = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] >>> pearson_corr(x1_ls, y1_ls) 1.0 >>> pearson_corr(x1_ls, y2_ls) 0.7751168025822525 Oppgave 2 ......... Måltidsplanlegging for late mennesker Du hadde en lang dag på skolen og du vil ikke dra til matbutikken på veien hjem. Du vet hva som finnes i kjøleskapet ditt og du har fire måltider som du elsker å lage ofte. Siden du tar INF100 bestemmer du deg for å lage en algoritme som finner de måltidene som du kan lage med det du har i kjøleskapet ditt. Mat i kjøleskapet og måltider er laget til i en liste, f.eks: .. code-block:: python # contents of my fridge, in a list my_fridge = ["tomato sauce", "mustard", "potatoes", "carrots", "chicken", "frozen fish"] Måltider er laget til en tuple av tupler: .. code-block:: python # meals and corresponding ingredients stored in tuple of tuples meals = ( # name of dish [0], ingredients [1] ("fish_sticks", ("frozen fish", "potatoes", "mustard")), ("chicken_curry", ("chicken", "curry paste", "carrots", "potatoes", "rice")), ("chicken_veg", ("chicken", "potatoes", "carrots")), ("pasta", ("spaghetti", "tomato sauce")), ) **Løs oppgaven i tre steger**. I filen ``uke_08_oppg_2.py`` gjør følgende: 1. Implementer en funksjon som heter ``meal_list()`` som tar som input to argumenter: (1) listen av ingredienser i kjøleskapet ditt og (2) tuplen av ingredienser til en måltid. Funksjonen returnerer ``True`` (du har alle ingredienser for å lage måltiden) eller ``False`` (du har **IKKE** alle ingredienser for å lage måltiden). Bruk kodeskissen nedenfor for å komme i gang hvis du vil. .. code-block:: python def meal_list(fridge, ingredient_list): """ 1. set up a tally that counts the ingredients you do have for a given meal in your fridge 2. _for each_ ingredient in a meal 3. check _if_ that ingredient is in your fridge 4. _add_ to tally of ingredients for a given meal that are in your fridge 5. once you have looped through the ingredient list, check _if_ your count tally matches the number of items in the ingredient list """ count = 0 # skriv koden her return count == len(ingredient_list) Eksempelkjøring: .. code-block:: python >>> meal_list(my_fridge, meals[0][1]) True 2. Så lag en annen funksjon som heter ``meal_options()`` for å finne måltidene du kan lage med ingrediensene du har i kjøleskapet ditt: .. code-block:: python def meal_options(fridge, meals): """ 1. _for each_ tuple pair in meals 2. run meal_list() 3. _if_ function evaluates to `True`, then add to a new list of meals that are possible to make """ meal_options_ls = [] # your code here return meal_options_ls Eksempelkjøring: .. code-block:: python >>> meal_options(my_fridge, meals) ['fish_sticks', 'chicken_veg'] 3. Til slutt, lag en siste funksjon som heter ``to_buy()`` at for et gitt måltid du ønsker å lage returnerer listen over ingredienser du må kjøpe fra butikken for å lage. Funksjonen tar som input to argumenter: (1) listen av ingredienser i kjøleskapet ditt og (2) tuplen av ingredienser til en måltid. .. note:: **TIPPS** Strategien for å løse for #3 er lik strategien for #1, med bare små forskjeller. Eksempelkjøring: .. code-block:: python >>> to_buy(my_fridge, meals[3][1]) ['spaghetti'] Oppgave 3 ......... I gamle egyptiske tekster finner vi en multiplikasjonsmetode for vilkårlige positive heltall, som fungerer med bare addisjon og dobling. For å multiplisere for eksempel a = 19 og b = 23, begynner vi med å skrive 1 og doble det til det nye tallet ville vært større enn a: .. code-block:: text 1 2 4 8 16 Vi stopper på 16, siden 32 er større enn a = 19. Det finnes nå ett unikt utvalg av disse tallene hvor summen resulterer i a = 19. Det er 16 + 2 + 1. Vi markerer disse tallene med X. .. code-block:: text X 1 X 2 4 8 X 16 I den tredje kolonnen starter vi med tallet b = 23, og fortsetter å doble. .. code-block:: text X 1 23 X 2 46 4 92 8 184 X 16 368 Til slutt tar vi bare de tallene fra den siste kolonnen som er merket med X, og summerer dem: ``23 + 46 + 368 = 437``. Dette er vårt resultat: ``19 * 23`` er ``437``. I ``uke_08_oppg_3.py`` skriv et program som gjør følgende: 1. Spør brukeren om to positive heltall med input(). 2. Ved behov, bytt tallene slik at det første tallet er mindre enn det andre. 3. Regn ut innholdet til den egyptiske multiplikasjonstabellen etter fremgangsmåten som er vist ovenfor. 4. Skriv ut den ferdige multiplikasjonstabellen med pen formatering og justerte kolonner; slik at den ser ut som eksemplene vist nedenfor. For formateringen kan du anta at brukeren bare gir deg tall mellom 1 og 99. Programmet trenger å kjøre bare en gang hver gang det startes, du trenger ikke å be om nye input etter utskriften. Noen eksempler på programkjøring ser slik ut: .. code-block:: python Factor A: 10 Factor B: 13 ========================= 1 13 X 2 26 4 52 X 8 104 ========================= 2 + 8 = 10 26 + 104 = 130 ========================= 10 * 13 = 130 .. code-block:: python Factor A: 19 Factor B: 23 ========================= X 1 23 X 2 46 4 92 8 184 X 16 368 ========================= 1 + 2 + 16 = 19 23 + 46 + 368 = 437 ========================= 19 * 23 = 437 .. code-block:: python Factor A: 17 Factor B: 6 ========================= 1 17 X 2 34 X 4 68 ========================= 2 + 4 = 6 34 + 68 = 102 ========================= 17 * 6 = 102 Oppgave 4 ......... Hordaland har 15 distriktsmandater i Stortinget. Disse 15 mandatene skal fordeles mellom partiene i forhold til stemmetallet de fikk. Metoden er beskrevet slikt i valgloven §11-4 (3): Hver partiets stemmetall divideres med 1,4 - 3 - 5 - 7 osv. Hvert stemmetall skal divideres så mange ganger som det er nødvendig for å finne det antall mandater listen skal ha. Det første mandatet tilfaller den listen som har den største kvotienten. Det andre mandatet tilfaller den listen som har den nest største kvotienten osv. Et **eksempel** på en mandatsfordeling av 11 seter (fra regjeringen.no): .. image:: regjeringen.png :width: 500 :alt: Mandatsfordeling av 11 seter (fra regjeringen.no) I ``uke_08_oppg_4.py`` må du lage **2 funksjoner** som bygger på hverandre: (1) ``valgresultat(parties, votes, seats)``, (2) ``parti_mandater(party_list, votes, seats)`` Først lag en funksjon ``valgresultat(parties, votes, seats)`` som tar som argumenter (1) listen av partier, (2) listen med stemmer til hvert parti og (3) antallet mandater som skal fordeles. Funksjonen skal returnere en liste av ``seats`` tupler som viser kvotienten som ``float`` og partinavnet, f.eks: .. code-block:: python parties = ["H", "Ap", "FrP", "SP", "SV", "KrF", "R", "V", "MdG"] votes = [74282, 68945, 38352, 29981, 26901, 14724, 14150, 13163, 11940] N_seats = 15 .. code-block:: python print(valgesultat(parties, votes, N_seats)) [(53058.571428571435, 'H'), (49246.42857142857, 'Ap'), (27394.285714285717, 'FrP'), ... ] # 15 tuples Så lag en funksjon som heter ``parti_mandater(party_list, votes, seats)`` som igjen tar som argumenter listen av partier, listen av stemmer, og antallet mandater. Funksjonen skal gjenbruke ``valgresultat()`` internt og skal returnere en liste av tupler som viser partinavn og antallet stemmer og antallet mandater for hvert parti. Partier uten mandat skal ikke nevnes i tuplen. For eksempel, resultat i Hordaland gir følgende tuple: .. code-block:: python [('H', 74282, 4), ('Ap', 68945, 4), ('FrP', 38352, 2), ('SP', 29981, 2), ('SV', 26901, 1), ('KrF', 14724, 1), ('R', 14150, 1)] Oppgave 5 ......... *Oppgaven tilpasset fra* `2021 Advent of Code, Day 1: Sonar Sweep `_ I filen ``uke_08_oppg_5.py`` skal du lage **to** funksjoner: ``sonar_depth_increase_cnt()`` og ```sonar_depth_increase_cnt_avg()`` basert på følgende beskrivelser i del 1 og 2 av denne oppgaven. .. note:: Teksten gir alle ledetrådene du trenger for å løse denne oppgaven, så les nøye og så går det helt fint! Tenk deg at du er en del av et mannskap på en ubåt. Når ubåten faller under havoverflaten utfører den automatisk et sonarsveip av havbunnen i nærheten. På en liten skjerm vises ekkoloddsvei-prapporten (din puslespillinndata): hver linje er en måling av havbunnsdybden når sveipet ser lenger og lenger bort fra ubåten. Anta for eksempel at du hadde følgende rapport: .. code-block:: text "199 200 208 210 200 207 240 269 260 263" Denne rapporten indikerer at ved å skanne utover fra ubåten fant ekkoloddsveipet dybder på 199, 200, 208, 210, og så videre. 1. Den første oppgaven er å finne ut hvor raskt dybden øker, bare så du vet hva du har å gjøre med - du vet aldri om nøklene blir båret inn på dypere vann av en havstrøm eller en fisk eller noe. For å gjøre dette, tell antall ganger en dybdemåling øker fra forrige måling. (Det er ingen måling før den første målingen.) I eksemplet ovenfor er endringene som følger: .. code-block:: text 199 (N/A - no previous measurement) 200 (increased) 208 (increased) 210 (increased) 200 (decreased) 207 (increased) 240 (increased) 269 (increased) 260 (decreased) 263 (increased) I dette eksemplet er det **7** mål som er større enn den forrige målingen. I filen ``uke_08_oppg_5.py`` lag en funksjon som heter ``sonar_depth_increase_cnt()`` som tar som input dybde-verdiene i en string (se eksempel nedenfor) og returnerer hvor mange målinger er større enn den forrige målingen. Denne funksjonen skal fungere med andre strenger av dybdemålinger, likt som eksemplet vi ga. Eksempelkjøring: .. code-block:: python >>> sonar_depths_ticker = "199 200 208 210 200 207 240 269 260 263" >>> sonar_depth_increase_cnt(sonar_depths_ticker) 7 2. Å vurdere hver enkelt måling er ikke så nyttig som du forventet: det er bare for mye støy i dataen. Vurder i stedet summen av et skyvevindu med tre mål. Igjen med tanke på eksemplet ovenfor: .. code-block:: text 199 A 200 A B 208 A B C 210 B C D 200 E C D 207 E F D 240 E F G 269 F G H 260 G H 263 H Start med å sammenligne det første og andre tremålsvinduet. Målene i det første vinduet er merket med A (199, 200, 208); summen deres er 199 + 200 + 208 = 607. Det andre vinduet er merket med B (200, 208, 210); dens sum er 618. Summen av målinger i det andre vinduet er større enn summen av det første, så denne første sammenligningen økte. Målet ditt nå er å telle antall ganger summen av målinger i dette skyvevinduet øker fra forrige sum. Så sammenlign A med B, sammenlign deretter B med C, deretter C med D, og så videre. Stopp når det ikke er nok mål igjen til å lage en ny tremålssum. I eksemplet ovenfor er summen av hvert tre-målingsvindu som følger: .. code-block:: text A: 607 (N/A - no previous sum) B: 618 (increased) C: 618 (no change) D: 617 (decreased) E: 647 (increased) F: 716 (increased) G: 769 (increased) H: 792 (increased) I dette eksemplet er det **5** summer som er større enn forrige sum. I filen ``uke_08_oppg_5.py`` lag en funksjon som heter ``sonar_depth_increase_cnt_avg()`` som tar dybder-verdiene i en string som input (se eksempel nedenfor), vurder summen av et tre-måls skyvevindu og returner summer som er større enn forrige sum. Denne funksjonen skal fungere med andre strenger av dybdemålinger, likt som eksemplet vi ga. Eksempelkjøring: .. code-block:: python >>> sonar_depths_ticker = "199 200 208 210 200 207 240 269 260 263" >>> sonar_depth_increase_cnt_avg(sonar_depths_ticker) 5