Floris' Blog

One of my pastimes is solving programming puzzles. I recently wrote an article for the newsletter of my employer. It is intended to interest our developers for these kinds of puzzles and to provide them with a different perspective to look at problems. The material is really introductionary. Text is in Dutch:

Een van mijn (vele) hobbies is het oplossen van programmeerpuzzels. Zo af en toe doe ik dit tijdens een ‘officiele’ wedstrijd, zoals BAPC of Masters of Java, maar over het algemeen probeer ik m’n vaardigheden bij te houden of te verbeteren met sites als topcoder.com en spoj.pl.

Ieder van de genoemde competities kent z’n eigen wedstrijdvorm en bijbehorende uitdagingen. BAPC geeft je aan het begin van de dag een stapel (lastige) opgaven en een aantal uur om met een team van drie personen zo veel mogelijk opgaven op te lossen. In Masters of Java krijg je telkens een half uur om een opgave op te lossen die je kennis van de Java API test. Bij Topcoder (in de algorithm matches) krijg je een uur de tijd voor drie opgaves op drie verschillende moeilijkheidsniveaus (en de opgaves blijven beschikbaar in zogenaamde practice rooms, waar je onbeperkt de tijd krijgt om te oefenen). Spoj uiteindelijk verzamelt opgaves van BAPC-achtige wedstrijden en opgaves die mensen zelf maken. Er is geen limiet op de tijd die je neemt om een oplossing te schrijven, maar wel op de tijd die je oplossing krijgt om te werken op de (onbekende) invoer. Het uitgebreide archief, de rankings en beschikbaarheid op elk moment van de dag maakt Spoj tot m’n huidige favoriet.
In deze serie van artikelen zal ik aan de hand van puzzels die beschikbaar zijn op Spoj uitleg geven over verschillende algoritmes en manieren om te werk te gaan bij het oplossen van dergelijke problemen.

Deze keer zullen we kijken naar een onderwerp dat in de praktijk weinig zichtbaar wordt gebruikt¹ maar des te vaker in puzzels te vinden is: priemgetallen. Priemgetallen, getallen die alleen deelbaar zijn door één of zichzelf, zijn een favoriet onderwerp van veel puzzels. In veel gevallen gaat het erom de getallen zo efficiënt mogelijk te genereren, als doel of als tussenstap.

De meest naïeve manier van priemgetallen genereren is voor ieder getal te proberen of het deelbaar is door een getal tussen één en het getal zelf. Het aantal delingen dat je daartoe moet uitvoeren neemt snel toe, en wanneer je bedenkt dat delen niet de snelste operatie is die je computer uit kan voeren, zal duidelijk zijn dat dit alleen bruikbaar is voor kleine getallen.

Een eerste optimalisatie valt te bereiken wanneer je ziet dat je bijvoorbeeld niet verder hoeft te testen voorbij de helft van het gezochte getal: daarboven valt de waarde van de deling tussen één en twee. Je blijkt uiteindelijk niet verder te hoeven gaan dan voorbij de wortel van het te testen getal. Dit komt omdat een groter getal dat een valide deling op zou leveren uitkomt op een getal dat kleiner is dan de wortel, en dus al getest is!

Een volgende stap is het overslaan van alle even getallen boven de twee: iedere succesvolle deling door een even getal had al lang afgevangen geworden door de deling door twee. Dit geldt echter ook voor alle veelvouden van drie, en van vijf, en …. van ieder priemgetal: je hoeft om te bepalen of iets een priemgetal is dus alleen delingen uit te voeren door voorgaande priemgetallen (tot de wortel van het getal).

Indien je alle priemgetallen tot een bepaalde grens wil bepalen en het aantal getallen valt binnen geheugen limieten, dan is er ook nog de zeef van Eratosthenes: je maakt een array van booleans en geeft deze allemaal dezelfde waarde. Hierna loop je vanaf element twee omhoog: als een element de default waarde heeft heb je een priemgetal, en je markeert alle elementen op posities die een veelvoud van het priemgetal zijn met een andere waarde.

Voor wedstrijden of puzzels is het vaak van belang goed te kijken of je van een enkel getal moet bepalen of het priem is, of dat het er vele zijn. In het eerste geval is het meestal efficienter alleen het getal te testen, maar wanneer je veel priemgetallen moet testen is het de moeite waard om een tabel te genereren met priemgetallen en een lookup in de tabel te doen.

Wanneer de bovengrens van de priemgetallen voorbij de grens van het geheugen begint te komen zijn er nog wel een paar verbeteringen: je kunt de even getallen weglaten en hiervoor eenvoudig compenseren bij het lezen en schrijven naar de array. Voor veelvouden van drie is dat ook nog wel te doen, maar levert al iets meer problemen op. Verder zijn boolean waarden natuurlijk geheugen-inefficient en kun je beter individuele bits manipuleren.

Voor erg grote getallen is het maken van tabellen (of het testen door deling door andere priemgetallen) niet realisch. In de praktijk zul je hier weinig puzzels mee tegenkomen, maar het is zeker interessante materie om eens op te zoeken. Zoek daarvoor naar ‘Fermat primality test’, ‘Miller-Rabin primality test’ en ‘AKS primality test’.

Om eens te spelen met priemgetallen kun je volgende puzzels op Spoj proberen:
2. Prime Generator – eenvoudig
288. Prime or Not – grote getallen (maar niet veel), met een beperking op de mogelijke talen.
3505. Prime Number theorem – Niet heel lastig, maar nog vrij veel mensen bijten zich er op stuk.
3587. Prime Again – Door de vraagstelling, grote getallen en het aantal testcases een uitdaging.
1841. Prime Path - combineert priemgetallen met shortest path, maar daarover meer in een ander artikel.

¹ Weinig zichtbaar wil niet zeggen dat het niet wordt gebruikt: priemgetallen zijn vaak een basis voor cryptografie, hashfuncties, etc.

References:
Topcoder.com
Spoj.pl

Last week I gave a talk at a technology evening organized by my employer. The subject of the evening was ‘How hot is RIA’, presenting a generic talk on what Rich Internet Applications are, a talk on Silverlight 2.0 and my talk on JavaFX.
Despite the limited time slot (half an hour) I think the basics were pretty much covered. I touched on the platform, language and workflow proposition, and gave a demo of using the Photoshop plugin to export material to Netbeans and animate it.
Based on the reactions I’d say the talk was well received!

References:
The presentation sheets.
JavaFX.com - the primary source of JavaFX information.
JFXtras - A very useful library when building JavaFX applications.
TweetBox - The project by Mark Nankman, who I had talk with after the presentation.