8.2 DRILL — Funksjoner over nøstede strukturer

Full drill på Oppgave 5: litt tyngre funksjoner over nøstede lister/ordbøker, ofte med to nivåers løkke og et flagg/akkumulator, av og til byggende på en tidligere funksjon.

75 min

10 oppgaver

DRILLFunksjoner over nøstede strukturer

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

8.1Nøstede lister og ordbøker 2.1Funksjoner: def, parametere og return

Brukes videre i

8.PPrøver til del 8: Nøstede strukturer

Dette kapitlet trener Oppgave 5, og bare den.

Sjanger G — skriv en funksjon over en nøstet liste eller ordbok står i
4 av 6 moderne eksamenssett (67 %) og er verdt 8–10 poeng, typisk fordelt på
to funksjoner à 4–5 poeng. Den andre bygger ofte på den første.

Dette skal du kunne — bokas midterste av tre prioritetsnivåer.

Bestillingene går igjen: «finn alt som er felles», «grupper etter …», «sjekk om alle …», «bygg en ny nøstet struktur». Alle er de samme fire mønstrene, og alle har den samme todelte løkka i seg.

Kapitlet er langt (~75 min) og er delt i tre økter med tidsanslag. Ta gjerne én økt om gangen.

Forkunnskaper — sist du var her

Kapitlet bygger på kap. 8.1 — Nøstede lister og ordbøker
og kap. 2.1 — Funksjoner.

De tre tingene drillen hviler på, friskes opp med kjørt kode.

1. To nivåers løkke over en nøstet ordbok:

uke = {"mandag": {"a": 3, "b": 5}, "tirsdag": {"a": 7}}
for dag in uke:
    for akt in uke[dag]:
        print(dag, akt, uke[dag][akt])

Utskrift:

mandag a 3 mandag b 5 tirsdag a 7

2. Oppbygging med to sjekker:

d = {}
for rad in [["a", "x", 1], ["a", "x", 4]]:
    if rad[0] not in d:
        d[rad[0]] = {}
    if rad[1] not in d[rad[0]]:
        d[rad[0]][rad[1]] = 0 d[rad[0]][rad[1]] = d[rad[0]][rad[1]] + rad[2]
print(d)

Utskrift:

{'a': {'x': 5}}

3. Funksjon med parameter og return etter løkka:

def tell_over(liste, grense):
    antall = 0 for x in liste:
        if x > grense:
            antall = antall + 1 return antall

print(tell_over([3, 8, 5], 4))

Utskrift:

Har du de tre, er resten rotasjon av mønsteret.

📜Løsningsoppskriften for sjanger G — fire steg

Bruk den samme framgangsmåten hver gang.

Steg 1 — Avgjør de to nivåene. Skriv ned hva det ytre nivået er, og hva det
indre er. «Ytre = dag, indre = aktivitet, verdi = antall deltakere.» Ti sekunder, og halve fellene forsvinner.

Steg 2 — Velg mønster. Fire dekker nesten alt:

- teller eller akkumulator over to nivåer — «hvor mange», «hvor mye til
sammen»,
- flagg med tidlig retur — «finnes det …», «er alle …»,
- bygg en ny struktur — «lag en ordbok fra … til …», «finn alt som er
felles»,
- oppslag med sjekk på begge nivåer — «hva var antallet for …».

Steg 3 — Håndter kant-tilfellene. Tom struktur, én indre struktur, indre
strukturer med ulik størrelse, og verdier som finnes på begge nivåer.

Steg 4 — Plassér akkumulatoren. Utenfor begge løkkene for en total, inne i
den ytre for «per rad». Det er det ene valget som oftest avgjør poenget.

Og til slutt: gjenbruk gjerne en funksjon du har skrevet i a). Oppgaveteksten legger som regel opp til det, og du kan kalle den selv om den ikke ble helt riktig.

De fire mønstrene

