Listeoppgaver (frivillig)

Disse oppgavene er frivillige i sin helhet. De vil ikke bli rettet – men om du ønsker tilbakemelding, kan du gjerne be en gruppeleder om å se på din besvarelse sammen med deg. Den inneholder flere oppgaver om lister og kan brukes som ekstra trening.

Nivå D
Diverse

Denne oppgaven består av fire deler. Skriv funksjoner til alle deloppgaver i én felles fil, assorted_tasks.py.

Del A

Skriv en destruktiv funksjon remove_threes(a) som tar inn en liste med tall a som parameter. Funksjonen skal mutere listen slik at alle forekomster av tallet 3 blir borte. Fordi funksjonen er destruktiv, trenger den ikke returnere noe.

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

print('Tester remove_threes... ', end='')
# Test 1
a = [1, 2, 3, 4]
remove_threes(a)
assert(a == [1, 2, 4])

# Test 2
a = [1, 2, 3, 3]
remove_threes(a)
assert(a == [1, 2])

# Test 3
a = [3, 3, 1, 3, 2, 4, 3, 3, 3]
remove_threes(a)
assert(a == [1, 2, 4])

# Test 4
a = [3, 3]
remove_threes(a)
assert(a == [])
print('OK')

Så lenge det finnes en 3’er i listen: fjern en 3’er fra listen.

Del B

Skriv en ikke-destruktiv funksjon every_fourth(a) som tar inn en liste a som parameter. Funksjonen skal returnere en ny liste som inneholder hvert fjerde element fra a (begynn med det første elementet, altså elementet på indeks 0).

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

print('Tester every_fourth... ', end='')
# Test 1
a = ['a', 'b', 'c', 'd', 'e']
assert(['a', 'e'] == every_fourth(a))
assert(['a', 'b', 'c', 'd', 'e'] == a)

# Test 2
a = list(range(10))
assert([0, 4, 8] == every_fourth(a))
assert(list(range(10)) == a)

# Test 3
a = list(range(20, 1000))
assert(list(range(20, 1000, 4)) == every_fourth(a))
assert(list(range(20, 1000)) == a)
print('OK')

  • Opprett en resultatliste (som i utgangspunktet er tom)
  • Gå gjennom listen a med en indeksert løkke. Dersom indeks er delelig med 4, legg til elementet i resultatlisten.

Del C

Skriv en destruktiv funksjon halve_values(a) som tar en liste med tall a som parameter. Funksjonen skal mutere listen slik at alle tallene i listen halveres.

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

print('Tester halve_values... ', end='')
a = [1, 2, 3]
halve_values(a)
assert([0.5, 1, 1.5] == a)
print('OK')

  • Gå gjennom listen a med en indeksert løkke. Inne i løkken muterer vi listen i den posisjonen indeks refererer til.

Del D

Skriv en destruktiv funksjon add_list(a, b) som tar to like lange lister av tall a og b som parametre. Funksjonen skal mutere listen a slik at verdiene i listen a økes med verdiene i listen b på tilsvarende posisjoner.

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

print('Tester add_list... ', end='')
a = [1, 2, 3]
b = [4, 2, -3]
add_list(a, b)
assert([5, 4, 0] == a)
assert([4, 2, -3] == b)
print('OK')

  • Gå gjennom listen a med en indeksert løkke
  • For hver indeks, regn ut summen av verdiene fra a og b med den gitte indeksen.

Del E

Skriv en destruktiv funksjon remove_duplicates(a) som tar inn en liste a som parameter. Funksjonen skal mutere listen slik at alle duplikater blir fjernet. For eksempel, hvis a er [1, 2, 3, 2, 1, 4, 5, 4], skal funksjonen mutere a slik at den blir [1, 2, 3, 4, 5].

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

print('Tester remove_duplicates... ', end='')
# Test 1
a = [1, 2, 3, 2, 1, 4, 5, 4]
remove_duplicates(a)
assert [1, 2, 3, 4, 5] == a
print('OK')

Del F

Skriv en destruktiv funksjon som fjerner alle tall som er delelig med 3 fra en liste med tall. Funksjonen skal mutere listen slik at alle tall som er delelig med 3 blir fjernet.

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

