Geacht Franckenlid, Geachte lezer van deze blog,

Inleiding - LEES DIT EERST!

Als je daar blij van wordt, probeer dan eerst de onderstaande opgave zelf op te lossen. In dit artikel leg ik uit welke strategie je bij een Crash and Compile zou kunnen toepassen om dit probleem op te lossen. Dit doe ik door deze opgave stap voor stap te ontleden en uiteindelijk mijn code voor de oplossing te presenteren. Mogelijk kan dat op een betere manier, maar dit is voor het eerst dat ik een dergelijke verhandeling schrijf.

De laatste opgave van de afgelopen Crash and Compile was de volgende:

---

#6 BLACK HAT KLAVERJASSEN (c) 2013 plus & sven:

You have a deck of 32 cards for a game of klaverjas and managed to place the four aces on top. Being able to execute perfect cuts and shuffles, you set out to construct a system that allows you to deal all aces back to your own team.

Starting and ending with a perfect cut in the middle of the deck you execute 1-11 of the shuffles described below.

riffle shuffle - 1 2 3 4 5 6 -> 1 4 2 5 3 6
monge shuffle  - 1 2 3 4 5 6 -> 6 4 2 1 3 5
snake shuffle  - 1 2 3 4 5 6 -> 3 2 1 6 5 4
peel shuffle   - 1 2 3 4 5 6 -> 3 4 2 5 1 6

What fraction of these shuffles will result in all aces being dealt to your team?

---

[SPOILERS]

Ok, dit is Crash and Compile dus laten we eerst de complexiteit van dit probleem aanschouwen:

'cut (shuffle shuffle shuffle ... ) cut' -> Heb ik alle azen?

Er zijn in totaal som(4^n,n,1,11)=5592404 van deze permutaties die we moeten checken. Overwegende dat dit te parralelliseren is en 5,6 miljoen in dit opzicht niet zo heel erg veel is, zal er geen hogere wiskunde of een directe functie beschikbaar zijn om tot het antwoord te komen zullen we vooral CPU en geheugen efficiënt moeten programmeren en waakzaam zijn voor typefouten in de shuffles.

We staan nu voor drie sub-problemen die we moeten gaan oplossen:

1. Hoe gaan we alle shuffles maken? (Zowel datastructuur als methode)
2. Hoe gaan we over alle shuffles itereren?
3. Hoe checken we of een shuffle het gewenste resultaat, van alle azen in je team, oplevert.

Ik zal nu beschrijven hoe ik dit probleem heb aangepakt maar wil eerst even aandacht besteden aan een interessante manier die sommige teams tijdens de Crash and Compile hebben aangewend voor sub-probleem twee.

Ingegeven door de een van de challenges werd er namelijk gekozen om dit probleem met de Monte-Carlo methode aan te pakken. Als je met de juiste wegingsfactor voor de lengte van de shuffles de permutaties voor deze shuffles uniform verdeeld laat zijn, zul je in de limiet de gevraagde ratio benaderen. Omdat we echter nog niet weten of er überhaupt succesvolle permutaties zijn, laat staan wat de fractie is, zou kunnen voorkomen voor hele hoge of hele lage fracties de convergentie van deze methode te traag is. Er is verder niets tegen op deze strategie maar mede wegens het feit dat 5,6 miljoen permutaties nog wel te doen is, heb ik er zelf voor gekozen om het volledige spectrum te analyseren.

1. Hoe gaan we deze shuffles maken?

We kennen de beginpositie van de azen, willen een tussentoestand kunnen bijhouden en uiteindelijk kunnen uitlezen of de aas onderdeel is van de kaarten die naar ons team gedeeld zijn. Er zijn hier twee strategieën: het bijhouden van de positie van elk van de azen en het bijhouden van de permutatie van het volledige deck. Afhankelijk waar je talent in programmeren zit, kies je nu een van deze strategieën.

Als je met Matlab werkt zul je waarschijnlijk de positie van de azen opslaan in een vector en voor de shuffles permutatiematrices gebruiken. Deze strategie zou ook kunnen werken in andere geïnterpreteerde talen zoals python, maar je zult meer moeite hebben om zonder de matrix-vector producten de permutaties van de tussentoestanden te genereren. Veel voordehandliggender in deze talen zou het schrijven van een stel functies die voor elke shuffle voor elke originele positie precies aangeeft waar de kaart terecht gaat komen. Afhankelijk van hoeveel moeite het kost om zoiets uit te rekenen kunnen we natuurlijk ook een tabel maken waarin voor alle beginposities staat omschreven waar ze terecht zullen komen.

