Listeoppgaver

Diverse

Denne oppgaven består av flere deler. Skriv funksjoner til alle deloppgaver i én felles fil, assorted_list_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.

def test_remove_threes():
    print('Tester remove_threes... ', end='', flush=True)
    # 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')

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

def test_every_fourth():
    print('Tester every_fourth... ', end='', flush=True)
    # 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
    print('OK')

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.

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

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.

def test_add_list():
    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')

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; bare den første av hvert unike element beholdes. For eksempel, hvis a er [1, 2, 3, 2, 1, 1, 4, 5, 4], skal funksjonen mutere a slik at den blir [1, 2, 3, 4, 5].

def test_remove_duplicates():
    print('Tester remove_duplicates... ', end='')
    # Test 1
    a = [1, 2, 3, 2, 1, 1, 1, 4, 5, 4, 2]
    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.

def test_remove_divisible_by_three():
    print('Tester remove_divisible_by_three... ', end='', flush=True)
    # Test 1
    a = [1, 2, 3, 4, 5, 6, 12, 300, 7, 8, 9]
    remove_divisible_by_three(a)
    assert [1, 2, 4, 5, 7, 8] == a
    print('OK')

Sortering etter fortegn

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 deg selv:

def test_sorted_by_sign():
    print('Tester sorted_by_sign... ', end='', flush=True)
    # 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')

Fjern rader og kolonner

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

Funksjonene i denne oppgaven forventer alle en 2D-liste som argument og skal fjerne enten en rad eller en kolonne, enten destruktivt eller 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.

def test_remove_row():
    print('Tester remove_row... ', end='', flush=True)
    # 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')

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.

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

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

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

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.

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

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

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 kolonnener i table bortsett fra kolonne col.

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

Radsum og kolonnesum

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:

