Uitslag Code Challenge uit Java Magazine #2

De eerste Java Magazine Code Challenge heeft tot enthousiaste reacties en inzendingen geleid. Hoog tijd voor een update dus. Om je geheugen even op te frissen: het doel van de challenge was om gegeven een woordenlijst een optimaal alfabet te vinden. Optimaal betekent in dit geval dat het gekozen alfabet er voor zorgt dat een maximaal aantal woorden in de lijst de letters in alfabetisch oplopende volgorde heeft staan.

Één beste oplossing?

Een snelle rekenaar (ok, Google in dit geval) ziet dat het aantal mogelijke alfabetten 26! (faculteit), oftewel een 4 met nog 26 nullen is. Het is duidelijk niet haalbaar om al deze mogelijkheden af te lopen binnen afzienbare tijd. Roy van Rijn, een van de inzenders, deed wel een dappere poging maar moest daar al snel van af zien. We hebben dus te maken met een zoekprobleem waarbij we eigenlijk nooit zeker kunnen weten of we een globaal optimum hebben bereikt. Wel hebben we een relatief eenvoudige manier om de ‘score’ van een alfabet te bepalen. Namelijk, voor ieder woord in de lijst checken of het in alfabetisch volgorde staat. Het totale aantal goede woorden is dan de score van het bijbehorende alfabet. We zullen zien dat er meerdere ‘beste antwoorden’ lijken te zijn.

Hill climbing

Er zijn een aantal tactieken die je kunt toepassen om tot een goed antwoord te komen. Een daarvan is Hill climbing: je begint met een random alfabet en berekent de score. Vervolgens bekijk je alle oplossingen in de ‘omgeving’ van het huidige alfabet. Wat de omgeving is verschilt per probleem. In ons geval kun je bijvoorbeeld kijken naar het wisselen van de positie van twee letters. Vervolgens bereken je de nieuwe scores en kies je de hoogste uit je omgeving. Zodra je geen hogere oplossing in je omgeving vindt, stop je. Een alternatief is toch doorgaan, maar stoppen wanneer de score al x iteraties niet verbetert. Of wanneer je anderszins besluit dat je lang genoeg gewacht hebt.

Voorbeelden van hillclimbing algoritmes kun je vinden in de volgende oplossingen:

Hill climbing is een zogenaamd greedy algorithm. Omdat je alleen maar naar hogere scores toewerkt bestaat er het gevaar dat je in een lokaal optimum terecht komt. Soms moet je door een dal om bij de absolute top te komen. Daarom wordt hill climbing vaak gecombineerd met random restarts: je draait het proces gewoon vaak genoeg met andere willekeurige startpunten om te voorkomen dat je alleen een lokaal maximum vindt. Stefan Boeser verwoordde het mooi in commentaar in zijn oplossing:

> the result depends on the input used – so we try different ones and cross our fingers

Een iets geavanceerdere variant is Simulated Annealing, toegepast door Jos Roseboom [https://github.com/JosRoseboom/AlphaPerm]. HIerbij accepteer je tijdens het ‘doorlopen’ van de oplossingen ook dat je af en toe een stapje terugzet. Op deze manier kun je tijdens het zoeken al via sub-optimale oplossingen bij een betere oplossing uitkomen.

Genetische algoritmes

Een andere mogelijkheid is om het probleem met een genetisch algoritme op te lossen. Hierbij neem je als ‘initiele populatie’ een aantal random alfabetten. De zogenaamde ‘fitness’ functie voor een alfabet is uiteraard de score zoals eerder besproken. Vervolgens ‘evolueert’ deze populatie door random mutaties toe te passen (wederom het verwisselen van een letter) en door veelbelovende alfabetten met elkaar te combineren tot nieuwe kandidaten. Het idee is dat de populatie op deze manier langzaam steeds beter wordt door goede oplossingen te combineren.

De grote vraag is: hoe combineer ik twee kanditaat-alfabetten? Zelf heb ik gekozen voor het in tweeën hakken van de twee kandidaten. Je neemt dan de eerste helft van het eerste alfabet en voegt daar alle letters uit de eerste helft van het tweede alfabet aan toe (uiteraard alleen de letters die nog niet in de eerste helft van het eerste alfabet zaten). Vervolgens voeg je de overgebleven letters uit de tweede helften in die volgorde toe. Marco Tolk [https://github.com/mtolk/alfabetsoep] had een zelfde idee, alleen kiest hij het ‘cross-over’ punt random in plaats van precies op de helft. 

And the winner is…

Uiteraard is er ook een winnaar. Allereerst hebben bijna alle inzendingen alfabetten opgeleverd op het (waarschijnlijk…) globale optimum van 4046 woorden. Niets is zeker, maar met zoveel datapunten kunnen we er redelijkerwijs van uit gaan dat dit het hoogst haalbare is. Omdat de score dus bij bijna iedereen gelijk is, heb ik gekeken naar de elegantste oplossing.

Eerst de eervolle vermelding. Roy van Rijn stuurde als eerste een inzending met 4046 woorden (BCPFJHLOWAQUMXVINTGKZERDYS). Roy wees mij ook op een andere challenge met de naam ‘Alphabet city’ van AI Zimmerman op http://azspcs.net/. Dus mocht je er nog geen genoeg van hebben, kun je daar je lol nog op.

Verder stuurde Bert Jan Schrijver een lijst met 3840 verschillende alfabetten op, die allemaal 4046 goede worden opleveren. Grondig! Zijn oplossing maakt ook gebruik van veel nieuwe Java 8 features en is zeker de moeite waard om te bekijken.

De winnaar van deze challenge is Jos Roseboom. Zijn analyse van het probleem en de beschrijving van de oplossing op basis van Simulated Annealing was zeer grondig. Jos, de Raspberry Pi komt jouw kant op!

See you next time?

Al met al kunnen we spreken van een succesvolle eerste ronde van de Java Magazine Coding Challenge. Hopelijk kunnen we volgende editie rekenen op nog meer inzendingen. Ik heb in ieder geval een hoop geleerd van het spelen met dit probleem en het zien van de verschillende oplossingen naast elkaar.

Alle oplossingen op een rij:

Bert Jan Schrijver [https://github.com/bertjan/codechallenge-javmag201402]

Stefan Boeser [http://github.com/boess/alfabetsoep]

Roy van Rijn [https://github.com/royvanrijn/alfabetsoep]

Marco Tolk [https://github.com/mtolk/alfabetsoep]

Sander Kooijmans [https://github.com/gogognome/alphabet]

Jos Roseboom [https://github.com/JosRoseboom/AlphaPerm]

Sjaak de Mul [https://github.com/sdemul/BestAlphabetFinder]