Uitslag Code Challenge Priemslang

Voordat we gaan kijken naar de oplossingen die jullie ingezonden hebben voor de Priemslang code challenge eerst een rectificatie. Deze challenge komt namelijk grotendeels uit de koker van Roy van Rijn (ook bekend als deelnemer van vorige challenges!). Helaas is zijn auteurschap in Java Magazine niet vermeld. Goed, nu we dat uit de weg hebben: waar ging het ook alweer over? Als opfrisser hier de samenvatting van de challenge.

"Je opdracht is om een slang te maken die in totaal 5000 stappen lang is, met als doel dat deze in een zo klein mogelijk vierkant past. Een slang van 5000 stappen lang zal in totaal 669 bochten maken. Zoveel priemgetallen zitten er onder de 5000. Voor elk van deze bochten moet je links of rechts kiezen. De eerste bocht is bij een lengte van 2, dan meteen bij een lengte van 3, en zo verder tot de laatste bocht wanneer de slang een lengte heeft van 4999."

Het uiteindelijke resultaat is dus een string met 669 keer L of R. De resulterende slang moet in een zo'n klein mogelijke rechthoek passen. Er zijn vier inzendingen binnengekomen van:

Helaas heeft Frans geen oplossing van de gewenste lengte kunnen vinden. Dat betekent dat er drie kanshebbers over blijven.

Het is leuk om te zien dat er weer verschillende aanpakken zijn gekozen. Uiteraard speelt randomness een grote rol, gezien de enorme oplossingsruimte van deze puzzel. Want alle deelnemers zijn er achtergekomen dat 2^669 mogelijke oplossingen een astronomisch aantal is. De vraag is dus: hoe vinden we in die hooiberg een geldige, kleine oplossing?

Sander gebruikt hiervoor simulated annealing. Dit is een iets geavanceerde variant van een hill-climbing algoritme, waarbij je af en toe ook genoegen neemt met een teruggang in de kwaliteit van je oplossing om aan lokale minima te ontsnappen. Soms begin je zelfs helemaal opnieuw. Ondertussen hou je dan de beste oplossing tot nu toe bij. Stefan kiest voor een evolutionair algoritme om relatief snel tot een goede oplossing te komen. Hier was een J-Fall sessie de inspiratie voor.

Peter heeft voor een iets andere aanpak gekozen, zonder gebruik te maken van randomisering. Zijn oplossing ziet het probleem echt als een (hele grote) zoekboom waar het juist pad in gevonden moet worden. Eigenlijk zou hij het liefst alle paden bewandelen. In zijn stats.txt is een uitgebreid overzicht te zien hoe verschillende traversal-strategieën het doen. Spoiler alert: niet al te best… Om praktische redenen heeft hij dus heuristieken moet verzinnen. Een succesvolle heuristiek blijkt de verhouding tussen de slanglengte en de oppervlakte te zijn. Peter's oplossing beschouwt alleen antwoorden waarbij die verhouding tussen de 8 en 9 ligt, wat in zeer korte tijd tot een heel acceptabele oplossing leidt.

Maar de grote vraag is natuurlijk: wie heeft de slang met de kleinste 'bounding box'? De ranglijst is als volgt:

  1. Stefan Boeser (176)
  2. Peter Doornbosch (188)
  3. Sander Kooijmans (206)
  4. Frans van den Berg (geen oplossing met 669 stappen)

De oplossing van Stefan ziet er als volgt uit:

Zoals in eerdere challenges ook al gebleken is kun je met een evolutionair algoritme hoge ogen gooien. Stefan, van harte gefeliciteerd met je overwinning! Leuk om te zien dat de kennis van J-Fall direct tot een overwinning leidt.

Voor de volledigheid hier nog de ingestuurde oplossingen:

Oplossing Stefan Boeser (176):