def test_all_rows_and_cols_equal_sum():
    print('Tester all_rows_and_cols_equal_sum... ', end='', flush=True)
    # Test 1
    arg = [
        [16, 8, 3],     # begge rader summerer til 27
        [2, 10, 15],    # alle kolonner summerer til 18
    ]
    assert all_rows_and_cols_equal_sum(arg) is True
        
    # Test 2
    arg = [
        [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
    ]
    assert all_rows_and_cols_equal_sum(arg) is False

    # Test 3
    arg = [
        [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
    ]
    assert all_rows_and_cols_equal_sum(arg) is False

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

DNA 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:

def test_complement():
    print('Tester complement... ', end='', flush=True)
    assert 'ACTGCTAT' == complement('ATAGCAGT')
    assert 'TAGTATCTAGT' == complement('ACTAGATACTA')
    assert 'ACACAGCTGCAT' == complement('ATGCAGCTGTGT')
    print('OK')

Botanist

Du er en botaniker som har vært på en ekspedisjon til en øy som er kjent for sine mange forskjellige planter. Du har samlet inn en rekke planter og har lagret dem i en liste plants. Du har også en liste dangerous_plants som inneholder navnene på alle de farlige plantene på øya. Du trenger å finne ut hvilke av plantene du har samlet inn som er farlige, slik at du kan fjerne dem fra samlingen din.

I en fil botanist.py, lag en ikke-destruktiv funksjon filtered_dangerous med 2 lister som parameter: en liste kalt plants og en liste av farlige planter kalt dangerous_plants. Funksjonen skal returnere en ny liste med plantene i plants som ikke er farlige.

For eksempel, hvis plants er ["rose", "daisy", "lily", "tulip", "dandelion"] og dangerous_plants er ["dandelion", "poison ivy"], skal funksjonen returnere ["rose", "daisy", "lily", "tulip"].

Du kan starte fra denne koden:

def filtered_dangerous(plants, dangerous_plants):
    # Din kode her

Test deg selv:

def test_filtered_dangerous():
  print("Testing filtered_dangerous... ", end="")
  assert ["rose", "daisy", "lily", "tulip"] == filtered_dangerous(["rose", "daisy", "lily", "tulip", "dandelion"], ["dandelion", "poison ivy"])
  assert ["minalia", "cherluvia", "kirina", "ajisai"] == filtered_dangerous(["minalia", "cherluvia", "kirina", "ajisai", "evil_plant", "raa"], ["evil_plant", "raa"])
  assert ["pythonium"] == filtered_dangerous(["pythonium", "haskelia", "shakersperia"], ["haskelia", "jaskria", "shakersperia"])
  print("OK")

Trylledrikker

Når Trollmannen Gallius brygger trylledrikker, pleier han å sette en styrkegrad på når han er ferdig, for eksempel 10. Disse styrkegradene setter han på en liste. Men Gallius har ikke vert veldig konsekvent med hvor sterk han sier enhver trylledrikk er! For eksempel sier han noen ganger 10 og andre ganger 100 000, og da vet vi ikke hva den øvre grensen er. Han trenger din hjelp til å normalisere nivåene slik at de ligger mellom 0 og 1, som gjør det lettere å se hva som er de sterkeste og svakeste trylledrikkene.

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 \(x_{\text{min}}\) og \(x_{\text{max}}\) ). Deretter må du gå gjennom listen og regne ut en ny verdi \(x’_i\) for hver verdi \(x_i\) i listen. Den nye verdien skal være lik:

hvor \(\Delta x\) angir forskjellen mellom største og minste verdi:

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 \(x_{\text{min}} = 1\), største verdi \(x_{\text{max}} = 5\) og vi kan regne ut \(\Delta x = 4\). Da vil for eksempel nivået for verdien 3 normaliseres til:

$$ \frac{3 - x_{\text{min}}}{\Delta x} = \frac{{3 - 1}}{{4}} = 0.5 $$

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

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.

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

def lists_almost_equal(list_a, list_b):
    if len(list_a) != len(list_b):
        return False
    for i, a in enumerate(list_a):
        if abs(a - list_b[i]) > 0.00000001:
            return False
    return True

def test_normalize_potions():
    def do_test(arg, expected):
        print('.', end='')
        arg_copy = arg.copy()
        actual = normalize_potions(arg)

        assert arg_copy == arg, (
            'Argument was unexpectedly mutated. '
            f'Was first {arg_copy} but is now {arg}.'
        )
        assert lists_almost_equal(expected, actual), (
            f'On input {arg} we expected {expected} '
            f'but got {actual}.'
        )
    
    print('Testing normalize_potions', end='')
    do_test(arg=[1, 2, 3, 4, 5], expected=[0, 0.25, 0.5, 0.75, 1])
    do_test(arg=[3, 2, 1, 0, -1], expected=[1, 0.75, 0.5, 0.25, 0])
    do_test(arg=[0.02, 0.01, 0.05, 0.03], expected=[0.25, 0.0, 1.0, 0.5])
    do_test(arg=[3, 3, 3], expected=[1, 1, 1])
    do_test(arg=[9], expected=[1])
    do_test(arg=[], expected=[])
    print(' OK')

if __name__ == '__main__':
    test_normalize_potions()

Hvetefarm

I denne oppgaven skal vi simulere hveteproduksjon gjennom en “hvetefarm”. Hvetefarmen består av et jorde som er delt inn i et rutenett. Hver rute i rutenettet kan enten være tom, inneholde en hvetespire som vokser, eller inneholde en ferdig hvetekornplante. Hver hvetekornplante går gjennom en syklus av vekst, og når den er ferdig vokst, kan den høstes for hvetekorn.

Syklusen er som følger:

• En tom rute (verdi 0) kan plantes med et frø dersom vi har frø igjen. Når frøet plantes skal verdien endres til 1.
• En hvetespire (verdi 1-7) vokser. Denne økes med 1 hver iterasjon.
• En ferdig vokst hvetekornplante (verdi 8) høstes. Da teller vi opp +1 hvetekorn, setter verdien i ruten til 0 og bruker random til å generere 1-4 nye frø som kan plantes senere.

Under er en funksjon simulate_wheat_farm som simulerer denne syklusen i et rutenett. For hver iterasjon går den gjennom hver rute i field og sjekker hvilket steg i syklusen ruten er på. simulate_wheat_farm har 3 parametere:

• field er en todimensjonal liste av tall som representerer jordet. Hver rute i jordet har en verdi som beskrevet over.
• seeds er antall hvetekorn som er tilgjengelig for planting.
• iterations er antall iterasjoner simuleringen skal kjøre.

Kan du fullføre logikken i funksjonen simulate_wheat_farm? Du vil se det som mangler i koden er markert med # Din kode her. Skriv koden i en fil som heter hvetefarm.py.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import random

MAX_GROWTH = 8

# bruk denne for å se jordet etter hver iterasjon om du ønsker
def print_field(field):
    line = "+---+---+---+---+"
    for row in field:
        print(line)
        for cell in row:
            print(f"| {cell} ", end="")
        print("|")
    print(line)

def simulate_wheat_farm(field, seeds, iterations):
    rows = len(field)
    cols = len(field[0])
    wheat = 0
    for _ in range(iterations):

        for row in range(rows):
            for col in range(cols):
                growth_stage = field[row][col]
                if (growth_stage == 0) and (seeds > 0):   # Plant et frø
                    # Din kode her
                    ...
                elif 1 <= growth_stage < MAX_GROWTH:       # Vokse planten
                    # Din kode her
                    ...
                elif growth_stage == MAX_GROWTH:      # Høst en ferdig plante
                    wheat += 1
                    field[row][col] = 0
                    seeds += random.randint(1, 4)
        # print_field(field)
    return wheat, seeds

def test_simulate_wheat_farm():
    print("Testing simulate_wheat_farm()... ", end="")
    field = [
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ]
    random.seed(1689)
    wheat, seeds = simulate_wheat_farm(field, 1, 10)
    assert wheat == 1
    assert seeds == 0
    
    field = [
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ]
    random.seed(1689)
    wheat, seeds = simulate_wheat_farm(field, 7, 100)
    assert wheat == 167
    assert seeds == 245
    print("OK")

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:

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

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

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

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:

    def test_find_words_in_character_grid():
    print('Tester find_words_in_character_grid... ', end='', flush=True)

    allowed_words = ['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'],
    ]
    expected = ['lese', 'smart', 'mål', 'lære', 'så']
    actual = find_words_in_character_grid(char_grid, allowed_words)
    assert sorted(expected) == sorted(found_words)
    print('OK')