Lab5

Dette er del 1 av laben. Del 2 av laben finner du på her (på mitt.uib). Merk at del 2 av laben har frist allerede etter én uke, mens del 1 har frist etter to uker.

Nivå E:

Nivå A-D:

Nivå E
Operasjoner på mengder

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

I denne oppgaven skal du skrive funksjoner for å utføre operasjoner på mengeder. Vi vil betrakte en mengde som en liste der hver element i listen forekommer kun én gang.

Python har en spesiell type for mengder som vi skal lære om senere i emnet. Den skal du ikke bruke i denne oppgaven. Du skal bare bruke lister.

Del A

Opprett en funksjon no_duplicates(a) som tar inn en liste a som parameter. Funksjonen skal returnere en liste der hvert element i listen a forekommer kun én gang. Rekkefølgen på elementene i den nye listen skal være den samme som i den opprinnelige listen.

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

print("Tester no_duplicates... ", end="")
assert([1] == no_duplicates([1, 1]))
assert([1, 3, 5, 4, 8] == no_duplicates([1, 1, 3, 5, 4, 3, 8]))
assert([1, 3, 5, 4, 8] == no_duplicates([1, 3, 5, 4, 8]))
print("OK")

Del B

Opprett en funksjon set_difference(setA, setB) som tar inn to lister setA og setB som parametre. Funksjonen skal returnere mengden av elementer i setA som ikke tilhører setB.

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

print("Tester set_difference... ", end="")
assert sorted([1, 5, 8]) == sorted(set_difference([1, 3, 5, 4, 8], [2, 3, 4, 7, 6])) 
assert sorted([2 , 7, 6]) == sorted(set_difference([2, 3, 4, 7, 6], [1, 3, 5, 4, 8])) 
print("OK")

Del C

Opprett en funksjon set_union(setA, setB) som tar inn to lister setA and setB som parametre. Funksjonen skal returnere en liste som inneholder alle elementene som forekommer i en eller begge listene setA od setB.

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

print("Tester set_union... ", end="")
assert sorted([1, 3, 5, 4, 8, 2, 7, 6]) == sorted(set_union([1, 3, 5, 4, 8], [2, 3, 4, 7, 6]))
assert sorted([2, 7, 6]) == sorted(set_union([2, 7, 6], [2, 6]))
print("OK")

Del D

Opprett en funksjon set_intersection(setA, setB) som tar inn to lister setA and setB som parametre. Funksjonen skal returnere en liste som inneholder alle elementene som forekommer både i setA og i setB.

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

print("Tester set_intersection... ", end="")
assert sorted([3 , 4]) == sorted(set_intersection([1, 3, 5, 4, 8] , [2, 3, 4, 7, 6]))
assert sorted([3]) == sorted(set_intersection([3, 4], [2, 3, 5]))
assert sorted([]) == sorted(set_intersection([3, 4], [5, 6]))
print("OK")
Nivå E
Flerfarget flagg

I filen multicolored_flag.py opprett en funksjon draw_multicolored_flagsom tar inn seks parametere: canvas, x1, y1, x2, y2, colors. Parameteren colors skal være en liste med strenger som representerer farger. Funksjonen skal tegne et flagg med vertikale striper på canvas med øvre venstre hjørne i punktet \((x_1, y_1)\) og nedre høyre hjørne i punktet \((x_2, y_2)\). Flagget skal ha like mange striper som det er farger i listen colors og hver oppføring i liste skal reflektere fargen på hver tilsvarende stripe. Første stripe skal altså ha farge colors[0], andre stripe skal ha farge colors[1], osv. Funksjonen trenger ikke å ha noen returverdi.

Merk: I filen multicolored_flag.py skal du ikke importere noe, og du skal heller ikke kalle på display-funksjonen. For å teste koden, opprett i stedet en separat fil multicolored_flag_test.py i samme mappe som multicolored_flag.py og kopier inn koden under. Når du kjører multicolored_flag_test.py, skal det tegnes tre flagg på skjermen som vist under:

from uib_inf100_graphics.simple import canvas, display
from multicolored_flag import draw_multicolored_flag