Kjenn dem igjen på formuleringen i oppgaveteksten: Formulering Mønster «hvor mange \dots», «hvor mye til sammen» teller eller akkumulator «finnes det \dots», «er alle \dots» flagg med tidlig retur «lag en ordbok fra \dots til \dots», «grupper etter \dots» bygg en ny struktur «hva er antallet for \dots» oppslag med sjekk på begge nivåer Alle fire har den samme todelte løkka i seg. Det som skiller dem, er hva som står inne i løkka, og hvor akkumulatoren eller returen står. Den todelte løkkestrukturen er selve poenget i sjanger G, og riktig struktur belønnes selv med en indeksfeil.

Formulering	Mønster
«hvor mange …», «hvor mye til sammen»	teller eller akkumulator
«finnes det …», «er alle …»	flagg med tidlig retur
«lag en ordbok fra … til …», «grupper etter …»	bygg en ny struktur
«hva er antallet for …»	oppslag med sjekk på begge nivåer

Økt 1 — Den gjennomarbeidede casen (~20 min)

Under står en komplett Oppgave 5 med to funksjoner, slik den kommer på eksamen, med margnotater om hva som gir uttelling.

✏️Eksempel 1: Full Oppgave 5 med sensor-margnotater

> En nøstet ordbok går fra ukedag til aktivitet til antall deltakere.
>
> a) Skriv deltakere_per_aktivitet(uke) som returnerer en flat ordbok fra
> aktivitet til samlet antall over alle dagene.
>
> b) Skriv finnes_paa_alle_dager(uke, aktivitet) som returnerer True bare
> hvis aktiviteten finnes på hver dag i uka.

Steg 1 — nivåene. Ytre = dag, indre = aktivitet, verdi = antall deltakere.

Steg 2 — mønstre. a) er «bygg en ny struktur» med en teller inni. b) er «er
alle …», altså flagg med tidlig retur.

def deltakere_per_aktivitet(uke):
    ut = {}
    for dag in uke:
        for akt in uke[dag]:
            if akt not in ut:
                ut[akt] = 0 ut[akt] = ut[akt] + uke[dag][akt]
    return ut

def finnes_paa_alle_dager(uke, aktivitet):
    for dag in uke:
        if aktivitet not in uke[dag]:
            return False return True

uke = {"mandag": {"spinning": 14, "yoga": 9},
       "tirsdag": {"spinning": 20, "yoga": 4},
       "onsdag": {"yoga": 3, "styrke": 11}}

print(deltakere_per_aktivitet(uke))
print(finnes_paa_alle_dager(uke, "yoga"))
print(finnes_paa_alle_dager(uke, "spinning"))
print(finnes_paa_alle_dager({}, "yoga"))

Utskrift:

{'spinning': 34, 'yoga': 16, 'styrke': 11}
True
False
True

Sensors margnotater.

a) (5 p): ut = {} før begge løkkene (1 p), den todelte løkka (1 p),
if akt not in ut: og ut[akt] = 0 (2 p), akkumuleringen med + og det doble oppslaget uke[dag][akt] (1 p). return står etter begge løkkene — inne i dem ville funksjonen svart etter første dag.

b) (5 p): løkka over ytternøklene (1 p), if aktivitet not in uke[dag]:
(2 p), return False inne i løkka (1 p), return True etter den (1 p).

Å snu de to returene er feilkode #7. Med return True inne i løkka ville
funksjonen svart ja så snart aktiviteten fantes på én dag — og da hadde
spinning også gitt True.

Legg merke til den siste linja: en tom uke gir True. Løkka går ingen runder,
så koden faller rett til return True. Det er logisk riktig — «alle dager har aktiviteten» er sant når det ikke finnes noen dager — men det er verdt en kommentar hvis oppgaven kan tolkes annerledes.

Og legg merke til at b) bare trenger én løkke. Det indre nivået sjekkes med
not in, ikke med en løkke. Å skrive to løkker der én holder, er ikke galt, men det er lengre og lettere å bomme på.

— naturlig pausepunkt —

Økt 2 — Teller, flagg og oppslag (~28 min)

De fem første oppgavene roterer de tre enkleste mønstrene over ulike strukturer:
nøstet liste, nøstet ordbok, og en ordbok med lister som verdier.

📝Oppgave 1

