Goochelaar Bob Hummer bedacht een magische kaartentruc die bestaat uit de volgende handelingen:
-
kies willekeurig tien kaarten uit een kaartspel en leg ze allemaal op een stapel met de beeldzijde naar onder
-
neem de bovenste twee kaarten van de stapel af, draai ze samen om en leg ze terug bovenaan de stapel
-
coupeer de stapel kaarten op een willekeurige plaats; bij het couperen van een stapel kaarten wordt de stapel in twee gesplitst, en wordt het bovenste deel van de stapel onder het onderste deel van de stapel geschoven
-
herhaal stappen (2) en (3) zo vaak je wil
-
draai alle kaarten op de even posities om: de tweede, de vierde, de zesde, de achtste en de tiende kaart, waarbij we beginnen te tellen vanaf de bovenste kaart
Dit levert altijd een stapel op waarvan er vijf kaarten met de beeldzijde naar boven liggen.
Onderstaande figuur toont een uitgewerkt voorbeeld van de kaartentruc, waarbij we de posities van de kaarten in de stapel van boven naar onder genummerd hebben van 1 tot en met 10. Elke kaart wordt voorgesteld met een unieke kleur en de uitstulping geeft aan of de kaart met de beeldzijde naar boven of naar onder ligt. Stappen (2) en (3) worden in dit voorbeeld drie keer herhaald, waarbij we achtereenvolgens in stap (3) couperen na 4, 5 en 3 kaarten. Uiteindelijk liggen na stap (5) de tweede, de derde, de zesde, de achtste en de negende kaart met de beeldzijde naar boven.
Later bewezen Persi Daconis en Ron Graham dat deze truc algemeen werkt voor een stapel van $$2n$$ kaarten, waarbij er finaal $$n$$ kaarten met de beeldzijde naar boven liggen.
Opgave
Een standaard kaartspel bestaat uit 52 verschillende kaarten die onderverdeeld worden in vier kleuren van elk 13 kaarten: 13 klaveren (♣), 13 ruiten (♦), 13 harten (♥) en 13 schoppen (♠). Klaveren en schoppen zijn zwart, ruiten en harten zijn rood, maar het zijn niet deze fysieke kleuren, maar de soorten die met de term kleur aangeduid worden. Van elke kleur zijn er telkens kaarten met een rang van 2 tot en met 10, een boer, een vrouw, een heer en een aas. Daarnaast bevat een spel soms twee of drie jokers, maar die laten we hier even buiten beschouwing.
We stellen elk van de 52 kaarten van een standaard kaartspel voor als een string (str) die bestaat uit de rang van de kaart, gevolgd door de kleur van de kaart:
-
rangen: 2, 3, 4, 5, 6, 7, 8, 9, 10, J (boer), Q (vrouw), K (heer) en A (aas)
-
kleuren: C (klaveren; ♣), D (ruiten; ♦), H (harten; ♥) en S (schoppen; ♠)
Zo stelt AS bijvoorbeeld schoppenaas voor, 10H hartentien en KC klaverenheer. Bovendien leggen we vast dat de voorstelling van een kaart die met zijn beeldzijde naar boven ligt gebruik maakt van hoofdletters (bijvoorbeeld AS of 10H), en dat de voorstelling van een kaart die met zijn beeldzijde naar onder ligt gebruik maakt van kleine letters (bijvoorbeeld as of 10h). Merk op dat het laatste karakter van de voorstelling altijd een hoofdletter of een kleine letter is (geen cijfer) die de kleur van de kaart aanduidt.
De lijstvoorstelling van een stapel kaarten bestaat uit een lijst (list) met de voorstellingen van de opeenvolgende kaarten uit de stapel, waarbij de bovenste kaart van de stapel het eerste element van de lijst is. Sommige kaarten van de stapel liggen met hun beeldzijde naar boven en de andere met hun beeldzijde naar onder. Een stapel hoeft niet noodzakelijk alle 52 kaarten van een kaartspel te bevatten, maar mag nooit meerdere keren dezelfde kaart bevatten.
Gevraagd wordt:
-
Schrijf een functie is_geldige_kaart waaraan één enkel argument moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of het gegeven argument een geldige voorstelling van een kaart is.
-
Schrijf een functie stringvoorstelling waaraan de lijstvoorstelling van een stapel met $$n \in \mathbb{N}_0$$ kaarten moet doorgegeven worden. De functie moet een stringvoorstelling (str) van de stapel teruggeven, die bestaat uit de voorstellingen van de opeenvolgende kaarten van de stapel (van boven naar onder), telkens van elkaar gescheiden door een spatie. Hierbij wordt een kaart die met zijn beeldzijde naar boven ligt op de standaard manier voorgesteld. Een kaart die met zijn beeldzijde naar onder ligt wordt voorgesteld door twee sterretjes (**).
-
Schrijf een functie selectie_omdraaien waaraan de lijstvoorstelling van een stapel met $$n \in \mathbb{N}_0$$ kaarten moet doorgegeven worden. Optioneel kan als tweede argument ook nog een reeks (list of tuple) van posities in de stapel doorgegeven worden. Hierbij worden de posities van de kaarten van boven naar onder genummerd vanaf 1. De functie mag ervan uitgaan dat alle posities in de gegeven reeks geldig zijn en dat elke positie hoogstens één keer voorkomt. De functie moet alle kaarten op de aangegeven posities in de stapel individueel omdraaien, waarbij de kaarten niet van positie veranderen. Als er geen tweede argument wordt doorgegeven aan de functie dan moeten alle kaarten in de stapel individueel omgedraaid worden, zonder dat de kaarten daarbij van positie veranderen.
De tweede, de vijfde en de negende kaart individueel omdraaien, zonder dat ze van plaats verwisselen. -
Schrijf een functie bovenste_omdraaien waaraan twee argumenten moeten doorgegeven worden: i) de lijstvoorstelling van een stapel met $$n \in \mathbb{N}_0$$ kaarten en ii) een aantal kaarten $$a \in \mathbb{N}$$ ($$0 \leq a \leq n$$). De functie moet de bovenste $$a$$ kaarten afnemen van de stapel, deze kaarten samen omdraaien en daarna terug bovenaan de stapel leggen. Dit is de handeling die uitgevoerd wordt in stap (2) van de kaartentruc met $$a = 2$$.
Bovenste vier kaarten omdraaien. -
Schrijf een functie couperen waaraan twee argumenten moeten doorgegeven worden: i) de lijstvoorstelling van een stapel met $$n \in \mathbb{N}_0$$ kaarten en ii) een aantal kaarten $$a \in \mathbb{N}$$ ($$0 \leq a \leq n$$). De functie moet de bovenste $$a$$ kaarten van de stapel afnemen en deze kaarten onder de resterende kaarten van de stapel schuiven. Dit is de handeling die uitgevoerd wordt in stap (3) van de kaartentruc.
Couperen na zes kaarten.
Aan de functies stringvoorstelling, selectie_omdraaien, bovenste_omdraaien en couperen moet als eerste argument een lijstvoorstelling van een stapel kaarten doorgegeven worden. Indien dit argument geen geldige lijstvoorstelling is dan moet een AssertionError opgeworpen worden met de boodschap ongeldige stapel.
De functies selectie_omdraaien, bovenste_omdraaien en couperen moeten telkens de gegeven lijstvoorstelling van de stapel kaarten aanpassen en een referentie naar deze stapel teruggeven. De functie stringvoorstelling mag de gegeven lijstvoorstelling van de stapel kaarten niet aanpassen.
Voorbeeld
Onderstaande code simuleert de opeenvolgende handelingen die in de inleiding uitgevoerd werden bij het voorbeeld van de kaartentruc (zie figuur).
>>> is_geldige_kaart('AS')
True
>>> is_geldige_kaart('10h')
True
>>> is_geldige_kaart('KC')
True
>>> is_geldige_kaart(42)
False
>>> is_geldige_kaart('11d')
False
>>> is_geldige_kaart('7X')
False
>>> is_geldige_kaart('qC')
False
>>> stapel = ['AH', '3S', 'KC', '4H', '3D', '10H', '8D', '5D', '7C', 'QS']
>>> stringvoorstelling(stapel)
'AH 3S KC 4H 3D 10H 8D 5D 7C QS'
>>> selectie_omdraaien(stapel)
['ah', '3s', 'kc', '4h', '3d', '10h', '8d', '5d', '7c', 'qs']
>>> stringvoorstelling(stapel)
'** ** ** ** ** ** ** ** ** **'
>>> bovenste_omdraaien(stapel, 2)
['3S', 'AH', 'kc', '4h', '3d', '10h', '8d', '5d', '7c', 'qs']
>>> stringvoorstelling(stapel)
'3S AH ** ** ** ** ** ** ** **'
>>> couperen(stapel, 4)
['3d', '10h', '8d', '5d', '7c', 'qs', '3S', 'AH', 'kc', '4h']
>>> stringvoorstelling(stapel)
'** ** ** ** ** ** 3S AH ** **'
>>> bovenste_omdraaien(stapel, 2)
['10H', '3D', '8d', '5d', '7c', 'qs', '3S', 'AH', 'kc', '4h']
>>> stringvoorstelling(stapel)
'10H 3D ** ** ** ** 3S AH ** **'
>>> couperen(stapel, 5)
['qs', '3S', 'AH', 'kc', '4h', '10H', '3D', '8d', '5d', '7c']
>>> stringvoorstelling(stapel)
'** 3S AH ** ** 10H 3D ** ** **'
>>> bovenste_omdraaien(stapel, 2)
['3s', 'QS', 'AH', 'kc', '4h', '10H', '3D', '8d', '5d', '7c']
>>> stringvoorstelling(stapel)
'** QS AH ** ** 10H 3D ** ** **'
>>> couperen(stapel, 3)
['kc', '4h', '10H', '3D', '8d', '5d', '7c', '3s', 'QS', 'AH']
>>> stringvoorstelling(stapel)
'** ** 10H 3D ** ** ** ** QS AH'
>>> selectie_omdraaien(stapel, [2, 4, 6, 8, 10])
['kc', '4H', '10H', '3d', '8d', '5D', '7c', '3S', 'QS', 'ah']
>>> stringvoorstelling(stapel)
'** 4H 10H ** ** 5D ** 3S QS **'
>>> stapel = ['AH', '3S', 'KC', '4H', '3D', '11H', '8D', '5D', '7C', 'QS']
>>> stringvoorstelling(stapel)
Traceback (most recent call last):
AssertionError: ongeldige stapel
>>> selectie_omdraaien(stapel)
Traceback (most recent call last):
AssertionError: ongeldige stapel
>>> bovenste_omdraaien(stapel, 2)
Traceback (most recent call last):
AssertionError: ongeldige stapel
>>> couperen(stapel, 2)
Traceback (most recent call last):
AssertionError: ongeldige stapel