Bij heel wat kaartspelletjes houden de spelers elk een reeks kaarten in hun hand. Nadat de spelers hun willekeurig gedeelde kaarten opgeraapt hebben, dan zitten die op dat moment ook nog willekeurig door elkaar. Neem bijvoorbeeld deze reeks van 13 kaarten die een speler als een waaier in zijn hand houdt.

Om overzicht te houden op zijn kaarten, zal de speler doorgaans voor het spel begint de kaarten in zijn hand op orde steken. Op die manier kan hij tijdens het spel makkelijker zijn strategie bepalen. Wat een logische volgorde is van de kaarten in een hand, hangt af van speler tot speler en van kaartspel tot kaartspel.

Om te kunnen uitleggen wat we als een logische volgorde zullen beschouwen, moet je eerst weten dat een standaard kaartspel bestaat uit 52 verschillende kaarten die onderverdeeld worden in vier soorten van elk 13 kaarten: 13 klaveren (♣), 13 ruiten (♦), 13 harten (♥) en 13 schoppen (♠). Klaveren en schoppen zijn zwart. Ruiten en harten zijn rood. Van elke soort zijn er telkens kaarten met een rang van 2 tot en met 10, een boer, een vrouw, een heer en een aas. Dit is meteen ook onze volgorde voor de verschillende rangen binnen een soort.

We zeggen dan dat een hand gesorteerd is als i) de kaarten in de hand gegroepeerd zijn per soort, ii) de kaarten in elke groep (soort) op volgorde liggen en iii) opeenvolgende groepen bestaan uit kaarten met een verschillende kleur (rood of zwart), behalve als alle kaarten in de hand dezelfde kleur hebben. De laatste voorwaarde betekent dat groepen indien mogelijk afwisselend uit rode en zwarte soorten kaarten moeten bestaan. De combinatie schoppen (♠) – klaveren (♣) – harten (♥) – ruiten (♦) is bijvoorbeeld niet toegelaten, omdat er dan twee groepen met zwarte kaarten na elkaar komen, en ook twee groepen met rode kaarten. Als een speler enkel schoppen (♠) en klaveren (♣) in zijn hand houdt, dan kan hij natuurlijk niet anders dan de twee zwarte soorten na elkaar te steken. De voorbeeld reeks van 13 kaarten kan bijvoorbeeld als volgt gesorteerd worden:

Merk op dat er meerdere manieren kunnen zijn om dezelfde hand met kaarten te sorteren. Zo hadden we ruitendame ook helemaal vooraan kunnen plaatsen, of de groepen met de klaveren en de schoppen van plaats kunnen verwisselen.

Opgave

Zorg ervoor dat we een hand met kaarten kunnen voorstellen, waarin individuele kaarten kunnen verplaatst worden en waarbij kan bepaald worden of de kaarten op volgorde zitten. Hiervoor ga je als volgt te werk.

Kaart

Definieer een klasse Kaart waarmee één kaart uit een standaard kaartspel kan voorgesteld worden. Bij het aanmaken van een nieuwe kaart (Kaart) moet de beschrijving van de kaart doorgegeven worden: een string (str) die bestaat uit de rang van de kaart, gevolgd door het soort kaart:

• rangen: 2, 3, 4, 5, 6, 7, 8, 9, 10, J (boer), Q (vrouw), K (heer) en A (aas)

• soorten: ♣ (klaveren), ♦ (ruiten), ♥ (harten) en ♠ (schoppen)

Merk op dat het soort kaart in de beschrijving altijd voorgesteld wordt door één karakter. Zo beschrijft A♠ bijvoorbeeld schoppenaas, 10♥ hartentien en K♣ klaverenheer. Als er geen geldige beschrijving wordt doorgegeven bij het aanmaken van een kaart (Kaart), dan moet een AssertionError opgeworpen worden met de boodschap ongeldige kaart.

Als er een kaart $$k$$ (Kaart) wordt doorgegeven aan de ingebouwde functie str, dan moet die de beschrijving (str) van kaart $$k$$ teruggeven.

Als er een kaart $$k$$ (Kaart) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een stringvoorstelling (str) van kaart $$k$$ teruggeven die leest als een Python expressie waarmee dezelfde kaart kan aangemaakt worden.

Zorg ervoor dat de zes vergelijkingsoperatoren (==, !=, <, <=, > en >=) kunnen toegepast worden op twee kaarten $$k_1$$ en $$k_2$$ (Kaart). De operatoren == en != moeten aangeven of $$k_1$$ en $$k_2$$ dezelfde (resp. een verschillende) kaart voorstellen. Als de kaarten $$k_1$$ en $$k_2$$ dezelfde soort hebben, dan moeten de vier andere operatoren (<, <=, > en >=) ze volgens rang vergelijken. Anders moeten die operatoren een AssertionError opwerpen met de boodschap kaarten van verschillende soort zijn onvergelijkbaar. 

Hand

Definieer een klasse Hand waarmee een reeks met $$n \in \mathbb{N}$$ verschillende kaarten in de hand van een speler kan voorgesteld worden. Bij het aanmaken van een nieuwe hand (Hand) moeten de beschrijvingen van de kaarten als $$n$$ argumenten doorgegeven worden. Als minstens één van die argumenten geen geldige beschrijving van een kaart voorstelt of als niet alle beschrijvingen verschillend zijn, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige hand.

Als er een hand $$h$$ (Hand) wordt doorgegeven aan de ingebouwde functie str, dan moet die een string (str) teruggeven met de beschrijvingen van de $$n$$ kaarten in hand $$h$$, die telkens van elkaar gescheiden worden door één spatie.

Als er een hand $$h$$ (Hand) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een stringvoorstelling (str) van hand $$h$$ teruggeven die leest als een Python expressie waarmee dezelfde hand kan aangemaakt worden.