(Innstegsoppgave — minimal sporing.) Gitt
y = [[4, 9], [2], [7, 1, 8]].

a) Skriv antall_tall(y) som returnerer hvor mange tall det er til sammen.

b) Skriv sum_alle(y) som returnerer summen.

c) Hvorfor kan du ikke bare bruke len(y) i a)?

📝Oppgave 2

Eksamensnivå, sjanger G

En nøstet liste holder poeng per runde for hver spiller: [[3, 5, 2], [7, 1], [4, 4, 4]].

a) Skriv sum_per_spiller(data) som returnerer en liste med summen for hver
spiller.

b) Skriv beste_runde(data) som returnerer det høyeste enkeltpoenget i hele
strukturen.

c) Skriv alle_har_spilt(data, minst) som returnerer True bare hvis alle
spillerne har spilt minst så mange runder.

📝Oppgave 3

Eksamensnivå, sjanger A

Hva skriver programmet ut?

def f(y):
    ut = []
    s = 0 for indre in y:
        for x in indre:
            s = s + x ut.append(s)
    return ut

print(f([[1, 2], [3], [4, 5]]))

📝Oppgave 4

Eksamensnivå, sjanger G

En nøstet ordbok går fra butikknavn til varenavn til antall på lager.

a) Skriv lager(d, butikk, vare) som gir antallet, eller 0 hvis butikken
eller varen ikke finnes.

b) Skriv butikker_med(d, vare) som returnerer en liste over navnene på
de butikkene som har varen.

c) Skriv totalt_av(d, vare) som gir det samlede antallet av varen over alle
butikkene.

📝Oppgave 5

Eksamensnivå, sjanger A

Hva skriver programmet ut?

d = {"a": {"x": 1, "y": 2}, "b": {"y": 5}, "c": {}}

antall_ytre = 0 antall_indre = 0 sum_alle = 0 for ytre in d:
    antall_ytre = antall_ytre + 1 for indre in d[ytre]:
        antall_indre = antall_indre + 1 sum_alle = sum_alle + d[ytre][indre]
print(antall_ytre, antall_indre, sum_alle)
print(len(d), len(d["c"]))

Økt 3 — Bygg nye strukturer og finn feil (~27 min)

De siste fem oppgavene er de tyngste: å bygge en ny nøstet struktur, å finne det som er felles, og å rette en modell som ser riktig ut.

📝Oppgave 6

Eksamensnivå, sjanger G

En liste av registreringer har formen [dag, sal, antall].

a) Skriv bygg(data) som returnerer en nøstet ordbok fra dag til sal til
samlet antall.

b) Skriv snu(nostet) som returnerer en ny nøstet ordbok med nivåene
byttet om: fra sal til dag til antall.

c) Test begge, og forklar hvorfor snu trenger de samme to sjekkene som
bygg.

📝Oppgave 7

Eksamensnivå, sjanger G

En ordbok går fra spillernavn til en liste over spill spilleren liker.

a) Skriv felles(d, a, b) som returnerer en liste over spillene både a og
b liker. Returner en tom liste hvis en av dem ikke finnes.

b) Skriv adskilt(d, a, b) som returnerer en liste over spillene bare én
av dem liker.

c) Skriv mest_populaere(d) som returnerer tittelen på det spillet flest
liker.

📝Oppgave 8

Eksamensnivå, sjanger G

En nøstet ordbok beskriver hvilke soner en kollektivbillett er gyldig i: fra billettype til sone til True eller False.

a) Skriv gyldig(regler, billett, sone) som returnerer True bare hvis
billetten er registrert som gyldig i sonen. Manglende billett eller sone gir
False.

b) Skriv soner_for(regler, billett) som returnerer en liste over sonene
billetten er gyldig i.

c) Skriv kan_reise(regler, billett, reise) der reise er en liste av soner,
og som returnerer True bare hvis billetten er gyldig i alle sonene.

d) Test alle tre, inkludert en tom reise.

📝Oppgave 9

Eksamensnivå, sjanger G

En liste av registreringer har formen [dag, aktivitet, deltakernavn].

