Basis

Deze pagina bevat uitvoerbare code.

De basis heeft twee delen. Begin na het eerste college met De nacht van het nijlpaard en na het tweede college met De uitslag van de schoolrun.

De nacht van het nijlpaard

Nijlpaarden houden van een goede maaltijd, maar ze willen wel ruimte om zich heen. Elke nacht zet de kok maaltijden op een lange tafel. Aan één kant van de tafel zijn de plaatsen genummerd: 1, 2, 3, enzovoort. Op een plaats kan meer dan één maaltijd staan. De ceremoniemeester bepaalt hoeveel ruimte er tussen de nijlpaarden moet zijn, en zorgt dat er zoveel mogelijk nijlpaarden mee-eten. In deze opgave reken je uit hoeveel dat er zijn.

De regel

Een nijlpaard gaat zitten op een plaats waar een maaltijd staat. De afstand tussen twee nijlpaarden is het verschil van hun plaatsnummers, en die moet minstens gelijk zijn aan de afstand die de ceremoniemeester heeft gekozen. Op één plaats zit hoogstens één nijlpaard.

Gekozen afstand

Plaatsen met een maaltijd

Zoveel nijlpaarden eten mee

Bijvoorbeeld op

1

2, 3, 3

2

2 en 3

2

1, 3, 7

3

1, 3 en 7

4

1, 3, 5, 10, 12

3

1, 5 en 12

Bij afstand 2 zit er dus minstens één lege plaats tussen twee nijlpaarden. In het laatste voorbeeld kunnen er geen vier mee-eten: welke vier plaatsen je ook kiest, er liggen er altijd twee minder dan 4 uit elkaar.

Voorbeeld 1: maaltijden op plaats 2, 3 en 3; nijlpaarden zitten op plaats 2 en 3

Voorbeeld 2: maaltijden op plaats 1, 3 en 7; op alle drie zit een nijlpaard

Voorbeeld 3: maaltijden op plaats 1, 3, 5, 10 en 12; nijlpaarden zitten op plaats 1, 5 en 12

De plaatsen staan in deze opgave altijd oplopend in de lijst.

Wat je gaat maken

Stap

Functie

Doet

Wat je oefent

1

far_enough

liggen twee plaatsen ver genoeg uit elkaar?

geen recursie

2

drop_too_close

haal de plaatsen weg die te dicht bij een nijlpaard liggen

één recursieve aanroep

3

hippo_dinner

hoeveel nijlpaarden kunnen er hoogstens mee-eten?

use it or lose it

Stap 1: far_enough(a, b, distance)

Geeft True als plaats b minstens distance verder ligt dan plaats a, en anders False. b is nooit kleiner dan a. Deze functie heeft geen recursie nodig.

Aanroep

Resultaat

far_enough(1, 3, 2)

True

far_enough(2, 3, 2)

False

far_enough(3, 3, 1)

False

Hint

Het verschil tussen de twee plaatsen is b - a.

# jouw oplossing

assert far_enough(1, 3, 2) == True
assert far_enough(2, 3, 2) == False
assert far_enough(3, 3, 1) == False
assert far_enough(5, 10, 5) == True

Stap 2: drop_too_close(place, places, distance)

Er zit een nijlpaard op plaats place. places is een oplopende lijst met de plaatsen erna. Geeft de lijst terug zonder de plaatsen aan het begin die te dicht bij place liggen. Vanaf de eerste plaats die ver genoeg ligt, blijft de lijst staan.

Aanroep

Resultaat

drop_too_close(1, [3, 7], 2)

[3, 7]

drop_too_close(3, [3, 5, 8], 4)

[8]

drop_too_close(5, [], 2)

[]

Hint

Gebruik far_enough uit stap 1. Ligt de eerste plaats ver genoeg, dan ben je klaar: dan geef je de hele lijst terug. Omdat de lijst oplopend is, liggen de plaatsen daarna nog verder weg.

# jouw oplossing

assert drop_too_close(1, [3, 7], 2) == [3, 7]
assert drop_too_close(3, [3, 5, 8], 4) == [8]
assert drop_too_close(1, [3, 5, 10, 12], 4) == [5, 10, 12]
assert drop_too_close(5, [6, 7], 3) == []
assert drop_too_close(5, [], 2) == []

Stap 3: hippo_dinner(distance, places)

places is een oplopende lijst met de plaatsen waar een maaltijd staat. Geeft terug hoeveel nijlpaarden er hoogstens kunnen mee-eten als de afstand tussen twee nijlpaarden minstens distance moet zijn. Gebruik recursie.

