Lab4

Pythonesia

Om du ikke allerede kan indeksering av 2d-lister veldig godt, anbefaler vi at du benytter fremgangsmåten og pseudokoden under for å se hvordan du kan iterere over en 2d-liste.

Du er med i en ekspedisjon til Pythonesia, et land som er kjent for sine mange rutenett av tall. Noe du har lest i reisehåndboken er at det er en gammel legende om at det finnes skatter gjemt under et av rutenettene i Pythonesia. Det er nemlig gjemt en skatt under alle ruter hvor radnummeret, kolonnenummeret og verdien i ruten (rad, kolonne) summerer til et spesielt tall. Du tenker du kan bruke dine programmeringsferdigheter til å finne posisjonene til disse skattene.

I en fil find_treasure.py, lag en funksjon find_treasure som tar inn en 2D-liste grid og et tall target_sum. Funksjonen skal returnere en liste av koordinater [row,col] i rutenettet hvor summen av rad, kolonne og verdi er lik target_sum. Hvis det ikke finnes noen slike skatter, skal funksjonen returnere en tom liste.

For eksempel, hvis du har følgende rutenett:

[ 
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

og target_sum er 5, så skal funksjonen returnere [[0, 2], [1, 0]] siden på rad 0, kolonne 2, så er summen 0 + 2 + 3 = 5, og på rad 1, kolonne 0, så er summen 1 + 0 + 4 = 5. Se bilder under for visualisering:

def find_treasure(grid, target_sum):
    ... # Din kode her

    # opprett en tom liste `treasures` som skal inneholde koordinatene til skattene.
    # definer en variabel `rows` som er antall rader i rutenettet
    # definer en variabel `cols` som er antall kolonner i rutenettet

    # lag en ytre løkke `for row in range(rows)`
        # lag en indre løkke `for col in range(cols)`
            # hent ut verdi til denne posisjonen
            # sjekk om summen av radnummer, kolonnenummer og verdi er lik `target_sum`
                # hvis det er tilfellet, legg koordinatene ``[row, col]`` til `treasures`
    
    # returner `treasures`

Her er kode du kan sette inn på slutten av find_treasure.py for å teste funksjonen din:

print("Testing find_treasure... ", end="")
# Test 1
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
target_value = 5
actual = find_treasure(grid, target_value)
expected = [[0, 2], [1, 0]]
assert expected == actual

# Test 2
actual = find_treasure([[1, 2], [3, 4]], 3)
expected = [[0, 1]]
assert expected == actual

# Test 3
actual = find_treasure([[1, 2], [3, 4]], 1)
expected = [[0, 0]]
assert expected == actual

# Test 4
actual = find_treasure([[1, 2], [3, 4]], 1000)
expected = []
assert expected == actual

print("OK")

Trylledrikker

Trollmannen Gallius har en liste over trylledrikker som han har brygget. Gallius har en liste over nivåer som beskriver hvor kraftige disse trylledrikkene er. Men Gallius har brygget så mange trylledrikker at han har mistet helt oversikten over hvor kraftige de forskjellige trylledrikkene er. Han trenger din hjelp til å normalisere nivåene slik at de ligger mellom 0 og 1.

For å normalisere nivåene til Gallius, må du finne den minste og største verdien i listen over nivåer (fremover referert til som henholdsvis low og high). Deretter må du gå gjennom listen og regne ut en ny verdi for hvert nivå. Den nye verdien skal være lik:

$$\frac{{level - low}}{{high - low}} $$

Det er disse nye verdiene som skal være resultatet av normaliseringen.

Som et eksempel, hvis Gallius har følgende liste over nivåer:

[1, 2, 3, 4, 5]

Da er minste verdi 1 og største verdi 5. For eksempel vil nivået 3 normaliseres til:

$$ \frac{{3 - 1}}{{5 - 1}} = \frac{2}{4} = 0.5 $$

Dette gir mening siden 3 er halvveis mellom 1 og 5 (som er minste og største verdi).

Som oppsummering:

I en fil normalize_potions.py, lag en ikke-destruktiv funksjon normalize_potions som tar inn en liste av nivåer levels og returnerer en ny liste med normaliserte nivåer. Hvis alle nivåene er like, skal funksjonen returnere en liste med samme lengde som levels hvor alle verdiene er 1. Hvis du ikke håndterer dette tilfellet, vil du få en ZeroDivisionError når du prøver å dele med high - low i formelen for normaliseringen. Du kan anta at levels alltid vil inneholde minst ett element.

Du kan kopiere følgende kode inn i normalize_potions.py for å teste funksjonen din:

print("Tester normalize_potions... ", end="")
# Første test
levels = [4, 3, 2, 1, 0]
expected = [1.0, 0.75, 0.5, 0.25, 0.0]
actual = normalize_potions(levels)
assert [4, 3, 2, 1, 0] == levels, "Funksjonen skal ikke mutere listen. Hvis du har brukt .sort() er listen mutert. Du kan bruke min og max for å finne minste og største verdi i listen uten mutasjon."
assert expected == actual, f"Forventet {expected} men fikk {actual}"

# Flere tester
assert [0.0, 0.25, 0.5, 0.75, 1.0] == normalize_potions([0.01,0.02,0.03,0.04,0.05])
assert [0.0, 0.25, 0.5, 0.75, 1.0] == normalize_potions([2, 3, 4, 5, 6])
assert [1.0, 1.0, 1.0, 1.0, 1.0] == normalize_potions([3, 3, 3, 3, 3])
assert [0.0, 0.3, 0.2, 0.9, 1.0] == normalize_potions([-1, 2, 1, 8, 9])
assert [1.0, 0.75, 0.5, 0.0] == normalize_potions([5, 4, 3, 1])
print("OK")

Integraler

Denne oppgaven består av fire deler. Skriv alle funksjoner til de fire delene (A-D) i én felles fil, integrals.py.

Del A

I matematikken kan en funksjon for eksempel være definert som \(g(x) = \frac{1}{8}x^2 - 2x + 10\). La oss modellere denne matematiske funksjonen som en programmeringsfunksjon:

• I filen integrals.py, opprett en funksjon g som har en parameter x og som regner ut verdien av \(\frac{1}{8}x^2 - 2x + 10\) for den gitte verdien av x.

For eksempel skal et kall til g(8.0) returnere verdien 2.0, og et kall til g(4.0) skal returnere verdien 4.0.

Test koden din:

def almost_equals(a, b):
    return abs(a - b) < 0.0000001

print("Tester g... ", end="")
# Første test
x = 8.0
actual = g(x)
expected = 2.0
assert almost_equals(expected, actual)

# Flere tester
assert almost_equals(4.0, g(4.0))
assert almost_equals(10.0, g(0.0))
print("OK")

Del B

I denne oppgaven skal vi regne ut en tilnærming for arealet under funksjonen \(g\) (fra del A) mellom to gitte punkter \(x_\text{lo}\) og \(x_\text{hi}\) på x-aksen. Vi antar at \(x_\text{lo} \leq x_\text{hi}\), og i denne omgang antar vi også at \(x_\text{lo}\) og \(x_\text{hi}\) er heltall.

For å gjøre vår tilnærming, skal vi enkelt nok regne ut summen av g(x_i) for alle heltalls-verdier \(x_i\) fra og med \(x_\text{lo}\) opp til (og ikke inkludert) \(x_\text{hi}\). For eksempel, dersom \(x_\text{lo} = 3\) og \(x_\text{hi} = 7\), er vi interessert i å vite hva summen \(g(3) + g(4) + g(5) + g(6)\) blir.

• I filen integrals.py, opprett en funksjon approx_area_under_g med parametre x_lo og x_hi som returnerer summen av g(x_i) for alle heltall x_i fra og med x_lo opp til x_hi.

Test kode din:

print("Tester approx_area_under_g... ", end="")
# Første test
x_lo = 4
x_hi = 5
actual = approx_area_under_g(x_lo, x_hi) 
expected = 4.0  # skal gi oss kun g(4), som altså er 4.0
assert almost_equals(expected, actual)

# Flere tester
assert almost_equals(3.125, approx_area_under_g(5, 6)) # g(5)
assert almost_equals(7.125, approx_area_under_g(4, 6)) # g(4)+g(5)
assert almost_equals(23.75, approx_area_under_g(1, 5)) # g(1)+g(2)+g(3)+g(4)
print("OK")

Del C

Estimatet for arealet vi regnet ut i forrige deloppgave er bare et estimat, siden vi later som funksjonen går i «trapper» i stedet for å være kontinuerlig, slik den egentlig er. For å gjøre estimatet vårt bedre, kan vi redusere bredden på hvert trappetrinn. Jo smalere trappetrinn vi velger, jo bedre blir estimatet vårt for arealet.

På figuren under vises det ulike bredder på trappetrinnene. Jo flere trappetrinn, jo mer nøyaktig vil arealet av det grønne området (som vi regner ut) stemme med det faktiske arealet under grafen (den røde streken).

Illustrasjon av 09glasgow09, CC BY-SA 3.0.

I denne oppgaven skal vi forbedre estimatet for arealet under grafen ved å la dem som kaller funksjonen vår bestemme hvor mange trappetrinn de ønsker å benytte. Dette kalles en (venstresidet) Riemann sum.¹

• I filen integrals.py, opprett en funksjon riemann_sum_g med parametre x_lo, x_hi og n. Funksjonen skal returnere en tilnærming av arealet under grafen g fra oppgave A basert på n antall trappetrinn.

• På samme måte som i del B skal vi oppdatere en løpende total i en løkke.

• På samme måte som i oppgaven «Oppdelt linjestykke» fra lab 3, skal vi dele opp linjestykket \([x_\text{lo}, x_\text{hi}]\) i \(n\) like store biter.

Merk: i denne oppgaven vet du allerede før løkken starter hvor mange iterasjoner løkken skal ha (nemlig n). Derfor bør du velge en for-løkke, og ikke en while-løkke. I denne oppgaven kan faktisk det å velge en while-løkke, i kombinasjon med avrundingsfeil som alltid vil skje når vi jobber med flyttall, gjøre at du får feil svar!

Test koden din:

print("Tester riemann_sum_g... ", end="")
assert almost_equals(7.125, riemann_sum_g(4, 6, 2))
assert almost_equals(6.71875, riemann_sum_g(4, 6, 4))
assert almost_equals(6.3348335, riemann_sum_g(4, 6, 1000))

assert almost_equals(23.75, riemann_sum_g(1, 5, 4))
assert almost_equals(22.4375, riemann_sum_g(1, 5, 8))
assert almost_equals(21.166676666, riemann_sum_g(1, 5, 1_000_000))
print("OK")

Del D

Vi ønsker nå å regne ut arealet under flere grafer. Når alt kommer til alt er funksjonen \(g(x) = \frac{1}{8}x^2 - 2x + 10\) relativt obskur.

Opprett en funksjon riemann_sum med parametre f, x_lo, x_hi og n. Funksjonen skal returnere en tilnærming av arealet under grafen f mellom x_lo og x_hi basert på n antall trappetrinn. Koden vil være helt identisk med forrige deloppgave, bortsett fra at du kaller f(x_i) istedet for g(x_i) inne i løkken.

For å teste funksjonen, legg denne koden nederst i filen:

# Vi sjekker først at riemann_sum med funksjonen g som argument gir
# samme svar som riemann_sum_g -metoden fra forrige deloppgave.
print("Tester riemann_sum med funksjonen g... ", end="")
assert almost_equals(7.125, riemann_sum(g, 4, 6, 2))
assert almost_equals(6.71875, riemann_sum(g, 4, 6, 4))
assert almost_equals(6.3348335, riemann_sum(g, 4, 6, 1000))

assert almost_equals(23.75, riemann_sum(g, 1, 5, 4))
assert almost_equals(22.4375, riemann_sum(g, 1, 5, 8))
assert almost_equals(21.166676666, riemann_sum(g, 1, 5, 1_000_000))
print("OK")

# Så tester vi med et par andre funksjoner
# Funksjonen som kvadrerer, square(x) = x**2
def square(x):
    return x**2

## Arealet under grafen square(x) = x**2 mellom 1 og 3
## Eksakt svar  er 8 + 2/3, altså 8.66666666....
## Merk at vi kommer gradvis nærmere eksakt svar ved å øke n
print("Tester riemann_sum med funksjonen square... ", end="")
assert almost_equals(5.0, riemann_sum(square, 1, 3, 2))
assert almost_equals(7.88, riemann_sum(square, 1, 3, 10))
assert almost_equals(8.5868, riemann_sum(square, 1, 3, 100))
print("OK")

# Funksjonen som er en jevnt stigende, linear(x) = x
def linear(x):
    return x

## Arealet under grafen for funksjonen f(x) = x mellom 2 og 4
## Eksakt svar er 6.
## Merk at vi kommer gradvis nærmere riktig svar ved å øke n
print("Tester riemann_sum med funksjonen linear... ", end="")
assert almost_equals(5.0, riemann_sum(linear, 2, 4, 2))
assert almost_equals(5.5, riemann_sum(linear, 2, 4, 4))
assert almost_equals(5.998046875, riemann_sum(linear, 2, 4, 1024))
print("OK")

Alternerende sum

I filen alternating_sum.py opprett funksjonen alternate_sign_sum som tar inn en liste med tall summands som parameter. Funksjonen skal regne ut den alternerende summen av tallenen i listen summands (summands[0] - summands[1] + summands[2] - summands[3] … summands[n-1]).

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester alternate_sign_sum... ", end="")
assert(3 == alternate_sign_sum([1, 2, 3, 4, 5]))
assert(30 == alternate_sign_sum([10, 20, 30, 40, 50]))

a = [-10, 20, -30, 40, -50]
assert(-150 == alternate_sign_sum([-10, 20, -30, 40, -50]))
assert([-10, 20, -30, 40, -50] == a) # Sjekker at funksjonen ikke er destruktiv
print("OK")