Fibonacci word/fractal

Fibonacci word/fractal
You are encouraged to solve this task according to the task description, using any language you may know.

The Fibonacci word may be represented as a fratal as described here:

For F_word₃₇ start with F_wordChar_n=1

Draw a segment forward

If current F_wordChar is 0

Turn left if n is even

Turn right if n is odd

next n and iterate until end of F_word

For this task create and display a fractal similar to Fig 1.

Icon and Unicon

This probably only works in Unicon. It also defaults to showing the factal for F_word₂₅ as larger Fibonacci words quickly exceed the size of window I can display, even with a line segment length of a single pixel.

<lang unicon>global width, height

procedure main(A)

   n := integer(A[1]) | 25			    # F_word to use
   sl := integer(A[2]) | 1             # Segment length
   width := integer(A[3]) | 1050       # Width of plot area
   height := integer(A[4]) | 1050      # Height of plot area
   w := fword(n)
   drawFractal(n,w,sl)

end

procedure fword(n)

   static fcache
   initial fcache := table()
   /fcache[n] := case n of {
                    1: "1"
                    2: "0"
                    default: fword(n-1)||fword(n-2)
                    }
   return fcache[n]

end

record loc(x,y)

procedure drawFractal(n,w,sl)

   static lTurn, rTurn
   initial {
       every (lTurn|rTurn) := table()
       lTurn["north"] := "west"; lTurn["west"] := "south"
       lTurn["south"] := "east"; lTurn["east"] := "north"
       rTurn["north"] := "east"; rTurn["east"] := "south"
       rTurn["south"] := "west"; rTurn["west"] := "north"
       }
   
   wparms := ["FibFractal "||n,"g","bg=white","canvas=normal",
              "fg=black","size="||width||","||height,"dx=10","dy=10"]
   &window := open!wparms | stop("Unable to open window")
   p := loc(10,10)
   d := "north"
   every i := 1 to *w do {
      p := draw(p,d,sl)
      if w[i] == "0" then d := if i%2 = 0 then lTurn[d] else rTurn[d]
      }

   until Event() == &lpress
   WriteImage("FibFract"||n||".png")
   close(&window)

end

procedure draw(p,d,sl)

   if d == "north"      then p1 := loc(p.x,p.y+sl)
   else if d == "south" then p1 := loc(p.x,p.y-sl)
   else if d == "east"  then p1 := loc(p.x+sl,p.y)
   else                      p1 := loc(p.x-sl,p.y)
   DrawLine(p.x,p.y, p1.x,p1.y)
   return p1

end</lang>

Python

Translation of: Unicon

Note that for Python 3, functools.lru_cache could be used instead of the memoize decorator below. <lang python>from functools import wraps from turtle import *

def memoize(obj):

   cache = obj.cache = {}
   @wraps(obj)
   def memoizer(*args, **kwargs):
       key = str(args) + str(kwargs)
       if key not in cache:
           cache[key] = obj(*args, **kwargs)
       return cache[key]
   return memoizer

@memoize def fibonacci_word(n):

   assert n > 0
   if n == 1:
       return "1"
   if n == 2:
       return "0"
   return fibonacci_word(n - 1) + fibonacci_word(n - 2)

def draw_fractal(word, step):

   for i, c in enumerate(word, 1):
       forward(step)
       if c == "0":
           if i % 2 == 0:
               left(90)
           else:
               right(90)

def main():

   n = 25 # Fibonacci Word to use.
   step = 1 # Segment length.
   width = 1050 # Width of plot area.
   height = 1050 # Height of plot area.
   w = fibonacci_word(n)

   setup(width=width, height=height)
   speed(0)
   setheading(90)
   left(90)
   penup()
   forward(500)
   right(90)
   backward(500)
   pendown()
   tracer(10000)
   hideturtle()

   draw_fractal(w, step)

   # Save Poscript image.
   getscreen().getcanvas().postscript(file="fibonacci_word_fractal.eps")
   exitonclick()

if __name__ == '__main__':

   main()</lang>

The output image is probably the same.

Racket

Prime candidate for Turtle Graphics. I've used a values-turtle, which means you don't get the joy of seeing the turltle bimble around the screen. But it allows the size of the image to be set (useful if you want to push the _n much higher than 23 or so!

We use word-order 23, which gives a classic n shape (inverted horseshoe).

Save the (first) implementation of Fibonacci word to Fibonacci-word.rkt; since we do not generate the words here.

<lang racket>#lang racket (require "Fibonacci-word.rkt") (require graphics/value-turtles)

(define word-order 23) ; is a 3k+2 fractal, shaped like an n (define height 420) (define width 600)

(define the-word

 (parameterize ((f-word-max-length #f))
   (F-Word word-order)))

(for/fold ((T (turtles width height

                      0 height ; in BL corner
                      (/ pi -2)))) ; point north
 ((i (in-naturals))
  (j (in-string (f-word-str the-word))))
 (match* (i j)
   ((_ #\1) (draw 1 T))
   (((? even?) #\0) (turn -90 (draw 1 T)))
   ((_ #\0) (turn 90 (draw 1 T)))))</lang>