Op tafel liggen $$n$$ kaarten, waardoor enkel de bovenkant van elke kaart zichtbaar is. Er staan twee getallen op elke kaart, één aan elke kant van de kaart. De getallen lopen van 1 tot en met $$2n$$ en elk van die getallen komt juist één keer voor op één van de kaarten. Je moet een willekeurig aantal kaarten kiezen, die kaarten omdraaien en dan de $$n$$ getallen op de bovenkant van de kaarten optellen. Wat is de maximale som die je op die manier kunt bereiken?
Het hoogste getal dat je zeker kunt bereiken is \[ \left\lceil{\frac{1 + 2 + 3 + \cdots + 2n}{2}}\right\rceil = \left\lceil{\frac{n(2n + 1)}{2}}\right\rceil \] Als de som van de zichtbare getallen aan de bovenkant van de kaarten groter of gelijk is aan deze waarde, dan laat je de kaarten gewoon liggen. Anders moet je de $$n$$ kaarten allemaal omdraaien.
Omdat je niet weet op welke manier de onzichtbare getallen verdeeld zijn over de onderkant van de kaarten, is dit in het slechtste geval misschien het beste dat je kunt doen. Stel bijvoorbeeld dat $$n=50$$ en dat de getallen 26 tot en met 75 zichtbaar zijn op de bovenkant van de kaarten. Dit is in totaal \[ 26 + 27 + \cdots + 75 = 2525 = \frac{1 + 2 + 3 + \cdots + 100}{2} \] Stel dat de $$k$$ kaarten die je omdraait de eerste $$k$$ kaarten zijn in de reeks $$1, 2, \ldots, 25, 76, 77, \ldots, 100$$. Als je minder dan 26 kaarten omdraait, dan zal de som steeds verder onder de 2525 zakken. Als je er meer omdraait, dan zal de som vanaf de 26e kaart terug beginnen stijgen. Maar pas bij de 50e kaart bereik je terug 2525. Hoe dan ook zal je in totaal nooit meer dan 2525 krijgen.
Een kaart waarop twee getallen staan — één aan elke kant van de kaart — stellen we voor als een tuple met twee getallen (int): het eerste is het zichtbare getal aan de bovenkant van de kaart en het tweede is het onzichtbare getal aan de onderkant van de kaart. Een reeks kaarten stellen we voor als een lijst (list) met kaarten (tuple) waarop twee getallen staan.
Gevraagd wordt:
Schrijf een functie zichtbaar waaraan een reeks (list) met kaarten (tuple) moet doorgegeven worden. De functie moet de som teruggeven van alle getallen die zichtbaar zijn aan de bovenkant van de kaarten in de gegeven reeks.
Schrijf een functie maximum waaraan een reeks (list) met kaarten (tuple) moet doorgegeven worden. De functie moet de som teruggeven die bekomen wordt door voor elke kaart van de gegeven reeks het grootste getal aan beide kanten van de kaart te nemen.
Schrijf een functie omdraaien waaraan een reeks (list) met kaarten (tuple) moet doorgegeven worden. De functie heeft een tweede optionele parameter selectie waaraan een reeks (list of tuple) met getallen (int) kan doorgegeven worden. Alle getallen in de reeks die aan de parameter selectie wordt doorgeven, moeten zichtbaar zijn aan de bovenkant van minstens één kaart in de gegeven reeks kaarten. Als dat niet het geval is dan mag de functie de reeks kaarten niet wijzigen en moet een AssertionError opgeworpen worden met de boodschap ongeldige selectie. Anders moet de functie alle kaarten in de gegeven reeks omdraaien waarvoor het getal aan de bovenkant van de kaart voorkomt in de reeks die aan de parameter selectie wordt doorgegeven, zonder dat de functie iets teruggeeft. Als er niet expliciet een argument wordt doorgegeven aan de parameter selectie dan moet de functie alle kaarten in de gegeven reeks kaarten omdraaien.
Schrijf een functie isgeldig waaraan een reeks (list) met $$n$$ kaarten (tuple) moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of elk getal van 1 tot en met $$2n$$ juist één keer voorkomt op één van de kaarten in de gegeven reeks.
Schrijf een functie genereer_kaarten waaraan een getal $$n \in \mathbb{N}$$ (int) moet doorgegeven worden. De functie moet een reeks (list) met $$n$$ kaarten (tuple) teruggeven, waarbij elk getal van 1 tot en met $$2n$$ juist één keer voorkomt op één van de kaarten. De getallen moeten volledige willekeurig op de kaarten geplaatst worden.
>>> kaarten = [(5, 9), (6, 10), (2, 7), (1, 8), (4, 3)]
>>> zichtbaar(kaarten)
18
>>> maximum(kaarten)
38
>>> omdraaien(kaarten)
>>> kaarten
[(9, 5), (10, 6), (7, 2), (8, 1), (3, 4)]
>>> zichtbaar(kaarten)
37
>>> omdraaien(kaarten, [3])
>>> kaarten
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> zichtbaar(kaarten)
38
>>> omdraaien(kaarten, [1])
Traceback (most recent call last):
AssertionError: ongeldige selectie
>>> kaarten
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> omdraaien(kaarten, (9, 10, 2))
Traceback (most recent call last):
AssertionError: ongeldige selectie
>>> kaarten
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> omdraaien(kaarten, (4, 7, 9))
>>> kaarten
[(5, 9), (10, 6), (2, 7), (8, 1), (3, 4)]
>>> zichtbaar(kaarten)
28
>>> isgeldig(kaarten)
True
>>> isgeldig([(5, 9), (10, 6), (8, 1), (3, 4)])
False
>>> isgeldig([(5, 9), (10, 6), (9, 7), (8, 1), (3, 4)]) # twee keer 9, geen 2
False
>>> genereer_kaarten(5)
[(9, 5), (8, 1), (2, 3), (6, 4), (7, 10)]
>>> genereer_kaarten(5)
[(2, 3), (4, 1), (7, 8), (9, 10), (6, 5)]