print('Tester remove_divisible_by_three... ', end='')
# Test 1
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
remove_divisible_by_three(a)
assert [1, 2, 4, 5, 7, 8] == a
print('OK')
Nivå D
Sorter etter tegn

I filen sorted_by_sign.py, skriv en ikke-destruktiv funksjon sorted_by_sign(a) som tar inn en liste med helltall a som parameter. Funksjonen skal returnerer en ny liste som består av:

  • Først, alle de negative tallene i samme rekkefølgen de opptrådte i a.
  • Deretter, alle 0 -verdiene.
  • Og til slutt, alle de positive tallene i samme rekkefølge de opptrådte i a.

For eksempel, hvis a er [3, -4, 1, 0, -1, 0, -2], skal funksjonen returnere listen [-4, -1, -2, 0, 0, 3, 1].

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

print('Tester sorted_by_sign... ', end='')
# Test 1
a = [3, -4, 1, 0, -1, 0, -2]
assert([-4, -1, -2, 0, 0, 3, 1] == sorted_by_sign(a))

# Test 2
a = [10, -10, -2, 0, 0, 30, 10]
assert([-10, -2, 0, 0, 10, 30, 10] ==  sorted_by_sign(a))

# Test 3
a = [100, -10, -20, 1000, -1000, 10]
assert([-10, -20, -1000, 100, 1000, 10] == sorted_by_sign(a))
print('OK')
Nivå D
2D-lister

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

Funksjonene i denne oppgaven har alle en 2D-liste som input og skal fjerne en rad destruktivt og ikke-destruktivt, og fjerne en kolonne destruktivt og ikke-destruktivt.

Del A

Skriv en destruktiv funksjon remove_row(table, row) som har en 2D-liste table og et radnummer row som parametre. Funksjonen skal mutere table slik at rad row blir fjernet.

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

print('Tester remove_row... ', end='')
# Test 1
table = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33],
    ]
remove_row(table, 0)
assert([
        [21, 22, 23],
        [31, 32, 33],
    ] == table)

# Test 2
table2 = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]
remove_row(table2, 1)
assert([
        [11, 12, 13],
        [31, 32, 33],
    ] == table2)
print('OK')

Tenk på table som en 1-dimensjonell liste og bruk metoder fra kursnotatere om vanlige lister for å destruktivt fjerne raden.

Del B

Skriv en ikke-destruktiv funksjon row_removed(table, row) som har en 2D-liste table og et radnummer row som parametre. Funksjonen skal returnere en ny liste med alle radene i table bortsett fra raden row.

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

print('Tester row_removed... ', end='')
table = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]

table_without_row1 = row_removed(table, 1)
assert([
        [11, 12, 13],
        [31, 32, 33],
    ] == table_without_row1)
    
# Sjekk at vi ikke har mutert table
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ] == table)

# Sjekk at table_without_row1 ikke inneholder aliaser til table
table_without_row1[0][1] = 1212 # Muterer table_without_row1
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ] == table)
print('OK')

I denne oppgaven kan det være lurt å bryte aliaset ved å lage en kopi, og deretter benytte funksjonen fra deloppgave A på kopien.

Del C

Skriv en destruktiv funksjon remove_col(table, col) som har en 2D-liste table og et kolonnenummer col som parametre. Funksjonen skal mutere table slik at kolonnen col blir fjernet.

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

print('Tester remove_col... ', end='')
# Test 1
table1 = [
        [16, 8, 3],
        [2, 10, 15],
    ]
remove_col(table1, 0)
assert([
        [8, 3],
        [10, 15],
    ] == table1)

# Test 2
table2 = [
        [3, 0, 9],
        [4, 5, 3],
        [6, 8, 1],
    ]
remove_col(table2, 1)
assert ([
        [3, 9],
        [4, 3],
        [6, 1],
    ] == table2)
print('OK')

Benytt en løkke som går gjennom hver rad, og der muterer hver av radene (de innerste listene i 2D-listen). For selve mutasjonen av en rad, bruk metoder fra kursnotatere om vanlige lister for å destruktivt fjerne elementer.

Del D

Skriv en ikke-destruktiv funksjon col_removed(table, col) som har en 2D-liste table og et kolonnenummer col som parametre. Funksjonen skal returnere en ny 2D-liste med alle kolonnene i table bortsett fra kolonne col.

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