Als er een hand $$h$$ (Hand) wordt doorgegeven aan de ingebouwde functie len, dan moet die het aantal kaarten $$n$$ (int) in hand $$h$$ teruggeven.

Voorts moet je op elke hand $$h$$ (Hand) met $$n$$ kaarten minstens de volgende methoden kunnen aanroepen:

• Een methode verplaats waaraan twee getallen $$i$$ en $$j$$ (int) moeten doorgegeven worden. Daarbij moet gelden dat $$0 \leq i,j < n$$. Als dat niet het geval is dan moet een AssertionError opgeworpen worden met de boodschap ongeldige verplaatsing en mag de volgorde van de kaarten in hand $$h$$ niet wijzigen. Anders moet de methode de kaart op positie $$i$$ verplaatsen naar positie $$j$$ in hand $$h$$ — waarbij de posities van de kaarten van links naar rechts genummerd worden vanaf nul — en een verwijzing teruggeven naar hand $$h$$. Een kaart verplaatsen bestaat dus uit het weghalen van een kaart uit hand $$h$$ (op positie $$i$$) en die ergens anders (op positie $$j$$) aan hand $$h$$ terug toevoegen.

• Een methode isgesorteerd waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of hand $$h$$ gesorteerd is. We herhalen nog eens dat dat het geval is als i) de kaarten in de hand gegroepeerd zijn per soort, ii) de kaarten in elke groep (soort) op volgorde liggen en iii) opeenvolgende groepen bestaan uit kaarten met een verschillende kleur (rood of zwart), behalve als alle kaarten in de hand dezelfde kleur hebben.

Voorbeeld

>>> kaart = Kaart('10♥')
>>> kaart
Kaart('10♥')
>>> print(kaart)
10♥

>>> Kaart('1♥0')
Traceback (most recent call last):
AssertionError: ongeldige kaart

>>> Kaart('2♥') < Kaart('10♥')
True
>>> Kaart('7♥') == Kaart('7♥')
True
>>> Kaart('Q♣') > Kaart('8♣')
True
>>> Kaart('7♥') != Kaart('7♣')
True
>>> Kaart('7♥') <= Kaart('7♥')
True
>>> Kaart('7♥') >= Kaart('7♥')
True

>>> Kaart('2♥') < Kaart('10♣')
Traceback (most recent call last):
AssertionError: kaarten van verschillende soort zijn onvergelijkbaar

>>> hand = Hand('6♣', 'K♠', '9♣', 'Q♦', 'Q♠', 'K♣', 'A♣', '4♣', '2♥', 'J♥', '4♠', '3♥', '7♠')
>>> hand
Hand('6♣', 'K♠', '9♣', 'Q♦', 'Q♠', 'K♣', 'A♣', '4♣', '2♥', 'J♥', '4♠', '3♥', '7♠')
>>> print(hand)
6♣ K♠ 9♣ Q♦ Q♠ K♣ A♣ 4♣ 2♥ J♥ 4♠ 3♥ 7♠
>>> len(hand)
13
>>> hand.isgesorteerd()
False
>>> hand.verplaats(1, 12)
Hand('6♣', '9♣', 'Q♦', 'Q♠', 'K♣', 'A♣', '4♣', '2♥', 'J♥', '4♠', '3♥', '7♠', 'K♠')
>>> hand.isgesorteerd()
False
>>> hand.verplaats(-3, 42)
Traceback (most recent call last):
AssertionError: ongeldige verplaatsing
>>> hand.verplaats(2, 12).verplaats(2, 10)
Hand('6♣', '9♣', 'K♣', 'A♣', '4♣', '2♥', 'J♥', '4♠', '3♥', '7♠', 'Q♠', 'K♠', 'Q♦')
>>> hand.isgesorteerd()
False
>>> hand.verplaats(4, 0).verplaats(8, 6)
Hand('4♣', '6♣', '9♣', 'K♣', 'A♣', '2♥', '3♥', 'J♥', '4♠', '7♠', 'Q♠', 'K♠', 'Q♦')
>>> hand.isgesorteerd()
True

>>> Hand('5♦', '4♦', 'spam', '9♥', '3♦')       # ongeldige kaart
Traceback (most recent call last):
AssertionError: ongeldige hand
>>> Hand('9♥', '5♦', '4♦', '5♥', '9♥', '3♦')   # dubbele kaart: 9♥
Traceback (most recent call last):
AssertionError: ongeldige hand

Epiloog

Misschien heb je je ooit al eens afgevraagd wat de meest efficiënte manier zou zijn om de kaarten in je hand op volgorde te steken. Als de verplaatsing van een kaart bestaat uit het weghalen van een kaart uit de hand en die ergens anders aan de hand terug toevoegen, dan komt deze efficiëntie-oefening neer op sorteren van kaarten met zo weinig mogelijk verplaatsingen. De hand van 13 kaarten die we als voorbeeld gebruikt hebben, bevat bijvoorbeeld een deelreeks van 8 kaarten die reeds gesorteerd zijn.

Dat is meteen de langste gesorteerde deelreeks voor deze hand met 13 kaarten. Dat meest efficiënte manier om deze hand op volgorde te steken, bestaat er dus in om de overig vijf kaarten één voor één te verplaatsen.

Het bepalen van een langste gesorteerde deelreeks (want die is niet per se uniek) van een hand met $$n$$ kaarten is een variant op het bepalen van de langste stijgende deelreeks¹. De uitvoeringstijd daarvoor is $$O(n^2)$$ met een strategie die gebruikmaakt van dynamisch programmeren², maar er bestaat ook een sneller algoritme dat het probleem oplost in $$O(n \log n)$$ tijd.