Dit waren de opties die wij serieus zouden hebben overwogen voor de Crash and Compile. De compactste versie die ik werkend heb gekregen is gebaseerd op de opzoektabellen.

Er is namelijk nog een methode voor de echte die-hards. Toen ik Sven dit idee gaf heeft hij het daadwerkelijk uitgewerkt; dus die credits liggen daar. De uitdaging is de volgende: een int heeft 32 bits en ik zou de positie van de azen kunnen aangeven door de bit die correspondeert met de positie van de aas op 1 te zetten en de rest 0 te laten. Zou jij alle shuffles kunnen programmeren terwijl je alleen maar gebruik maakt van bitwise-operators?

Enfin. Mijn lookup table vindt je in de code waarbij de array shuffles[0] cuts bevat,shuffles[1] de riffle shuffle, shuffles[2] de monge shuffle, shuffles[3] de snake shuffle en tot slot shuffles[4] de peel shuffle. Tijdens de competitie had ik deze waarschijnlijk met de hand uitgetypt. Omdat ik niet onder tijdsdruk stond heb ik in eerste instantie functies geschreven waardoor ik voor deze code de tabellen kon genereren. De overweging hierbij lijkt vooral te zijn hoe goed je nog in staat bent tot 32 te tellen.

2. Hoe gaan we over alle shuffles itereren?

Een eerste gedachte? 'Met heel veel geneste for-lussen?' Dit is mogelijk maar het werken met 11 variabelen in een bijna onmogelijk diepe for-lus is bijzonder vervelend en typefoutgevoelig. (En dan ook nog een keer met 10,9,..!) Ok, laten we dan maar een andere strategie hanteren: 'recursie'. Recursieve functies zijn functies die de mogelijkheid hebben zichzelf aan te roepen. Wat in het onderstaande programma gebeurt, is dat iedere keer dat de recursion functie word aangeroepen de functie uitgebreid wordt met alle verschillende shuffles totdat ze voldoende lang zijn. Indien ze die lengte - in het langste geval 11 maal - hebben bereikt controleren we na een cut of ze 'succesvol' zijn.

3. Hoe checken we of een shuffle het gewenste resultaat, van alle azen in je team, oplevert.

Ik presenteer hier een drietal manieren om te controleren die gebaseerd zijn op de functies of opzoektabellen in de volgorde zoals ze bij mijn pogingen zijn opgekomen. Efficiënte keuzes hierin zullen hooguit een paar seconden van je rekentijd afhalen. Voor de vector of bitwise methode zal je code iets anders moeten werken maar de gedachtegang blijft analoog.

Eerst dacht ik erover om alle correcte permutaties van de 4 cijfers te genereren op basis van een lijst met posities van de kaarten zoals ze naar jouw team gedeeld worden. Hier is echter een tabel van 4*16*15*14*13=174720 plekken nodig. Dus dat is gewoon absurd.

Veel efficiënter is om te kijken of voor elke vier van de posities van de azen, deze positie voorkomt in de lijst met posities van kaarten die naar je eigen team gedeeld zijn. Dat is op zich een slimme methode maar het kost je een functie-aanroep, gemiddeld 12 vergelijkingen en het bepalen van een returnwaarde.

Nog efficiënter was om wederom een opzoektabel te maken voor alle uiteindelijke posities die te vinden is als team in mijn code.

Tot slot

De code: http://codepad.org/PjQECzv0

Ondanks het feit dat de leesbaarheid iets minder wordt, heb ik besloten deze versie van 6 regels code te plaatsen omdat ik de compactheid awesome vind. Dank hiervoor aan Sven die 3 regels heeft helpen uitsparen.

Mocht je een verbetering hebben voor dit verhaal of een goede methode die ik ben vergeten te behandelen, schroom dan niet om mij te contacteren. Dit geldt ook als je op zoek bent naar iemand die je leert om (beter) te programmeren of iemand zoekt om voor een academische deadline aan extreme programming te doen. Spreek me aan als ik je tegen kom op de gang in de Universiteit of stuur een mail naar het Francken-bestuur.