print('Tester col_removed... ', end='')
# Test 1
table = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]
assert ([
        [12, 13],
        [22, 23],
        [32, 33],
    ] == col_removed(table, 0))
# Sjekk at table ikke ble mutert
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33],
    ] == table)

# Test 2
assert ([
        [11, 12],
        [21, 22],
        [31, 32],
    ]== col_removed(table, 2))
print('OK')

  • Begynn med å opprette en tom liste result = [], som vi skal mutere for å opprette resultatet vårt. Merk at selv om vi muterer result, vil ikke metoden være destruktiv, siden result er en liste vi selv har opprettet inne i funksjonen.
  • For hver rad i table, bruk metoder fra kursnotatere om vanlige lister for å ikke-destruktivt opprette en ny liste som ikke inkluderer kolonnen som skal fjernes. Legg den nye raden inn i result-listen.

Nivå D
Rad og kolonne sum

I filen row_and_column_sum.py skriv funksjonen all_rows_and_cols_equal_sum(table) som har en en 2D-liste med tall table som parameter. Funksjonen skal returnere True dersom listen har samme sum langs alle rader, og samme sum langs alle kolonner, og returnerer False hvis ikke.

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

print('Tester all_rows_and_cols_equal_sum... ', end='')
# Test 1
assert True is all_rows_and_cols_equal_sum([
        [16, 8, 3],     # begge rader summerer til 27
        [2, 10, 15],    # alle kolonner summerer til 18
    ])
    
# Test 2
assert False is all_rows_and_cols_equal_sum([
        [3, 0, 9],   # rad0 summerer til 12, col0 summerer til 13
        [4, 5, 3],   # rad1 summerer til 12, col1 summerer til 13
        [6, 8, 1],   # rad2 summerer til 15, col2 summerer til 13
    ])

# Test 3
assert False is all_rows_and_cols_equal_sum([
        [3, 4, 6],   # rad0 summerer til 13, col0 summerer til 12
        [0, 5, 8],   # rad1 summerer til 13, col1 summerer til 12
        [9, 3, 1],   # rad2 summerer til 13, col2 summerer til 15
    ])

# Test 3
assert True is all_rows_and_cols_equal_sum([
        [1, 2, 3, 4], # alle rader og kolonner summerer til 10
        [2, 3, 4, 1],
        [3, 4, 1, 2],
        [4, 1, 2, 3],
    ])
print('OK')

Del opp problemet i mindre biter:

  • Skriv en hjelpemetode som finner summen av tallene i en gitt kolonne
  • Skriv en hjelpemetode som sjekker om en kolonne har samme sum som sin nabokolonne
  • Skriv en hjelpemetode som sjekker at alle kolonnene har samme sum som sin nabokolonne
  • Tilsvarende for rader
  • Bruk hjelpemetodene for løse problemet.

Nivå C
Komplementstreng

En DNA-sekvens (f.eks ATAGCAGT) sammensettes av 4 ulike «baser», som beskrives vanligvis med bokstavene A, T, G og C. Under replikasjon av DNA-sekvensen kan hver base settes sammen med eksakt én av de andre: A med T, og C med G.

original ------->
         ATAGCAGT
         ||||||||
         TATCGTCA
         <------- complement

Slik får man en «komplementstreng» av den opprinnelige DNA-sekvensen.

Det er vanlig å skrive komplementstrenger baklengs, slik at i vårt eksempel sier vi at komplementstrengen til ATAGCAGT er ACTGCTAT (ikke TATCGTCA).

I filen complementation.py lag en funksion som heter complement(seq) som returnerer komplementstrengen av en DNA-sekvens. Funksjonen skal ta inn en streng seq som representerer en DNA-sekvens, og skal returnere sekvensens komplementstreng.

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

print('Tester complement... ', end='')
assert('ACTGCTAT' == complement('ATAGCAGT'))
assert('TAGTATCTAGT' == complement('ACTAGATACTA'))
assert('ACACAGCTGCAT' == complement('ATGCAGCTGTGT'))
print('OK')

  • Del opp oppgaven i to steg: (1) regn ut den «fremlengse» komplementstrengen; (2) reverser den.
  • For å regne ut den fremlengse komplementstrengen, benytt en løkke over symbolene i seq og inne i løkken, benytt betingelser for å legge til riktig symbol i en resultatstreng.
  • For å reversere strengen kan du benytte beskjæring med negativt steg.