draw_multicolored_flag(canvas, 125, 135, 275, 265, ["red", "orange", "yellow", "green", "blue", "purple"])
draw_multicolored_flag(canvas, 10, 10, 40, 36, ["black", "yellow", "red"])
draw_multicolored_flag(canvas, 10, 340, 390, 360, ["black", "white", "black","black", "white", "black","black", "white", "black"])

display(canvas)
Eksempelkjøring 1

PS: Når du kaller på canvas.create_rectangle, legg til outline="" i argumentlisten. Da unngår du at det tegnes en svart ramme rundt rektangelet.

Nivå E
Farget rutenett

I filen colored_grid.py opprett en funksjon draw_grid som tar in følgende parametre: canvas, x1, y1, x2, y2, color_grid. Parameteren color_grid er en 2D-liste med strenger som representerer farger. Funksjonen skal tegne et rutenett med farger med øvre venstre hjørne i punktet \((x_1, y_1)\) og nedre høyre hjørne i punktet \((x_2, y_2)\). Fargene i listen color_grid skal reflektere fargen på rutene i tilsvarende posisjon (se eksempelkjøringen). Funksjonen trenger ikke å ha noen returverdi.

Merk: I filen colored_grid.py skal du ikke importere noe, og du skal heller ikke kalle på display-funksjonen. For å teste koden, opprett i stedet en separat fil colored_grid_test.py i samme mappe som colored_grid.py og kopier inn koden under. Når du kjører colored_grid_test.py, skal det tegnes tre rutenett på skjermen som vist under:

from uib_inf100_graphics.simple import canvas, display
from colored_grid import draw_grid

# Et 4x2 rutenett med farger
draw_grid(canvas, 40, 100, 120, 180, [
        ["red", "darkred"],
        ["yellow", "orange"],
        ["white", ""],
        ["cyan", "blue"],
    ])

# Et sjakkbrett
draw_grid(canvas, 170, 30, 370, 250, [
        ["white", "black"] * 4,
        ["black", "white"] * 4,
    ] * 4)

# En 2D-liste med kun én rad
draw_grid(canvas, 50, 310, 350, 370, [
    ['#00c', '#01c', '#02c', '#03c', '#04c', '#05c', '#06c', '#07c',
     '#08c', '#09c', '#0ac', '#0bc', '#0cc', '#0dc', '#0ec', '#0fc']
])

display(canvas)
Eksempelkjøring 1

from uib_inf100_graphics.simple import canvas, display
from colored_grid import draw_grid

# Et 3x3 rutenett med innebygde farger
draw_grid(canvas, 40, 100, 120, 180, [
        ["red", "green", "blue"],
        ["yellow", "pink", "cyan"],
        ["black", "gray", "orange"],
    ])

# Et sjakkbrett
draw_grid(canvas, 170, 30, 370, 250, [
        ["white", "black"] * 4,
        ["black", "white"] * 4,
    ] * 4)

# En 2D-liste med kun én rad
draw_grid(canvas, 50, 310, 350, 370, [
    ['#00c', '#01c', '#02c', '#03c', '#04c', '#05c', '#06c', '#07c',
     '#08c', '#09c', '#0ac', '#0bc', '#0cc', '#0dc', '#0ec', '#0fc']
])

display(canvas)
Eksempelkjøring 1