Aanroep

Resultaat

hippo_dinner(1, [2, 3, 3])

2

hippo_dinner(2, [1, 3, 7])

3

hippo_dinner(4, [1, 3, 5, 10, 12])

3

hippo_dinner(3, [])

0

Hint

Kies bij de eerste plaats, zoals bij subset in het college:

  • Use it: er gaat een nijlpaard op de eerste plaats zitten. Dat is er één, plus zoveel als er passen op de rest, nadat je met drop_too_close de plaatsen hebt weggehaald die te dicht bij de eerste liggen.

  • Lose it: op de eerste plaats gaat niemand zitten. Dan tel je zoveel als er op de rest passen.

Geef het grootste van de twee terug.

# jouw oplossing

assert hippo_dinner(1, [2, 3, 3]) == 2
assert hippo_dinner(2, [1, 3, 7]) == 3
assert hippo_dinner(4, [1, 3, 5, 10, 12]) == 3
assert hippo_dinner(3, [4]) == 1
assert hippo_dinner(3, []) == 0

Tot slot

Bij afstand 4 en maaltijden op 1, 3, 5, 10 en 12 eten er drie nijlpaarden mee. Of je de eerste plaats moet gebruiken, kon hippo_dinner niet vooraf weten. Pas door beide keuzes te proberen vond de functie het beste antwoord, precies zoals subset in het college.

hippo_dinner zegt hoeveel nijlpaarden er mee-eten, maar niet op welke plaatsen. Hoe je ook de gekozen elementen terugkrijgt, zie je aan het eind van het tweede college.

(Informatica Olympiade 2023-2024)

De uitslag van de schoolrun

Op de sportdag lopen de leerlingen een rondje van drie kilometer. Na afloop moet er een uitslag komen: wie was het snelst, wat is de ranglijst, en wie wint bij de jeugd, onder de 18? In deze opgave schrijf je die functies. In stap 4 tot en met 7 geef je een andere functie mee: aan max, min of sorted, of aan een functie die je zelf schrijft.

De uitslag

De uitslag is een lijst van lijsten. Elke deelnemer is een lijst met drie elementen:

Index

Betekenis

Voorbeeld

0

naam

"Noor"

1

leeftijd in jaren

17

2

tijd in seconden

754

Noor liep het rondje dus in 754 seconden: 12 minuten en 34 seconden. Wie de kleinste tijd heeft, was het snelst. De cel hieronder zet de uitslag klaar in RESULTS. Voer hem eerst uit.

RESULTS = [
    ["Noor", 17, 754],
    ["Sem", 19, 698],
    ["Lotte", 18, 698],
    ["Yara", 16, 812],
    ["Finn", 21, 745],
]

Wat je gaat maken

Stap

Functie

Doet

Wat je meegeeft

4

fastest

de naam van de snelste

een lambda-functie aan min

5

ranking

de namen van snel naar langzaam

een lambda-functie met een sleutel van twee delen aan sorted

6

select

de deelnemers die aan een voorwaarde voldoen

een functie als argument aan je eigen functie

7

winner

de naam van de snelste die aan een voorwaarde voldoet

een functie als argument, die je weer aan select meegeeft

8

youth_podium

maximaal drie namen onder een leeftijdsgrens

je kiest zelf aanpak en opbouw

opdracht 1

de functies van stap 4 tot en met 7

wat moet er veranderen bij gelijke tijden?

je beschrijft de wijziging, zonder code

Stap 4: fastest(results)

Geeft de naam van de deelnemer met de kleinste tijd. results is niet leeg. Hebben twee deelnemers dezelfde tijd, dan wint wie het eerst in de lijst staat.

Aanroep

Resultaat

fastest(RESULTS)

"Sem"

fastest([["Ali", 20, 600]])

"Ali"

Hint

min met een lambda-functie achter key= geeft de hele deelnemer met de kleinste tijd, zoals max(players, key=lambda p: p[1]) in het tweede college. Van die deelnemer geef je alleen de naam terug. Bij gelijke tijden geeft min vanzelf de eerste.

# jouw oplossing

assert fastest(RESULTS) == "Sem"
assert fastest([["Ali", 20, 600]]) == "Ali"

Stap 5: ranking(results)

Geeft een lijst met de namen van alle deelnemers, van de snelste naar de langzaamste. Hebben twee deelnemers dezelfde tijd, dan komt de naam die in het alfabet eerst komt vooraan.

Aanroep

Resultaat

ranking(RESULTS)

["Lotte", "Sem", "Finn", "Noor", "Yara"]

