page header photo

april 2017 Archieven

Robinsonizing in C++


Geplaatst door bob op 2017-04-13 13:03:13 | Permanente link | Categorie: Programmeren | Reacties: 0

Wat is er nu leuker dan een blog van AT Computing aan te vangen met een zin die precies dertien a's, drie b's, vijf c's, negen d's, vijfenveertig e's, acht f's, elf g's, drie h's, zesentwintig i's, vijf j's, twee k's, zes l's, drie m's, zevenentwintig n's, drie o's, drie p's, twaalf r's, achtentwintig s's, tweeentwintig t's, vier u's, elf v's, negen w's en vijf z's bevat?

Als je dit zou nagaan, door inderdaad alle letters zorgvuldig te tellen, kom je er achter (wellicht tot je verbijstering) dat het precies klopt. De rest van dit verhaal gaat over hoe je zo'n zin kunt construeren. Dus:

Hoe kun je nou toch een zin construeren die van zichzelf vertelt dat er precies zeven a's, zeven c's, vier d's, achtenveertig e's, zes f's, zes g's, zes h's, eenentwintig i's, vier j's, twee k's, vijf l's, zevenentwintig n's, vijf o's, twee p's, elf r's, achtentwintig s's, eenentwintig t's, vier u's, dertien v's, zeven w's en elf z's in staan?

Immers, als je dit zelf op een kladblaadje probeert kom je er snel achter dat wanneer je één telwoord verandert, er meteen een paar andere niet meer kloppen. En als je die probeert te verbeteren veranderen de aantallen van een boel letters opnieuw. Het grijpt allemaal in elkaar!

De strategie om een kloppende zin te krijgen is wonderlijk. Het idee is als volgt. Je construeert een zin waarin je willekeurig gekozen telwoorden invult, voor elke letter van het alfabet. Die zin is dan weliswaar correct Nederlands, maar inhoudelijk staat er onzin (omdat de aantallen niet kloppen). Deze zin is je uitgangspunt; laten we hem 'the seed' noemen, het zaadje.

Je gaat nu zorgvuldig de letters turven die in deze 'seed' staan. Dat levert je een reeks aantallen op, voor de meeste letters van het alfabet. Je construeert nu opnieuw een zin, maar nu met uitgeschreven telwoorden voor de werkelijk geturfde aantallen. Ook voor deze zin geldt waarschijnlijk dat hij inhoudelijk nog niet klopt, maar de aantallen zijn nu een stuk realistischer.

Dit proces herhaal je. Dus: letters tellen, en opnieuw een zin construeren met de zojuist geconstateerde aantallen.

Hoe kun je nu controleren of een zo geconstureerde zin werkelijk klopt? Eenvoudig: wanneer je de letters weer gaat turven, en je komt op dezelfde aantallen uit als de laatste keer, dan "spreekt de zin de waarheid"!

Je zou deze strategie eenvoudig tot een computerprogramma kunnen omvormen dat al het telwerk en zinnen construeren voor je doet. Maar stop! Niet zo snel. Je vindt lang niet altijd een oplossing! Het komt vaak voor dat je in cirkels blijft lopen, m.a.w. op aantallen komt die je een paar rondes terug al had. Het spreekt voor zich dat je er dan nooit uitkomt. Een computerprogramma moet dus een veiligheidsventiel krijgen, in de vorm van een maximaal aantal pogingen dat we gaan doen voor we besluiten te stoppen. Als we op die manier een reeks pogingen afbreken beginnen we opnieuw met een reeks willekeurig gekozen waarden: een nieuwe seed.

Op basis van deze aanpak heb ik in het verleden diverse implementaties gebouwd. Mijn eerste poging was in 1987 met een BASIC programma op een Tandy TRS-80, een computer met een 1.7 MHz Z80 CPU. Deze implementatie was in staat om 85 zinnen per minuut te analyseren.

Fast-forward naar het heden. Ik heb een C++-implementatie op mijn laptop gebouwd, die ongeveer 4 miljoen pogingen per seconde haalt. We zijn in die dertig jaar dus wel iets vooruit gegaan qua snelheid.

Met behulp van zo'n programma is het interessant om te onderzoeken wat de beste instellingen zijn om gemiddeld genomen zo snel mogelijk kloppende resultaten te krijgen. Een belangrijke parameter is de waarde die ik net al beschreef: na hoeveel pogingen besluit je dat het genoeg is, en dat je opnieuw moet beginnen met een reeks willekeurige telwoorden?

De praktijk heeft uitgewezen uit dat het loont dit getal verrassend klein te houden, bijvoorbeeld tien. Zo klein? Ja, als je na tien pogingen nog geen kloppende zin hebt gevonden, begin dan maar opnieuw. Het is beter om heel vaak vanuit verschillende kanten naar een oplossing toe proberen te werken, in plaats van lang door te blijven ploeteren vanuit een bepaald startpunt. Heb je eenmaal een startwaarde die tot een juiste oplossing zal leiden, dan ben je daar meestal in slechts een paar stappen.

Tenslotte: de strategie die we hier volgen heet Robinsonizing, naar de persoon die dit voor het eerst bedacht. Zinnen waarin alle letters van het alfabet voorkomen heten Pangrams. Deze term kom je ook tegen als je gaat zoeken naar meer informatie over dit soort zelfreferente zinnen. Maar bedenk dat de zinnen die ik hier heb laten zien niet persé alle letters van het alfabet opsommen, en zodoende dus geen zuivere pangrams zijn. Een bekende (Engelse) pangram is bijvoorbeeld: "The quick brown fox jumped over the lazy dog". De kortste Nederlandse die ik ken is: "Doch Bep, vrij sexy qua vorm, zwijgt". Strafpunten voor de eigennaam, natuurlijk, maar toch slechts 28 letters!

Dit is wel een echte pangram en bevat precies acht a's, twee b's, zeven c's, zes d's, eenenvijftig e's, drie f's, vijf g's, zes h's, zeventien i's, drie j's, een k, twee l's, twee m's, drieentwintig n's, een o, drie p's, een q, zeven r's, zesentwintig s's, achttien t's, een u, acht v's, zeven w's, een x, een y en acht z's.

Okee, en dan nu de challenge: wie bouwt een programma dat de snelheid van mijn C++-implementatie overtreft? Mijn laptop heeft een Quad Core 2.3 GHz i5 processor aan boord, dus we moeten wel normaliseren naar die snelheid. Ik gebruik bovendien maar één processorkern. Ik wil mijn implementatie ook best testen op jouw 4 GHz Xeon of zo, om de getallen vergelijkbaar te houden. :-)