PS: I denne oppgaven skal outline være med når du tegner rektangler.

  • Begynn med å definere to variabler rows og cols som representere antall rader og antall kolonner i rutenettet. Antall rader er lengden på den ytre listen (len(color_grid)) mens antall kolonner er lengden på den første indre listen (len(color_grid[0])). Vi antar at det er like mange kolonner i hver rad, slik at vi ikke trenger å sjekke alle.

  • Definer to variabler cell_width og cell_height som representerer henholdsvis bredden og høyden på en celle i rutenettet. Bredden til en celle vil være differansen mellom x-koordinatene delt på antall kolonner, mens høyden til en celle vil være differansen mellom y-koordinatene delt på antall rader.

  • La oss gå gjennom hver eneste mulige kombinasjon av en rad og en kolonne. La row og col være iterandene i to nøstede for-løkker; la row gå fra 0 opp til (ikke inkludert) rows, og la col gå fra 0 og opp til (men ikke inkludert) cols.

  • Inne i den nøstede løkken skal vi tegne cellen i rad row og kolonne col. For å tegne cellen, må vi regne ut koordinatene (cell_x1, cell_y1) som er punktet til venstre øverst i cellen, og punktet (cell_x2, cell_y2) som er punktet til høyre nederst.

    • For å regne ut cell_x1, begynner vi på koordinatet x1 og flytter oss cell_width piksler til høyre col ganger.
    • For å regne ut cell_y1, begynner vi på koordinatet y1 og flytter oss cell_height piksler nedover row ganger.
    • For å regne ut cell_x2, begynn på cell_x1 og flytt deg cell_width piksler til høyre.
    • For å regne ut cell_y2, begynn på cell_y1 og flytt deg cell_height piksler nedover.

  • Etter at du har regnet ut koordinatene til cellen, kall create_rectangle på canvas. Etter de posisjonelle argumentene vi regnet ut over, bruk fill=color_grid[row][col] for å sette fargen.

Nivå D
Alternerende sum

I filen alternating_sum.py opprett funksjonen alternate_sign_sum som tar inn en liste med tall summands som parameter. Funksjonen skal regner 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")

  • 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(summands)), 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.

Nivå C
Minste absolutt-forskjell

I filen least_difference.py skriv funksjonen smallest_absolute_difference som har en liste med tall a som parameter. Funksjonen skal returnerer den minste absolutt-verdi som er forskjellen mellom to tall i listen a.

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

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 summands[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(summands); regn ut absolutt-verdien av forskjellen på summands[i] og summands[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.

Nivå B
Ordspill

Denne oppgaven består av to deler. Skriv funksjoner til begge deloppgaver (A-B) i én felles fil, word_games.py.

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.

Del A

Opprett en funksjon can_be_made_of_letters(word, letters) som tar inn en streng word og en streng letters som parametre. Funksjonen skal returere True hvis strengen word kan lages med bokstavesamlingen letters, og False hvis ikke.

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

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

Opprett en funksjon possible_words(wordlist, letters) som tar inn en liste med strenger wordlist og en streng letters som parametre. Funksjonen skal retunere en liste med alle ord fra wordlist som kan lages med bokstavene i letters.

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

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")
Nivå A
Komprimering

Denne oppgaven består av to deler. Skriv funksjoner til begge deloppgaver (A-B) i én felles fil, runlength_encoding.py.

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 lister og ikke direkte med 1’ere og 0’ere lagret i minnet.

Del A

Opprett en funksjon compress(raw_binary) som tar inn en streng raw_binary bestående av 0’ere og 1’ere. Funksjonen skal retunerer en liste som representerer sekvensen i komprimert form (tall skilles med mellomrom).

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

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

  • Det finnes mange måter å løse dette problemet på. Det kan være lurt å begynne med å sjekke om første tegn er “1”. Hvis det er tilfelle legg til 0. Fordi 0 indikerer at det første tegnet ikke er «0».
  • Lag en variabel som begynner på 0 (int) den kan brukes for å telle antall 0’ere og 1’ere, og en tom liste.
  • Lag en løkke som går fra 0 opp til lengden av stringen - 1. Dette lar oss sammenligne to tegn samtidig.
  • I løkken sjekk om tegnet er lik neste tegn, feks “if [i] == [i + 1]:” hvis dette er True øk telleren med 1. Hvis dette ikke stemmer legg verdien til telleren i listen, og tilbakestill teleren til 1.
  • Når løkken er feridg legg till telleren i listen igjen.
  • Bruk join funksjonen til å konvertere listen til en string, return den stringen.
  • Pass på å bruke str() for å konvertere int til str.

Del B

Opprett en funksjon decompress(compressed_binary) som tar inn en liste compressed_binary beståenden av heltall som representerer en komprimert sekvens av 0’ere og 1’ere. La funksjonen returnere den ukomprimerte sekvensen av 0’ere og 1’ere.

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

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