Nivå B
Ikke-kontinuerlig substreng

En streng sub er en ikke-kontinuerlig substreng av strengen s dersom alle tegnene i sub opptrer i samme rekkefølge i s. For eksempel er "foo" en ikke-kontinuerlig substreng av "good for nothing":

good for nothing
     ||   |
     fo   o

I filen non_contiguous_substring.py, skriv en funksjon non_contiguous_substrings(s) som tar inn en streng s og returnerer en liste med alle ikke-kontinurelige substrenger av s.

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

print('Tester non_contiguous_substrings... ', end='')
# Test 1
# Merk: rekkefølgen på elementene i listen betyr ingenting,
# siden begge listene sorteres før de sammenlignes
assert(sorted([
  '', # Den tomme strengen er alltid en substreng
  'a', 'b', 'c', 'd',
  'ab', 'ac', 'ad', 'bc', 'bd', 'cd',
  'abc', 'abd', 'acd', 'bcd',
  'abcd',
]) == sorted(non_contiguous_substrings('abcd')))

# Test 2
assert(sorted([
  '',
  'f', 'o',  # Merk: 'o' opptrer bare én gang
  'fo', 'oo',
  'foo',
]) == sorted(non_contiguous_substrings('foo')))
print('OK')

For å se løsningen på denne oppgaven, hjelper det å observere følgende:

  • Dersom vi på magisk vis vet løsningen for problemet når strengen vi jobber med er ett symbol kortere, kan vi utnytte den: alle substrenger for den ett symbol kortere strengen, er også substrenger for den lengre strengen. De eneste substrengene som da «mangler» er de som slutter på det siste tegnet i strengen.

  • Begynn med å opprette en resultatliste som inneholder kun den tomme strengen (den tomme strengen er alltid en substreng).
  • Gå gjennom tegnene i s med en løkke; én iterasjon av løkken er ansvarlig for å legge til alle ikke-kontinuerlige substrenger som slutter på dette tegnet.
  • Hvilke valg finnes det for begynnelsen på de substrengene vi nå skal legge til? Det er nettopp de strengene som finnes i resultatlisten fra før.
  • Å utvide en liste samtidig som man løkker over listen krever at man holder tungen beint i munnen. Det kan være lettere å opprette en hjelpeliste substrings_ending_at_c hvor man legger til bare dem som slutter på gitte tegn, og så utvide resultatlisten med denne listen når den er ferdig utregnet.
  • Benytt funksjonen no_duplicates du skrev i lab5 for å fjerne duplikater.

Hvor mange ikke-kontinuerlige substrenger finnes det for strengen 'good for nothing'?

Nivå A
Ordsøk

I filen wordsearch.py 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.

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

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

glossary = ['dikt', 'hus', 'lese', 'by', 'elev', 'så',
            'smart', 'helt', 'mål', 'yr', 'lære', 'ås']
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', 'så']) == sorted(found_words))
print('OK')

  • Opprett en hjelpefunksjon som sjekker om et gitt ord finnes i char_grid vertikalt og begynner på en bestemt posisjon (row, col).
    • Begynn med å sjekke om det gitte ordet er for langt, og hvis det er det, returner False. Et ord er for langt dersom høyden på rutenettet (antall rader) er mindre enn startradens indeks (row) + ordets lengde.
    • Benytt løkke over ordet som sjekkes, og sjekk inni løkken at tegnet på denne posisjonen i ordet er den samme som posisjonen i rutenettet. Øk indeks til raden i rutenettet med én for hver iterasjon.
    • Dersom du finner en forskjell, returner False
    • Dersom du ikke fant en forskjell etter at du er ferdig med hele løkken, returner True

  • Skriv en funksjon tilsvarende den i kulepunktet over, men som sjekker horisontalt.
  • Opprett en funksjon som sjekker om et gitt ord finnes i char_grid: bruk en nøstet for-løkke for å gå gjennom alle mulige start-posisjoner, og bruk deretter hjelpemetodene fra forrige kulepunkter.
  • For hvert ord: sjekk om ordet finnes i char_grid med bruk av hjelpemetoden i forrige kulepunkt.