a) Skriv bygg(data) som returnerer en nøstet ordbok fra dag til aktivitet
til en liste av deltakernavn.

b) Skriv antall_unike(nostet) som returnerer hvor mange ulike deltakere
det er til sammen, uansett dag og aktivitet.

c) Test begge.

📝Oppgave 10

Eksamensnivå, sjanger I

En medstudent har skrevet:

def per_aktivitet(uke):
    ut = {}
    for dag in uke:
        for akt in uke[dag]:
            ut[akt] = uke[dag][akt]
    return ut

def alle_dager(uke, akt):
    for dag in uke:
        if akt in uke[dag]:
            return True return False

a) Hva er feil i per_aktivitet?

b) Hva er feil i alle_dager, gitt at den skal svare om aktiviteten finnes på
alle dager?

c) Gi et konkret moteksempel på hver av dem, og skriv de rettede
funksjonene.

Typiske feil i dette kapitlet

Fem feil koster nesten alle poengene som mistes på sjanger G:

- Å blande de to nivåene. for akt in uke: i den indre løkka går gjennom
dagene på nytt; y[j][i] er et annet oppslag enn y[i][j].
- #7 — feil vei på returene. «Finnes det …» gir True inne i løkka og
False etter; «er alle …» er motsatt. Å snu dem gir riktig type svar og feil innhold.
- #14 — å bygge uten å opprette først. Både den indre strukturen og den indre
nøkkelen må opprettes, i den rekkefølgen.
- Å overskrive der du skulle akkumulere. ut[akt] = verdi i stedet for
ut[akt] = ut[akt] + verdi gir verdien fra den siste runden i stedet for summen.
- #6 — kant-tilfellene. Tom struktur, tom indre struktur, og indre strukturer
med ulik størrelse. En «alle»-sjekk gir True på en tom struktur — riktig, men verdt en kommentar.

Og én plasseringsfeil: akkumulatoren utenfor den ytre løkka når den skulle vært inne i den. Den gir løpende summer i stedet for én sum per rad.

API- og konstruksjonsliste

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.

Sjanger G — formen

To funksjoner over nøstede lister eller ordbøker, 4-5 poeng hver, til sammen 8-10 poeng. Sjangeren står i 4 av 6 moderne sett (67 %), som Oppgave 5. Den andre funksjonen bygger ofte på den første: «bruk funksjonen fra a) til å \dots». Da kan du kalle den selv om den ikke ble helt riktig — sensor vet hva den skulle gjøre. Den todelte løkkestrukturen er selve poenget, og riktig struktur belønnes selv med en indeksfeil.

Steg 1 — skriv ned de to nivåene

«Ytre = dag, indre = aktivitet, verdi = antall deltakere.» Ti sekunder på kladden, og halve fellene forsvinner: du blander ikke nivåene, du vet hvilken variabel som er en nøkkel, og du vet hvor verdien hentes. Det er den samme disiplinen som steg 0 i fil-deloppgaven — å lese formatet før du koder.

De fire mønstrene

Teller eller akkumulator — «hvor mange», «hvor mye til sammen». Flagg med tidlig retur — «finnes det \dots», «er alle \dots». Bygg en ny struktur — «lag en ordbok fra \dots til \dots», «grupper etter \dots», «snu nivåene». Oppslag med sjekk på begge nivåer — «hva var antallet for \dots». Alle fire har den samme todelte løkka. Det som skiller dem, er hva som står inne i løkka, og hvor akkumulatoren eller returen står.

Akkumulatorens plassering

Den ene avgjørelsen som oftest bestemmer om svaret blir riktig. Utenfor begge løkkene: én sum for hele strukturen. Inne i den ytre løkka: én sum per indre struktur — «per spiller», «per dag». En akkumulator som skulle vært nullstilt og ikke blir det, gir løpende summer i stedet for enkeltsummer. Begge deler kan være riktig; oppgaveteksten avgjør. Les hvor den står før du sporer. Én linjes forskjell i innrykk gir et helt annet svar.

Når én løkke holder

