Uke 7

Innlevering, Krav for å bestå og viktigheten av bonusoppgaver

• Du kan levere så mange ganger du vil. Siste innlevering telles.
• For å få bestått, må du få 100% riktig av CodeGrade på alle oppgaver som ikke er merket som bonus.
• Oppgavene som er merket som bonus er frivillige. Imidlertid er det verdt å bruke tid på disse oppgavene da de kan gi deg verdifull erfaring med å løse liknende problemer som kan dukke opp på eksamen.

Generelt tips: les alltid gjennom kursnotatene før du begynner på lab’en!

Oppgave 1

I filen uke_07_oppg_1.py skriv funksjonen random_series() som tar inn en liste a med tall og regner ut \(\frac{a[0]}{1} + \frac{a[1]}{2} + \frac{a[2]}{3} + \frac{a[3]}{4} + … + \frac{a[n-1]}{n}\). Der n er lengden av listen.

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

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

Oppgave 2

I filen uke_07_oppg_2.py, skriv en funsjon som heter sum_of_column(a, col) som tar inn en 2-d liste a og en kolonneindeks col og returnerer summen av verdiene fra den oppgitte kolonnen i 2-d listen.

Eksempelkjøringer:

print("Tester sum_of_column... ", end="")
a = [[1,  2,  3],
     [4,  5,  6]]
assert(5 == sum_of_column(a, 0))
assert(7 == sum_of_column(a, 1))
assert(9 == sum_of_column(a, 2))
print("OK")

Oppgave 3

Medianen i en samling med tall er et gjennomsnitt av

• det største tallet hvor minst halvparten av tallene er større enn eller lik dette, og
• det minste tallet hvor minst halvparten av tallene er mindre enn eller lik dette.

Man kan finne medianen ved å sortere samlingen med tall og velge det midterste tallet i rekken; eventuelt gjennomsnittet av de to midterste tallene dersom samlingen består av et jevnt antall tall.

I filen uke_07_oppg_3.py skriv funksjonen median(a) som tar inn en liste a med tall og regner ut medianen. (Merk at det finnes biblioteker man kan importere som har en funksjon som gjør akkurat dette – men de kan du selvfølgelig ikke bruke i denne oppgaven, det ville vært litt juks. Andre funksjoner som sort og len er greit.)

print("Tester median... ", end="")
assert(3 == median([1, 2, 3, 6, 7]))
assert(3.5 == median([1, 2, 3, 4, 6, 9]))
a = [-10, 100, 8, 7, 2]
assert(7 == median(a))
assert([-10, 100, 8, 7, 2] == a) # Sjekker at funksjonen ikke er destruktiv
print("OK")

Oppgave 4

I filen uke_07_oppg_4.py skriv funksjonen smallest_absolute_difference(a,b) som tar inn to lister a og b med tall og returnerer den minste absolutt-verdi som er forskjellen mellom et tall i a og et tall i b. Funksjonen skal være ikke-destruktiv.

print("Tester smallest_absolute_difference... ", end="")
a = [1, 20, 4, 19, -5, 99]
b = [67, 9, 40]
assert(5 == smallest_absolute_difference(a,b)) # |4-9| =5
c = [67, 19, 40, -5, 1]
d= [2, 1, 4, 1, 5, 6]
assert(0 == smallest_absolute_difference(c, d)) # |1-1| =0
e = [50, 40, 70, 33]
assert(27 == smallest_absolute_difference(d,e)) # |6 - 33| =27
assert([50, 40, 70, 33] == e) # Sjekker at funksjonen ikke er destruktiv
print("OK")

Oppgave 5

En fil består av en sekvens av 1’ere og 0’ere. Noen filformater har i praksis veldig lange sekvenser med kun 1’ere eller kun 0’ere. For eksempel: en sensor i et alarmsystem gir 1 som output når en dør er åpen, og 0 som output når en dør er lukket; sensoren blir avlest 1 gang i sekundet, og disse data’ene blir lagret som en sekvens av 0’ere og 1’ere i en fil. Et annet eksempel på slike filer er bilder med store hvite eller svarte felter.

For å komprimere slike filer, kan vi omgjøre måten vi skriver filen på til å bestå av en sekvens heltall som forteller vekselvis hvor mange 0’ere og 1’ere som kommer etter hverandre. Det første tallet i komprimeringen forteller hvor mange 0’er det er i begynnelsen. Dette tallet kan være 0 dersom binærtallet begynner med 1. Alle andre tall i komprimeringen vil være positive. Du kan lese mer om denne typen komprimering på wikipedia.

For enkelhets skyld gjør vi denne oppgaven med strenger og ikke direkte med 1’ere og 0’ere lagret i minnet.

Del A

I filen uke_07_oppg_5.py skriv en funksjon compress(raw_binary) som tar inn en streng raw_binary bestående av 0’ere og 1’ere og retunerer en streng som representerer sekvensen i komprimert form (tall skilles med mellomrom).

print("Tester compress... ", end="")
assert("2 3 4 4" == compress("0011100001111"))
assert("0 2 1 8 1" == compress("110111111110"))
assert("4" == compress("0000"))
print("OK")

Del B

I filen uke_07_oppg_5.py skriv en funksjon decompress(compressed_binary) som tar inn en streng compressed_binary beståenden av mellomrom-separerte heltall som representerer en komprimert sekvens av 0’ere og 1’ere. La funksjonen returnere den ukomprimerte sekvensen av 0’ere og 1’ere.

print("Tester decompress... ", end="")
assert("0011100001111" == decompress("2 3 4 4"))
assert("110111111110" == decompress("0 2 1 8 1"))
assert("0000" == decompress("4"))
print("OK")

Bonus

Skriv funksjonen find_words_in_character_grid(char_grid, words) som tar inn en 2D-liste med bokstaver char_grid og en ordliste words. Funksjonene skal søke i 2D-listen både fra venstre mot høyre og fra toppen og ned, og returnere en liste over alle ord fra ordlisten som finnes i char_grid.

print("Tester find_words_in_character_grid... ", end="")

glossary = ["dikt", "hus", "lese", "by", "elev",
            "smart", "helt", "mål", "yr", "lære"]
char_grid= [
        ['d','s','h','s','s','y'],
        ['l','æ','r','e','s','å'],
        ['k','a','l','a','m','e'],
        ['t','h','e','r','a','q'],
        ['e','t','s','t','r','z'],
        ['e','t','e','r','t','p'],
        ['e','m','å','l','v','w'],
    ]
found_words = find_words_in_character_grid(char_grid, glossary)
assert(sorted(['lese', 'smart', 'mål', 'lære']) == sorted(found_words))
print("OK")