Lab6

Forberedelser
Innlevering og automatisk retting
Oppgave 1

I denne oppgaven skal vi tegne vertikale striper ved hjelp av tre ulike hjelpefunksjoner. Ta utgangspunkt i denne koden:

from uib_inf100_graphics import *

def draw_stripes_from_left_edge(app, canvas, colors):
    ...

def draw_stripes_from_point(canvas, x, y, width, height, colors):
    ...

def draw_vertical_stripes_between(canvas, x1, y1, x2, y2, colors):
    ...

def redraw_all(app, canvas):
    draw_stripes_from_left_edge(app, canvas, ["green", "yellow", "#0cc"]*4)
    draw_stripes_from_point(canvas, 50, 50, 50, 100, ["#f00", "#f50", "#f80"])
    draw_vertical_stripes_between(canvas=canvas, x1=250, y1=10, x2=350, y2=80,
                                  colors=["red", "#a00", "#500", "black",])
    
run_app(width=400, height=200)

Foreløpig viser koden bare et tomt vindu, men etter at du har fylt inn de tre funksjonene, skal koden over tegne følgende bilde:

Illustrasjon av ferdig resultat

Del A: draw_stripes_from_left_edge

Funksjonen tar in en liste med farger og tegner like store vertikale striper av hver farge i listen. Hver stripe skal være 10 piksler bred, og den første stripen begynner lengst til venstre i lerretet.

Når funksjonen er implementert, skal programmet du kjører se slik ut:

Illustrasjon del A fullført

  • For å tegne rektangler, benytt metoden create_rectangle på canvas -objektet. Se kursnotater om grafikk 1 for eksempeler på bruk. De fire første argumenetene til metoden er x1, y1, x2, y2 som representerer kordinatene til to motstående hjørner i rektangelet.

Vi skal tegne like mange rektangler som det er farger i listen. Fordi vi vet hvor mange farger det er i listen allerede før løkken begynner (nemlig len(colors)), tilsier dette at vi skal benytte en for-løkke.

Vi skal tegne ett rektangel i hver iterasjon av løkken, og vi trenger å regne ut x og y -koordinater til to motstående hjørner for hvert rektangel.

  • y -koordinatene er enkle: det første y-koordinatet y1 er alltid 0, mens det andre y-kordinatet y2 er like stor som høyden på vinduet. Denne finner du som variabelen app.height
  • x-koordinatet avhenger av hvilken iterasjon vi befinner oss i
    • i iterasjon nummer 0 er x-verdiene x1=0  og x2=10
    • i iterasjon nummer 1 er x-verdiene x1=10 og x2=20
    • i iterasjon nummer 2 er x-verdiene x1=20 og x2=30
    • i iterasjon nummer 3 er x-verdiene x1=30 og x2=40
    • … og så videre

Ser du mønsteret? Dersom vi er i iterasjon nummer i, da skal x1=? og x2=?. Benytt en løkke med indeksering slik at du har iterasjonsnummeret i tilgjengelig for utregningen.

Del B: draw_stripes_from_point

Denne funksjonen minner om funksjonen fra del A, men tillater litt større fleksibilitet. Blant annet kan den som kaller funksjonen spesifisere høyden på stripene, bredden på stripene, samt punktet til venstre øverst hvor stripene begynner.

Parameterene til denne funksjonen er

Når du er ferdig med denne funksjonene, skal programmet ditt tegne følgende:

Illustrasjon del B fullført

Ta utgangspunkt i koden fra forrige deloppgave, men endre følgene:

  • For verdien av y1 når du kaller create_rectangle, bruk verdien fra parameteren y du har som input i stedet for 0.

  • For verdien av y2 når du kaller create_rectangle, bruk summen av y og høyde-parameteren du har som input.

  • I stedet for å bruke bredden 10, benytter vi bredde-parameteren width alle steder vi tidligere multipliserte med 10.

  • Alle x-koordinater må forskyves med x – dette betyr at vi må legge x -parameteren til alle x-verdier vi ellers regner ut.

Del C: draw_vertical_stripes_between

Denne funksjonen gir samme funksjonalitet som funksjonen i del B, men gir den som kaller metoden litt mer praktiske parametre å forholde seg til. Parametrene til denne funksjonen er:

Alle rektanglene skal være like brede. Du kan gjenbruke (kalle på) funksjonen fra del B om du ønsker.

Når du er ferdig, skal koden din tegne figuren vist øverst i denne oppgaven.

Det er mulig å gjenbruke koden fra forrige deloppgave (gjøre et kall til draw_stripes_from_point) for å løse denne deloppgaven.

  • For parametrene x, y og colors i draw_stripes_from_point kan vi enkelt og greit bruke x1 og x2 og colors som argumenter. Det gjenstår å regne ut høyde og bredde.

  • For å regne ut høyden, kan vi gjøre et enkelt regnestykke på y-verdiene våre. Hvilket?

  • For å regne ut bredden til en stripe, kan vi først regne ut den totale bredden vi skal dekke, og deretter dele den totale bredden på antall striper.

