Pappersdrake av Heighway-modell

Heighway-drake är (tyvärr) inte en eldsprutande mytologisk varelse. För att se sådana så prova här borta. En Heighway-drake är en sorts fraktal som man kan rita upp, en matematisk kurva. Ett sätt att skapa den är att se draken i olika generationer, som skapas enligt:

• generation 0 (noll) är textsträngen "FX"
• generation n skapas genom att man i generation (n-1) byter ut alla X mot X+YF+ och alla Y mot -FX-Y.

Man får alltså att de första generationerna av drakar är
Gen 0: FX
Gen 1: FX+YF+
Gen 2: FX+YF++-FX-YF+
Gen 3: FX+YF++-FX-YF++-FX+YF+--FX-YF+


När man ska rita upp kurvan så startar man i punkten (0,0) och har riktningen uppåt. Sedan går man igenom textsträngen och de olika tecknen betyder:

• F = dra ett streck ett steg framåt
• + = vrid 90 grader medurs
• - = vrid 90 grader moturs

X och Y betyder inget när man väl ritar upp kurvan.

Generation 1 och 2, uppritat på rutat papper.

En pappersmodell

Man kan göra sig en modell av en Heighway-drake genom att vika ihop en pappersremsa på mitten, och vika ihop den på mitter igen och så vidare. Sen vecklar man ut remsan, och försöker vå vinkeln i varje veck att bli 90 grader. Jag har några kort på hur en fjärde generationens drake kan se ut, när man vecklar ut den steg för steg.

Generation 1

Generation 2

Generation 3

Generation 4

En app

Pappersmodellerna är bra, men det är svårt att göra drakar av högre generationer. Så en kväll gjorde jag mig en app till min telefon som kan rita upp draken åt mig. I alla fall upp till generation 10, sen klarar inte min telefon av det. Koden är med största sannolikhet inte tillräckligt optimerad för att vara så snabb som den borde, men som tur är har skärmen inte upplösning nog för att visa så mycket mer. Att jag var tvungen att låtsas att jag kan Java, OpenGL och Android SDK för att få till den bidrar nog också till att den inte är den mest optimerade appen.

Min app gör inte mycket. Men det den gör, gör den på en Android-telefon. Den fungerar i alla fall på min, och skulle någon våga prova så finns här: Heighway-app. För att se olika storlekar så drar man fingret höger-vänster över skärmen.

Project Euler - Problem 220

Istället för korsord brukar jag ibland ge mig på något problem från Project Euler. Ibland går det bra, ibland kör jag fast. Problem nr 220 handlar om just Heighway-drakar som är ännu större, som är av ännu högre generation, än de drakar min lilla app ritar upp. Men i problemet består inte i att rita ut draken, utan det är beräkningar som ska göras på kurvan. Problemet (i korthet) går ut på att räkna ut var man hamnar om man går utefter drakens kurva i ett visst antal steg, om man startar i "svansen" som har sin spets i punkten (0,0).

Till exempel, om man (i den första bilden från appen) följer den gröna draken i 5 steg med start där röd och grön drake möts, så hamnar man på punkten (2,-1)

I Project Euler är antalet steg 10 upphöjt till 12 (1000000000000), och jag har inte haft datorkraft/tålamod att låta min dator rita upp en drake av tillräckligt hög generation för att kunna gå de stegen. Men som tur är behöver man som sagt inte rita upp draken, man kan istället räkna ut var man hamnar. För att räkna ut det så skrev jag en liten snutt Haskell-kod, och efter ett par misslyckade försök så lyckades jag komma på hur positionen skulle räknas ut (utan att behöva mer datorkraft/tålamod än vad jag hade tillgång till).

Koden tänkte jag inte lägga ut här, om det är någon som vill ge sig på problemet själv, men i korthet går min lösning ut på att:

• en drake av generation n består av två drakar av generation (n-1) som börjar från varsitt håll och möts i huvudet.
• var huvudet på en drake hamnar går lätt att räkna ut om man vet dess generation