Skal det indre nivået bare testes, ikke gås gjennom, holder én løkke: if vare in d[butikk]: . Skal det indre nivået måles, holder også én: if len(spiller) < minst: . Å skrive to løkker der én holder, er ikke galt — bare lengre og lettere å bomme på. Spør alltid: må jeg se hvert element, eller bare vite om noe finnes?

Å snu nivåene

Å bygge en ny nøstet ordbok der den gamle indrenøkkelen blir den nye ytternøkkelen. Mønsteret er en to nivåers løkke inn og to if -sjekker ut — oppbyggings-malen brukt på målstrukturen. At kildestrukturen finnes, hjelper ikke: målstrukturen starter tom, og begge nivåene i den må opprettes. Kjenn den igjen i oppgaveteksten på «lag en oversikt over hvilke dager hver sal er i bruk».

Å flate ut

Å summere bort det ene nivået: fra dag \to aktivitet \to antall til aktivitet \to totalt antall . Formen er teller-idiomet med en to nivåers løkke rundt seg, og resultatet er en vanlig ordbok. Den vanligste feilen er å overskrive i stedet for å akkumulere. ut[akt] = uke[dag][akt] gir verdien fra den siste dagen; ut[akt] = ut[akt] + uke[dag][akt] gir summen.

Finn det felles

for x in d[a]: med if x in d[b]: inne i seg, og .append(x) når begge har den. Rekkefølgen i svaret følger den første lista. Det er verdt å vite når du skal spore en utskrift. Motstykket — «det bare én av dem har» — trenger to løkker, én hver vei. Med bare den første overses det den andre har alene, og det er den vanligste feilen i mønsteret.

Duplikater over flere nivåer

sett = [], if navn not in sett: sett.append(navn), og return len(sett) . Mønsteret er det samme uansett hvor dypt navnene ligger — du trenger bare én løkke per nivå for å nå dem. Variabelnavnet sett er trygt; set ville skygget en innebygd funksjon, og det er feilkode #13 .

Verdien brukt rett som betingelse

Er verdien allerede True eller False, kan den stå rett i en if : if regler[billett][sone]: . Og en funksjon kan returnere den direkte: return regler[billett][sone] . En ekstra if som gjør om True til True, er overflødig. Formen er kort og lesbar — men bare når verdien faktisk er en sannhetsverdi. Er den et tall, betyr if tall: «tallet er ikke null», og det er sjelden det du mente.

Tomme strukturer

En tom indre ordbok er en helt gyldig verdi, og den er ikke det samme som at nøkkelen mangler. len(d["c"]) er 0 når c finnes med en tom ordbok; d["z"] stopper programmet når z ikke finnes i det hele tatt. I en to nivåers løkke teller den tomme indre strukturen med i den ytre løkka, men gir null runder i den indre. Det er en fast sporingsfelle.

«Alle»-sjekk på tom struktur

En «er alle \dots»-funksjon returnerer True på en tom struktur: løkka går ingen runder, og koden faller rett til return True . Det er logisk riktig — «alle elementene oppfyller kravet» er sant når det ikke finnes noen elementer — og det er slik matematikken definerer det. Men det kan overraske, og oppgaveteksten kan mene noe annet. Skriv en kommentarlinje om valget, så ser sensor at det er bevisst.

Tidlig retur med tom liste

if a not in d: return ut der ut er den tomme lista. Det er et bevisst valg framfor None : den som kaller, kan bruke svaret i en løkke uten å sjekke først, og en tom liste betyr naturlig «ingen treff». None er bedre når svaret skal sammenlignes eller brukes som et objekt. Les hva oppgaven skal gjøre med resultatet.

Å gjenbruke funksjonen fra a)

kan_reise kaller gyldig; totalt_av kaller lager; beste_spiller kaller sum_per_spiller . Oppgaveteksten legger nesten alltid opp til det ved å be om den enkle funksjonen først. Gjenbruken er et selvstendig poeng, ikke bare en snarvei. Og den er trygg: du kan kalle funksjonen fra a) selv om du ikke fikk den helt riktig. Sensor vet hva den skulle gjøre.

Repetisjon — de seks setningene som må sitte

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.