Test deg selv

Koden din skal være fleksibel, og må fungere også med andre input enn akkurat dem vi har gitt. Kopier og lim inn den alternative redraw_all -funksjonen under (uten å endre på dine egne funksjoner) og sjekk at du nå tegner bildet vist under

def redraw_all(app, canvas):
    draw_stripes_from_left_edge(app, canvas, ["blue","navy"]*5)
    draw_stripes_from_point(canvas, 30, 90, 50, 100, 
                            ["#0f0", "#0fc", "#0ff", "#0cf"])
    draw_vertical_stripes_between(canvas=canvas, x1=160, y1=10, x2=350, y2=80,
                                  colors=["black", "red", "yellow"])

    margin = 2
    width = 30 + margin
    height = 20 + margin
    x_left = 270
    y_top = 100
    for row in range(3):
        for col in range(4):
            draw_vertical_stripes_between(canvas=canvas,
                x1=(x_left + width*row),
                y1=(y_top + height*col),
                x2=(x_left + width*(row+1) - margin),
                y2=(y_top + height*(col+1) - margin),
                colors=["#0f0", "#0a0", "#050", "black",])

Illustrasjon av alternativ redraw_all

Oppgave 2

I filen uke_06_oppg_2.py skriv funksjonen alternate_sign_sum() som tar inn en liste a med tall og regner ut a[0] - a[1] + a[2] - a[3] … a[n-1]

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")

  • Vi trenger å bruke en løkke for å gå igjennom alle elementene i listen. Siden vi vet allerede før løkken begynner hvor mange iterarsjoner vi skal ha (nemlig len(a)), bør vi bruke en for-løkke

  • Før løkken starter, opprett en variabel som holder den løpende totalsummen. For hver iterasjon av løkken legger vi til (eller trekker fra) et tall til denne variabelen.

  • Inne i løkken må vi avgjøre om vi skal legge til eller trekke fra i den iterasjonen som nå skal utføres. Hvis vi benytter en indeksert løkke, kan vi sjekke om indeks er et partall eller oddetall, og slik velge om vi legger til eller trekker fra.

  • Returner totalsummen når løkken er ferdig.

Oppgave 3

Medianen i en samling med tall er et gjennomsnitt av

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_06_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.)

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")

  • Det finnes mange måter å løse dette problemet på. Det enkleste er å velge det midterste (eller to midterste) elementet i en sortert liste; men pass på at du ikke muterer listen. Du kan unngå dette ved å sortere ikke-destruktivt eller bryte aliaset ved å lage en kopi før du sorterer.

Oppgave 4

I filen uke_06_oppg_4.py skriv funksjonen smallest_absolute_difference(a) som tar inn en liste a med tall og returnerer den minste absolutt-verdi som er forskjellen mellom to tall i listen.

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

Alternativ A (kanskje enklest å komme på, men litt ineffektivt):

  • Før løkkene starter, opprett en variabel som har til hensikt å hold på den minste forskjellen mellom to elementer sammenlignet så langt. Initielt kan den for eksempel ha absolutt-verdien av avstanden mellom de to første elementene i listen
  • Benytt en indeksert for-løkke for å gå igjennom alle elementene i listen. I iterasjon nummer i av løkken er hensikten å finne den minste absolutt-verdi-forskjellen mellom elementet a[i] og et element som kommer senere i listen (vi trenger kun å sjekke det som kommer senere i listen – fordi hvis den minste forskjellen var mot et element tidligere i listen, vil denne forskjellen allerede være funnet da vi sjekket det elementet).
  • Benytt en nøstet for-løkke for å gå gjennom alle posisjoner j mellom i+1 og len(a); regn ut absolutt-verdien av forskjellen på a[i] og a[j], og dersom den er mindre enn noe vi har sett før, lagre denne avstanden i variabelen som har til hensikt å huske dette.
  • Når alle iterasjonene er ferdig, returner svaret

Alternativ B (mer effektivt):

  • Ikke-destruktivt sorter listen

  • Gå gjennom listen med en indeksert løkke, og regn ut forskjellen på alle etterfølgende elementer. Ta vare på den minste slike avstanden.

Oppgave 5

I denne oppgaven skal vi skrive et hjelpemiddel for deg som ønsker å bli bedre i ordspill som Scrabble og Wordfeud. Det er selvfølgelig ikke lov å bruke dette for å jukse når man spiller, men det er lov å bruke det for å evaluere spill i etterkant.