ranking([])

[]

Sem en Lotte hebben allebei 698 seconden. Lotte staat vooraan, want de L komt vóór de S.

Hint

Een sleutel mag ook een lijst zijn. Python vergelijkt twee lijsten zoals twee woorden: eerst het eerste element, en pas als dat gelijk is het tweede. [698, "Lotte"] komt dus vóór [698, "Sem"]. Laat de lambda-functie de lijst [tijd, naam] teruggeven. Zet daarna met een list comprehension alleen de namen in een lijst.

# jouw oplossing

assert ranking(RESULTS) == ["Lotte", "Sem", "Finn", "Noor", "Yara"]
assert ranking([["Bo", 30, 700], ["Ad", 25, 700]]) == ["Ad", "Bo"]
assert ranking([]) == []

Stap 6: select(results, test)

test is een functie die bij een deelnemer True of False teruggeeft. Geeft een lijst met de deelnemers uit results waarvoor test True teruggeeft, in dezelfde volgorde.

Aanroep

Resultaat

select(RESULTS, lambda r: r[1] < 18)

[["Noor", 17, 754], ["Yara", 16, 812]]

select(RESULTS, lambda r: r[1] > 30)

[]

De lambda-functie in het eerste voorbeeld geeft True voor wie jonger is dan 18: de jeugd.

Hint

Een list comprehension met een if, zoals in week 2. Roep in de if de functie test aan op elke deelnemer.

# jouw oplossing

assert select(RESULTS, lambda r: r[1] < 18) == [["Noor", 17, 754], ["Yara", 16, 812]]
assert select(RESULTS, lambda r: r[2] < 700) == [["Sem", 19, 698], ["Lotte", 18, 698]]
assert select(RESULTS, lambda r: r[1] > 30) == []

Stap 7: winner(results, test)

Geeft de naam van de snelste deelnemer waarvoor test True teruggeeft. Er is altijd minstens één zo’n deelnemer.

Aanroep

Resultaat

winner(RESULTS, lambda r: r[1] < 18)

"Noor"

winner(RESULTS, lambda r: r[1] >= 18)

"Sem"

Hint

Je hebt alles al. winner geeft test mee aan select, en zoekt in wat daar uitkomt de snelste met fastest. Dat past op één regel.

# jouw oplossing

assert winner(RESULTS, lambda r: r[1] < 18) == "Noor"
assert winner(RESULTS, lambda r: r[1] >= 18) == "Sem"
assert winner(RESULTS, lambda r: r[0][0] == "Y") == "Yara"

Stap 8: een jeugdpodium

De schoolrun krijgt een podium voor deelnemers jonger dan een meegegeven leeftijdsgrens. Schrijf youth_podium(results, age_limit): een lijst met maximaal drie namen, van snel naar langzaam en bij gelijke tijd op alfabet. Zijn er minder dan drie geschikte deelnemers, dan is de lijst korter. Zonder geschikte deelnemers krijg je een lege lijst. De gegevens hebben dezelfde vorm als RESULTS; namen zijn uniek en leeftijden en tijden zijn gehele getallen. Wie precies de leeftijdsgrens heeft bereikt, doet niet mee aan dit podium.

Aanroep

Resultaat

youth_podium(RESULTS, 18)

["Noor", "Yara"]

youth_podium(RESULTS, 16)

[]

Je kent al comprehensions, recursie en functies als argument. Als je met zulke middelen zelf de verwerking van invoer naar resultaat ontwerpt, werk je hier functioneel. Eén eigen functie met een comprehension of recursie kan al voldoen. Alleen een def rond code met lussen en toekenningen is niet genoeg. Kies zelf de passende middelen, aanpak en opbouw; bestaande functies gebruiken mag, maar hoeft niet.

Noteer vóór je programmeert hoe je het podium bepaalt en hoe je de functies opbouwt. Noem daarbij welk functioneel middel je kiest en wat het in jouw verwerking doet. Schrijf daarna je code met een docstring en eigen assertions. Wijs bij de terugblik in je code aan waar je dat middel gebruikt en welk deel van het resultaat het berekent. Vergelijk je uitvoering met je plan: wat heb je behouden of veranderd, en waarom?

Hint

Probeer ook een uitslag waarbij de derde en vierde geschikte deelnemer even snel zijn. Controleer dan welke naam de laatste podiumplaats krijgt.

# jouw plan

# jouw oplossing en eigen assertions