LRRRLLRLLRRLLRRRLRRLLRLLLRRLLRLLRRLLRRLLLRRLLRLLRRLRLLLRRLRLLRRLRRLLRLRRRLLRRLLRRLRRLLRRLLRRLLRLLRLLRRLLRLLRLRRRLLLRRLLRRRLLLRRLLLRRLLRRLLRRLRRLLLRLLRRLLRLRRRRLLRLRRLLRRLLRRRLRLLLRRRLRRLLLRLRRLLLRLLRRLLRRLLLRRLRLRRRLRLRRLRLRLRLLLRRRRRLRLLLRLRRRLLLRRLRLLLRRLRRLRLLLRLRLLRLRRLRLRLLRRLLRRRLRLLLLRRRLLLRRLLRRLLRRLLRRLLRLRRLLLRRLRRRLRLLLLRRRLLRLLRRLLRRLLRRLRLLLRRRLRLLRLLRRRRLLRRLRLLRRLRRRRLLLRLLRLRLRRLLRLRRLLRRLLRRRLRLLLRRLLRRLRRLLRRLRLLRRLLRLRRRLLLLRRRLRLLLRRRLRRLLLRRLRRLRLLRRLRLLRRLLRLRRLLLRRLLRLLRRRRLRLRRLLRRLLLRRRLRLRLLLRRRLLRRLLLRRRLLRLRRRLLRLLRRRLLRRLRLLRLRLRRLLRLLLRRRRLRRLLRLLRLRRLRLLLRRRLRRLRLLLLRRRLRRLLRLRRRLLLRRLLLLRRLLLRRRLLRLRRLLRRLLRRLLLRRLLLRRLRRLRLRLLRL

Oplossing Peter Doornbosch (188):

RRLLLRRLLLRLLRLRRLRRLRLRRLRLLRRRLLRRLRLRLRRLRLRRLLRRLRRLLRLRRLLRRLRLRRLRRLLRLRLRRLRLLRLLLRRRRLRRLLRLRRLRLRLRRLRLRLLRRLRLLRRLRLRLRRLRLRLRLRRRRLLRLLLRLRLRLLRRLRRRLLLRLRRLRRLLRRLRLRLLRRLRLLRRLRRLLRRLLRRLRLLRRLLRLRLRRLRLLRRLRRLRRLLLRLRLRRLRLRLRLLRRLRLRRLLRLLRLLRRLRLLRRLRRRLLLRLRRRLLRLRRRRLRLLLRLLRRLLRRLRRLRLLRLLRRLRRLLRRLLRRLLRLRRRLLRLRLRLRLRLRRLLRRLRLLRRLRLLLRLRRLLRLLRRRLRLLRRRLRRLLLRRLRLRRLLRRLLRRLLRRLLRLRRLRLRLLRLRRLRLRLLRLLRRLRRRLLRRLLRRLRLLRLRRLRLRLRLRRRLLLRLLLRLRRLLRRLLRRLLRRRLRLLRRRLLRLRLRRLLRRLRRLLLRLRRRLRLLLRRLLRRLRRLLRRLRLLLRRLRRRLLLRLRLRRRLLRLLRLLLRRLLRRRLLRLLLRRRLRLRLRRLRLLLRLLRLRRLLRLRRLLRRLLRLRRRLLRLRLLRRLLLLRRLLLRRRLLLRRRRLRLLRRRLLLRLRRRLLLRRLLRRLRRR

Oplossing Sander Kooijmans (206):

RRLLLRLLRLLRLRLRLLRLRLLRRRLRLLRRLRRLRLRLRLRRLLLLRRLLRRLLRLLLRRLRRLRLRRLLRLLRRRLRRLLRRRLLLRLRRLRLLRRLLRRRLLRLLRLRRLRRLRLRLLRRRLRRLLRLLRLRLLRLLRLRRLLRRLRRLRRLLRRLRLLLRRLLLRRLLRLRRLRRLLRLLRRRLLLRLRLRRLRRRLLLRRRLLRLRLLLRRRLLRRRLRLRLLLRLRRLLRRRLLRRLLRRLRRLLRLRRLRLRRRLLRLLRLRLLRLRRLLLRLRLLRLRLRRLRRLLRRLLRRLLRRRLLRLRLLRLLRLRRLRLRLRRLLRLLRRRRLLRLRRLLRLRLRRRLRLLRRLRLRLRLLRLLRLLRLRRLLRRRLRRLLRLLRLRLRRLRLRRLRLRLRLRRLLRLRRRLLLLRRLLRLRLRRRLRLLLRLLRRRLLLRRRLRLLRLLRLRLRLLRRLLLRRLRLRLRRLRRLLRRRLRLLRRRLLRLLRLRRLRLLRLRRLLRLLLRLRRLLRRLRLRLRLLRLRLRRLLRRRLRLLRRLRRRLLRLRLLLRRLRRLLLLLRRRRLLRLRRLRRLRLLRLLRLLLRRRLRLLRRLLLRLRLLRRRRLLLRRRLLRLLRRLLRRLRLLLRLRLRLRLRRRLLLRRLLLRLRLRLLLRRRLRRL

Oplossing Frans van den Berg: geen oplossing met 669 stappen