I spill som Scrabble og Wordfeud har hver spiller en bunke med brikker, som hver har én bokstav på seg. Poenget er å kombinere brikkene slik at de former et lovlig ord. For å avgjøre hva som er et lovlig ord, bruker vi ordlisten nsf2022.txt som er den offisielle ordlisten fra Norsk Scrabbleforbund fra og med august 2022.

I denne oppgaven skal vi skrive et program i filen uke_06_oppg_5.py som foreslår hvilke ord vi kan legge, gitt hvilke bokstaver vi har for hånden.

Del A

Skriv en funksjon can_be_made_of_letters(word, letters) som tar inn en streng word og en streng letters og returerer True hvis strengen word kan lages med bokstavesamlingen letters, og False hvis ikke.

print("Tester can_be_made_of_letters... ", end="")
assert(can_be_made_of_letters("emoji", "abcdefghijklmno"))
assert(not can_be_made_of_letters("smilefjes", "abcdefghijklmnopqrs"))
assert(can_be_made_of_letters("smilefjes", "abcdeeefghijklmnopqrsss"))
assert(can_be_made_of_letters("lese", "esel"))

# Ekstra tester for mer avansert variant, med wildcard * i bokstavene
# assert(can_be_made_of_letters("lese", "ese*"))
# assert(not can_be_made_of_letters("lese", "esxz*"))
# assert(can_be_made_of_letters("smilefjes", "s*i*e*j*s"))
# assert(not can_be_made_of_letters("smilefjes", "s*i*e*j*z"))
print("OK")

Sjekk for hver bokstav i ordet som skal lages om antall forekomster av bokstaven i bokstavsamlingen er tilstrekkelig i forhold til antall forekomster av bokstaven i ordet. Strenger har en metode .count som kan brukes til dette.

Del B

Skriv en funksjon possible_words(wordlist, letters) som tar inn en liste med strenger wordlist og en streng letters og retunerer en liste med alle ord fra wordlist som kan lages med bokstavene i letters.

print("Tester possible_words... ", end="")
hundsk =["tur", "mat", "kos", "hent", "sitt", "dekk", "voff"]
kattsk =["kos", "mat", "pus", "mus", "purr", "mjau", "hiss"]

assert(['kos', 'sitt'] == possible_words(hundsk, "fikmopsttuv"))
assert(['kos', 'pus', 'mus'] == possible_words(kattsk, "fikmopsttuv"))

# Ekstra tester for mer avansert variant, med wildcard * i bokstavene
# assert(['tur', 'mat', 'kos', 'sitt'] == possible_words(hundsk, "fikmopsttu*"))
# assert(['kos', 'mat', 'pus', 'mus'] == possible_words(kattsk, "fikmopsttu*"))
print("OK")

Del C

Skriv en funksjon possible_words_from_file(path, letters) som tar inn en filsti path til en fil som inneholder en ordliste med ett lovlig ord på hver linje, samt en bokstavsamling letters. La funksjonen returnere en liste med alle ord man kan lage av de gitte bokstavene.

For å teste funksjonen kan du laste ned filen nsf2022.txt legge den i samme mappe som uke_06_oppg_5.py kjøres fra.

Husk at hvilken mappe du kjører fra ikke alltid er den samme mappen hvor programmet ligger; men dersom du åpner VSCode i samme mappe som skriptet ditt, vil dette også være den mappen du kjører programmet fra.

print("Tester possible_words_from_file... ", end="")
assert(['du', 'dun', 'hu', 'hud', 'hun', 'hund', 'nu', 'uh']
        == possible_words_from_file("nsf2022.txt", "hund"))

# Ekstra test for varianten hvor det er wildcard i bokstavene
# assert(['a', 'cd', 'cv', 'e', 'i', 'pc', 'wc', 'æ', 'å']
#         == possible_words_from_file("nsf2022.txt", "c*"))
print("OK")
Oppgave 6

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_06_oppg_6.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_06_oppg_6.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")
Oppgave 7

For veldig lenge siden i en galakse langt, langt borte var det en gang en emneansvarlig som skulle avgjøre hvem som skulle få ta eksamen. Data om studentene var samlet i en semikolon-separert csv-fil du kan laste ned her: course_data.csv. I denne filen står B for bestått, mens alle andre verdier betyr ikke bestått.

Reglene for å få ta eksamen var som følger:

Emneansvarlig ønsker å skrive en funksjon som leser csv-filen og returnerer en liste med id til dem som fikk bestått. Kunne du hjulpet ham?

I filen uke_06_oppg_7.py skriv en funksjon students_who_passed(path) som leser csv-filen over og returnerer en liste med id’er for de studentene som har bestått arbeidskravene i kurset.

print("Tester students_who_passed... ", end="")
assert(['abc101', 'abc103', 'abc105', 'abc109', 'abc111', 'abc113'] 
        == students_who_passed("course_data.csv"))
print("OK")