Code Challenge

Iedereen heeft wel zo’n prachtige Nokia gehad met het beruchte spelletje snake. In deze challenge gaan we iets doen wat daar op lijkt. Onze slang groeit alleen oneindig en heeft één vreemde eigenschap. Elke keer als de slang een stap neemt en zijn totale lengte een priemgetal is, moet de slang daarna een bocht maken van 90 graden. Uiteraard geldt nog steeds dat onze slang zichzelf niet mag raken, als een coördinaat gebruikt is dan mag deze niet nogmaals gebruikt worden.

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.

 

Je antwoord bestaat uit een string van 669 karakters L of R, overeenkomend met de keuzes die de slang maakt voor iedere priemlengte. Een valide voorbeeld is "LRRLLRRLLRRLL…". Dit is overigens niet echt een slang die efficiënt gebruik maakt van de ruimte, zie ook de afbeelding (rood is het beginpunt). Een triviale invalide oplossing begint met "RRR…" waarbij de slang direct over zichzelf heen loopt. Je opdracht is om een valide antwoord te vinden voor een slang met lengte 5000 waarbij je een vierkante 'bounding box' om de snake minimaliseert. Om precies te zijn: een vierkant met zijden van: max(max(x) – min(x), max(y) – min(y)).

 

Om je op weg te helpen staat de code om een visualisatie van je oplossing te maken hier: http://bit.ly/priemslang. Deze solver controleert ook of je antwoord valide is.