assert youth_podium(RESULTS, 18) == ["Noor", "Yara"]
assert youth_podium(RESULTS, 16) == []
assert youth_podium([], 18) == []
assert youth_podium([["Bo", 17, 700]], 18) == ["Bo"]
assert youth_podium([["Bo", 18, 600], ["Ad", 17, 700]], 18) == ["Ad"]
assert youth_podium(
    [["Daan", 17, 700], ["Cato", 16, 700], ["Bo", 17, 600], ["Ad", 15, 500]], 18
) == ["Ad", "Bo", "Cato"]

# vergelijking met je plan

Opdracht 1: dezelfde regel bij gelijke tijden

Maak eerst stap 4 tot en met 8 af. Voer de aparte analyseversie hieronder uit, ook als jouw eigen code anders is. Ze vervangt de gelijknamige functies en RESULTS in je notebook, maar bevat geen uitwerking van het jeugdpodium.

De school wil voortaan ook bij fastest en winner bij gelijke tijden de alfabetisch eerste naam als winnaar. Je beschrijft de wijziging; je hoeft haar niet te programmeren. De voorwaarden voor niet-lege invoer blijven gelden.

RESULTS = [
    ["Noor", 17, 754],
    ["Sem", 19, 698],
    ["Lotte", 18, 698],
    ["Yara", 16, 812],
    ["Finn", 21, 745],
]

def fastest(results):
    """Geeft de naam van de deelnemer met de kleinste tijd; results is niet leeg."""
    return min(results, key=lambda r: r[2])[0]


assert fastest(RESULTS) == "Sem"
assert fastest([["Ali", 20, 600]]) == "Ali"

def ranking(results):
    """Geeft de namen van snel naar langzaam; bij gelijke tijd op alfabet."""
    return [r[0] for r in sorted(results, key=lambda r: [r[2], r[0]])]


assert ranking(RESULTS) == ["Lotte", "Sem", "Finn", "Noor", "Yara"]
assert ranking([["Bo", 30, 700], ["Ad", 25, 700]]) == ["Ad", "Bo"]
assert ranking([]) == []

def select(results, test):
    """Geeft de deelnemers uit results waarvoor test True teruggeeft."""
    return [r for r in results if test(r)]


assert select(RESULTS, lambda r: r[1] < 18) == [["Noor", 17, 754], ["Yara", 16, 812]]
assert select(RESULTS, lambda r: r[2] < 700) == [["Sem", 19, 698], ["Lotte", 18, 698]]
assert select(RESULTS, lambda r: r[1] > 30) == []

def winner(results, test):
    """Geeft de naam van de snelste deelnemer waarvoor test True teruggeeft."""
    return fastest(select(results, test))


assert winner(RESULTS, lambda r: r[1] < 18) == "Noor"
assert winner(RESULTS, lambda r: r[1] >= 18) == "Sem"
assert winner(RESULTS, lambda r: r[0][0] == "Y") == "Yara"

Beantwoord in de cel hieronder, als commentaar:

  1. Wat is de verantwoordelijkheid van elk van de vier gegeven functies?

  2. Welke functies roepen elkaar aan? Welke functie wordt als argument doorgegeven, en waar wordt die aangeroepen?

  3. Waar moet de regel voor gelijke tijden veranderen? Wijs de sleutel aan en onderbouw waarom deze plek ook het gedrag van winner verandert.

  4. Wat verandert er voor fastest, winner, ranking en select bij RESULTS en bij [["Bo", 16, 700], ["Ad", 17, 700]]? Bespreek bij winner zowel jeugd als volwassenen voor RESULTS. Wat gebeurt er zonder gelijke tijden? Welke bestaande assertions moeten veranderen, en welke blijven geldig?

Dit antwoord onderzoekt bestaande samenwerking. Het is afzonderlijk van je ontwerp en code voor het jeugdpodium in stap 8.

# jouw analyse

Tot slot

Sem en Lotte liepen even snel: allebei 698 seconden. fastest geeft Sem, omdat hij eerder in de lijst staat en min bij een gelijke tijd de eerste kiest. De ranglijst zet Lotte vooraan, omdat daar bij een gelijke tijd het alfabet beslist. Twee functies, twee regels voor een gelijke stand. Bij de jeugd wint Noor.

In stap 4 tot en met 7 gaf je een functie mee. In stap 4 en 5 gaf je een lambda-functie aan min en sorted; die riepen die functie bij elke deelnemer aan. In stap 6 schreef je zelf een functie die een functie als argument krijgt, en in stap 7 gaf je die functie weer mee. Zo maakt één winner de winnaar van elke categorie: alleen de lambda-functie die je meegeeft, verschilt.