Kies uit een standaard kaartspel evenveel zwarte als rode kaarten (je mag ook het volledige kaartspel nemen), en maak daarmee een stapel waarbij de kaarten afwisselend rood en zwart zijn. Het maakt niet uit of de bovenste kaart zwart of rood is. Splits nu de stapel kaarten in twee kleinere stapels die ongeveer even hoog zijn, maar zorg ervoor dat de onderste kaart van de ene stapel zwart is en de onderste kaart van de andere rood. Dit kan alleen als de twee stapels een oneven aantal kaarten bevatten, waardoor meteen ook de bovenste en de onderste kaart van elke stapel een andere fysieke kleur moeten hebben.
Til de twee kleinere stapels met de duimen omhoog en laat de kaarten willekeurig op elkaar vallen: eerst een paar kaarten van de eerste stapel, dan een paar kaarten van de tweede stapel, dan weer een paar kaarten van de eerste stapel, …, totdat alle kaarten van de twee stapels in elkaar gevallen zijn. Schuif nu alle kaarten samen tot een nieuwe stapel. Deze manier om de kaarten te schudden wordt de zwaluwstaartmethode1 (Engels: riffle-shuffle) genoemd. Neem nu telkens twee kaarten van de bovenkant van de nieuwe stapel. Hoeveel van die paren zullen er een verschillende fysieke kleur hebben (één zwarte kaart en één rode kaart)?
Verrassend genoeg zullen alle paren een verschillende fysieke kleur hebben. Veronderstel bijvoorbeeld dat er eerst een zwarte kaart valt. Dan moet die ofwel gevolgd worden door de volgende kaart van dezelfde stapel (die een rode kleur heeft) of de eerste kaart van de andere stapel (die ook een rode kleur heeft). Hoe dan ook zal het eerste paar bestaan uit één zwarte en één rode kaart. Als we dezelfde redenering doortrekken, dan zal dat ook gelden voor alle andere paren opeenvolgende kaarten in de stapel die we na het schudden bekomen hebben. Dit fenomeen werd voor het eerst ontdekt in 1958 door de goochelaar Norman Gilbreath.
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 beschrijven elk van de 52 kaarten van een standaard kaartspel met een string 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.
We stellen een stapel kaarten voor als reeks beschrijvingen van de kaarten uit de stapel, waarbij elk beschrijving op een afzonderlijke regel staat. De eerste regel bevat de beschrijving van de bovenste kaart van de stapel. Een stapel hoeft niet noodzakelijk alle 52 kaarten van een kaartspel te bevatten.
Bij de zwaluwstaartmethode vallen alle kaarten van een stapel in groepen van een aantal opeenvolgende kaarten. We stellen zo een gegroepeerde stapel voor als een tekstbestand dat de stapel kaarten bevat. Tussen elke twee groepen kaarten staat er telkens een lege regel. Zo stelt het tekstbestand
AD 9C KD 10C QH
een gegroepeerde stapel voor waarvan de kaarten gegroepeerd zijn in drie groepen van respectievelijk 2, 1 en 2 kaarten.
De zwaluwstaartmethode werkt dan met twee gegroepeerde stapels, die niet noodzakelijk evenveel groepen moeten hebben en waarvan de verdeling van de kaarten over de groepen niet noodzakelijk moet overeenstemmen. Het resultaat van de zwaluwstaartmethode is een nieuwe stapel die gevormd wordt door de kaarten van de eerste groep van de eerste stapel, gevolgd door de kaarten van de eerste groep van de tweede stapel, gevolgd door de kaarten van de tweede groep van de eerste stapel, gevolgd door de kaarten van de tweede groep van de tweede stapel, … Als alle groepen van één van de stapels opgebruikt zijn, dan volgen daarna nog de kaarten uit de overige groepen van de andere stapel (als die er zijn).
Gevraagd wordt om een bash shell script dovetail te schrijven waaraan twee argumenten moeten doorgegeven worden die de bestandslocaties van twee gegroepeerde stapels aangeven. De nieuwe stapel die bekomen wordt door de zwaluwstaartmethode toe te passen op de twee gegeven stapels moet door het shell script uitgeschreven worden naar standard output. Bovendien moet het shell script ook de volgende vier opties ondersteunen:
-
optie -s: indien deze optie gebruikt wordt, dan moet de omschrijving van elke kaart bij het uitschrijven van de stapel voorafgegaan worden door het nummer van de stapel waaruit de kaart komt: 1 voor de eerste stapel en 2 voor de tweede stapel; tussen dat nummer en de omschrijving van de kaart moet een dubbelpunt (:) staan
-
optie -k: indien deze optie gebruikt wordt, dan moet de omschrijving van elke kaart bij het uitschrijven van de stapel gevolgd worden door een dubbelpunt (:) en een omschrijving van de fysieke kleur van de kaart
-
optie -r: met deze optie moet verplicht een argument doorgegeven worden; dit argument bevat de omschrijving van de fysieke kleur rood die moet uitgeschreven worden als de optie -k gebruikt wordt (standaardwaarde zonder optie -r: red)
-
optie -b: met deze optie moet verplicht een argument doorgegeven worden; dit argument bevat de omschrijving van de fysieke kleur zwart die moet uitgeschreven worden als de optie -b gebruikt wordt (standaardwaarde zonder optie -b: black)
Het shell script moet de volgende foutafhandeling voorzien:
-
indien het shell script niet de gepaste opties meekrijgt (enkel ondersteuning voor de opties -s, -k, -r en -b waarbij de laatste twee met een verplicht argument) dan moet een gepaste boodschap (zie onderstaande voorbeeldsessie) uitgeschreven worden naar standard error en moet het shell script eindigen met exit status 1
-
het shell script mag ervan uitgaan dat er twee argumenten aan het shell script doorgegeven worden, die bestandslocaties van twee gegroepeerde stapels aangeven; het shell script hoeft dit niet expliciet te controleren
Voorbeeld
Onderstaande voorbeeldsessie geeft aan hoe het shell script dovetail moet kunnen gebruikt worden. Hierbij gaan we ervan uit dat de tekstbestanden stack1.txt2, stack2.txt3 en stack3.txt4 zich in de huidige directory bevinden.
$ paste stack1.txt5 stack2.txt6 stack3.txt7 7C AD AD 9C 2D 9C JC KD KD 7H 10C KD 10S QH 10C QH JS $ dovetail stack1.txt8 stack2.txt9 7C AD 9C 2D JC 7H KD 10S 10C QH $ dovetail -s stack1.txt10 stack2.txt11 1:7C 2:AD 2:9C 1:2D 1:JC 1:7H 2:KD 1:10S 2:10C 2:QH $ dovetail -k stack1.txt12 stack2.txt13 7C:black AD:red 9C:black 2D:red JC:black 7H:red KD:red 10S:black 10C:black QH:red $ dovetail -ks stack1.txt14 stack2.txt15 1:7C:black 2:AD:red 2:9C:black 1:2D:red 1:JC:black 1:7H:red 2:KD:red 1:10S:black 2:10C:black 2:QH:red $ dovetail -ks -r rood -b zwart stack1.txt16 stack2.txt17 1:7C:zwart 2:AD:rood 2:9C:zwart 1:2D:rood 1:JC:zwart 1:7H:rood 2:KD:rood 1:10S:zwart 2:10C:zwart 2:QH:rood $ dovetail -ks -r red -z black stack1.txt18 stack2.txt19 Usage: dovetail [-ks] [-r COLOR] [-b COLOR] FILE FILE $ echo $? 1 $ dovetail -ks stack1.txt20 stack3.txt21 1:7C:black 2:AD:red 1:2D:red 1:JC:black 1:7H:red 2:9C:black 2:KD:rood 1:10S:black 2:KD:red 2:10C:black 2:QH:red 2:JS:black
Bronnen
-
Gardner M (August 1960). Mathematical Recreation column. Scientific American.
-
Gardner M (1966). New Mathematical Diversions from Scientific American.
-
Gilbreath N (1958). Magnetic colors. The Linking Ring 38(5), 60.