Fibonacci word fractal

Question

The Fibonacci word is a sequence of binary strings defined as:

• \$F_0 = \$ 0
• \$F_1 = \$ 01
• \$F_n = F_{n-1} F_{n-2}\$

The first few Fibonacci words are:

0
01
010
01001
01001010
0100101001001
010010100100101001010
...

Each of these strings is a prefix of the next, so they are all prefixes of the single infinite word \$F_\infty\$ =

010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001...

(The definition above is borrowed from this sandbox challenge by pxeger.)

Now we can define a fractal curve based on the Fibonacci words.

Starting from some point on the plane, for each digit at position \$k\$ of the Fibonacci word \$F_\infty\$:

• Draw a segment with length \$1\$ forward,
• If the digit is \$0\$:
  • Turn 90° to the left if \$k\$ is even,
  • Turn 90° to the right if \$k\$ is odd.

This is called the Fibonacci word fractal.

For example, the first 21 digits in \$F_\infty\$ are 010010100100101001010, which would give the following shape:

┌
│ ┌─┐
└─┘ │
   ┌┘
   │
   └┐
┌─┐ │
│ └─┘

To be clearer, let's mark the starting point by ^, and replace the other chars by its corresponding digit in the Fibonacci word:

0
1 010
010 1
   00
   1
   00
010 1
^ 010

Here are some more steps of the Fibonacci word fractals, taken from Wikipedia:

Task and rules

Given a non-negative integer \$n\$, draw at least \$n\$ steps of the infinite Fibonacci word fractal.

You may draw more steps than \$n\$. But the extra steps should still belong to the infinite Fibonacci word fractal.

Or alternatively, you may take no input, and draw every step of the infinite Fibonacci word fractal (as an animation, or an infinite sequence of outputs).

You may output as either ascii-art or graphical-output.

For ascii-art, you may choose any characters to draw the curve as long as the output is clear.

The fractal curve consists of a chain of line segments. For each step, you may choose to draw one of the followings, but your choice must be consistent (taking \$n=21\$ as an example):

• the starting point of the segment:

# ###
### #
   ##
   #
   ##
### #
# ###

• the ending point of the segment:

#
# ###
### #
   ##
   #
   ##
### #
  ###

• the whole segment.

#
# ###
### #
   ##
   #
   ##
### #
# ###

The direction don't need to be consistent. You may arbitrarily rotate or reflect the curve.

This is code-golf, so the shortest code in bytes wins.

Answer 1

J, 79 bytes

load'plot'
[:plot 0;/@|:[:+.@([:+/\1*/\@,-.+0j1*]*_1^#\)@;_2&(],<@;@{.)&(1;1 0)

J Playground

Generates more than required, because it:

• First iterates fib n times
• Uses complex numbers with product scans and sum scan to calculate all the coords at once
• plots those coordinates

Answer 2

Desmos, 111 bytes

p->p+1,d->d+90(1-floor(pk+k)+floor(pk))(1-2mod(p,2)),L->join(L[1]+(cosd,sind),L)
L=[(0,0)]
gg~g+1
k=2-g
p=2
d=0

Paste the first line in a ticker, the second line in a collapsed folder, and the rest of the lines in the regular expression boxes. Also make sure Desmos is set to degrees mode, and not radians.

Then click the ticker (the metronome in the top left corner) to run the code.

Theoretically, this can go on infinitely, but due to Demsos's list length cap at 10000 elements, we can only generate 9999 segments before erroring out. But it doesn't really matter, because Desmos already starts lagging pretty badly (at least on my computer) around 3 or 4k segments, so it would take a while to actually get to 9999 segments (I left it running for around 15 minutes or so and got up to around 7000 segments).

Also, the list L is stored in a collapsed folder because Desmos lags really, really badly if not collapsed; it is trying to render the entire list while it is constantly being updated by the tickers. Open the folder at your own risk :P

Fun little tidbit: Setting d's initial value to something other than 0 will cause the code to produce a rotated fractal. Try it out!

Try It On Desmos!

Try It On Desmos! - Prettified

Around 7000 segments

---

Here's a longer version without actions (it runs a lot faster!):

125 bytes

gg~g+1
k=2-g
L=[1...n]
S=∑_{a=0}^L90(1-floor(ak+k)+floor(ak))(-1)^a
C(l)=∑_{i=1}^Ll[i]
f(n)=join((0,0),(C(cosS),C(sinS)))

The function f(n) will take in a positive integer n and output the first n segments of the fractal.

The restriction of 9999 segments also applies to this answer; Desmos lists can only contain up to 10000 elements. Theoretically though, the code can produce any amount of segments if there was no restriction on list length.

f(9999) takes about 30 seconds to load on my computer.

Try It On Desmos!

Try It On Desmos! - Prettified

3000 segments (if you don't want to load the 9999 segments)

Answer 3

Vyxal, 41 39 33 32 31 30 28 26 25 24 23 19 bytes

1₀?(~p)yNYdÞR8%2×ø∧

Try it Online!

Takes n and draws the nth fibonacci number of steps.

Outputs as ascii art.

I may have forgotten you can use any non-whitespace character :p...

-4 thanks to emanresuA even if I somehow didn't notice it for 4 days

Explained (old)

1₀?(~p)f:ẏu$ed*ÞR8%2×ø∧
1₀                        # Push 1 and 10 to the stack. These will form the initial terms for the Fibonacci words
  ?(  )                   # Input number of times: 
    ~p                    #   Without popping the top two items on the stack, prepend the top to the second-top. This gives [1, 10, 101, 10110, 10110101, 1011010110110, ...] - the sequence but with inverted bits
       f:                 # Push two copies of the top of the stack as a list of digits
         ẏu$e             # Push -1 to the power of each index in the range [0, len(top)]. This determines both a) whether a turn is needed and b) which general direction to make the turn if a turn is needed for each bit in the Fibonacci word. The result will be 0 (no turn, keep going), 1 (turn to the right) or -1 (turn to the left).
             d*           # Double the list so it can be used with the canvas drawing element and multiply the bit list by the direction list. More on the canvas a little later
               ÞR         # Take the cumulative sums of the list, remove the last item, and prepend a 0. Yes, that's a thing that's 2 bytes in Vyxal.
                 8%       # Modulo each item by 8. This is so that each number can be mapped to a canvas direction that is one of [0, 2, 4, 6]. 0 = up, 2 = right, 4 = down, 6 = left
                   2×ø∧   # For each direction in that list, draw a line of *s of length 2 on the global canvas in that direction. Think of the canvas as a kind of turtle but ascii thing, where each direction moves the turtle and leaves a trail of *s behind. The global canvas is implicitly printed at end of execution. This could also be ø^, but ø∧ looks better :p    

Answer 4

Python, 83 bytes

from turtle import*
a,b=[i:=0],[-1]
while 1:a,b=b,b+a;lt(b[i]**i*90);fd(5);i+=1

-6 thanks to tsh

Draws it infinitely.

Very slow because it generates another term of the Fibonacci sequence at every iteration. This is much faster if you want to test it:

from turtle import*
a,b=[i:=0],[90]
while 1:
 if i>=len(b):a,b=b,b+a
 lt(b[i]*(-1)**i);fd(5);i+=1

Try it on repl.it!

You can also add a speed(0) at the beginning to make it draw faster.

Answer 5

Charcoal, 29 26 bytes

≔1θＦＮ«#↷∧Ｉ§θι⁺²×⁴ι≔⭆θ⍘⊕κ²θ

Try it online! Link is to verbose version of code. Outputs the start point of each segment. Explanation: Actually calculates the complementary sequence A005614 because it's golfier.

≔1θ

Start with 1.

ＦＮ«

Repeat n times.

#

Output the start point of the segment.

↷∧Ｉ§θι⁺²×⁴ι

Calculate the amount of rotation in multiples of 45°. This is 0 if the element of A005614 was 0 or 2 plus 4 times the number of steps so far (k).

≔⭆θ⍘⊕κ²θ

Extend the string holding A005614 by incrementing each digit in base 2 i.e. replace 0 with 1 and 1 with 10. (Note that this is very inefficient since it calculates the string to length F(n+2) which is 28657 for the example of n=21.)

Previous more efficient 29-byte version:

ＦＮ«#Ｗ№⍘Ｌυ²11⊞υω⊞υω↷∧﹪Ｌυ²⁺²×⁴ι

Try it online! Link is to verbose version of code. Outputs the start point of each segment. Explanation: The Fibonacci word A003849 is simply the Fibbinary sequence A003714 modulo 2.

ＦＮ«

Loop n times.

#

Output the start point of the segment.

Ｗ№⍘Ｌυ²11⊞υω

Increase the length of the predefined empty list as necessary so that it reaches a Fibbinary number, i.e. its binary representation does not contain 11.

⊞υω

Increase the length of the predefined empty list again. The above loop will then find the next Fibbinary number on the next pass through the outer loop, but this also complements the least significant bit which simplifies the next calculation.

↷∧﹪Ｌυ²⁺²×⁴ι

Calculate the amount of rotation in multiples of 45°. This is 0 if the Fibbinary number was odd or 2 plus 4 times the number of steps so far (k).

Answer 6

05AB1E, 37 34 32 bytes

Tηλèì}āsÏV0YvDyÈiÍëÌ])8%AY¥>2šrΛ

Takes advantage of the mentioned at least in the challenge rules to save 2 bytes.
Outputs using the lowercase alphabet as characters (but could also use any single digit instead by replacing the A).

Try it online.

Explanation:

Step 1: Get the Fibonacci word \$F_n\$ based on the input \$n\$, but with the 0s and 1s reversed:

T         # Push 10
 η        # Pop and push its prefixes: [1,10]
  λ       # Start a recursive environment,
   è      # to generate the (0-based) (implicit) input'th value
          # Starting with a(0)=1 and a(1)=10
          # Where every following a(n) is calculated as:
          #  (implicitly push a(n-2) and a(n-1)
    ì     #  Prepend a(n-1) in front of a(n-2)
  }       # Close the recursive environment

Try just step 1 online.

Step 2: Generate a list of \$k+1\$ at the 1-positions:

   ā      # Push a list in the range [1,length] (without popping the string)
    s     # Swap so the string is at the top of the stack again
     Ï    # Only keep the 1-based values at the truthy (==1) positions

Try just step 2 online.

Step 3: Using this list of \$k+1\$ indicating when to turn clockwise/counterclockwise, transform it to a list of 05AB1E Canvas directions (0=↑; 2=→; 4=↓; 6=←):

      V   # Pop and store this list in variable `Y`
0         # Push a 0
 Yv       # Loop `y` over list `Y`:
   D      #  Duplicate the current value
    yÈi   #  If `y` is even:
       Í  #   Increase the value by 2
      ë   #  Else (`y` is odd):
       Ì  #   Decrease the value by 2
  ]       # Close both the if-else and loop
   )      # Wrap all values on the stack into a list
    8%    # Modulo-8 each

Try just step 3 online.

Step 4: Modify the list from step 2 to a list of lengths, and using this modified list and the directions-list from step 3, draw the lowercase alphabet in this pattern with the Canvas builtin:

A         # Push constant "abcdefghijklmnopqrstuvwxyz"
 Y        # Push list `Y` from step 2
  ¥       # Pop and push its deltas/forward-differences
   >      # Increase each value by 1
    2š    # Prepend a 2
      r   # Reverse the three values on the stack
       Λ  # Use the Canvas builtin with these three options
          # (after which the result is output immediately)

See this 05AB1E tip of mine for an in-depth explanation about the Canvas builtin Λ and how the generated directions- and length-lists are used.

Answer 7

Wolfram Language (Mathematica), 75 bytes

Graphics@Line@AnglePath@Nest[Flatten@{#,p(-1)^Tr[1^(p=#)]}&,p=0;Pi/2,#]&

Takes n and draws the nth fibonacci number of steps.

n=14

-24 bytes from @alephalpha
-4 bytes from @att

Answer 8

MATL, 28 27 26 bytes

Inspired by Sanchises' answer to a loosely related challenge. I think the approach is also similar to that in Jonah's answer here.

JO2B1i:"6Mh]htn:Eq*^YpYsXG

The output is rotated 90 degrees clockwise with respect to the examples in the challenge text. The initial segment is not drawn. More steps than necessary are drawn.

Try it at MATL online!

With input 11 this gives the last image shown in the challenge (rotated):

Explanation

J       % Push imaginary unit, j: (*)
O       % Push 0: (**)
2B      % Push 2 in binary, that is, [1 0]. This is F_1, with 0 and swapped
1       % Push 1. This is F_0, with 1 instead of 0
i       % Input n
:"      % Do n times
  6M    %   Push first input to the latest function that took more than 1 input.
        %   In the first iteration this does nothing; in iteration k>1 it gives
        %   F_{k-1} 
  h     %   Concatenate F_k and F_{k-1} to produce F_{k+1}
]       % End. The top of the stack contains F_{k+1}
h       % Concatenate 0 (**) with F_{k+1}: (***) 
t       % Duplicate
n:      % Range [1 2 3 ... L], where L is the length of the above
Eq      % Times 2, minus 1, element-wise. Gives [1 3 5 ...]
*       % Multiply with (***), element-wise
^       % Imaginary unit (*) raised to this, element-wise
Yp      % Cumulative product. This generates the directions: 1, j, -1 or -j
Ys      % Cumulative sum. This generates the path, starting at 0
XG      % Plot as complex numbers

Answer 9

Prolog (SWI), 242 bytes

N+A+B+R:-N<1,R=B;append(B,A,C),N-1+B+C+R.
D-X/Y-N-K-Q:-Q=[H|T],(N/\1>0,V=X+2-N;V=X),(N/\1>0,W=Y;W=Y+1-N),new(L,line(X,Y,V,W)),send(D,display,L),M is(N-K*H)mod 4,D-V/W-M-(-1)*K-T;1=1.
\X:-new(D,window()),X+[1]+[1,0]+R,D-0/0-1-1-R,send(D,open).

\X will calculate the Xth Fibonacci word and thus draw at least X steps.

Uses the XPCE toolkit for creating GUI applications in Prolog, here's an example output for goal \20.:

In the A-B-C-D-E predicate, no expressions are evaluated until calling new to create the line, which makes the code very slow:

?- time(\16).
% 36,098 inferences, 15.493 CPU in 15.518 seconds (100% CPU, 2330 Lips)

Here is a faster and more readable version that evaluates every iteration:

_-_-_-_-[]-fast.
D-X/Y-N-K-[H|T]-fast:-
    % Flip K (odd/even position)
    Z is(-1)*K,
    % Calculate the new X,Y location
    (N/\1>0,V is X+2-N;V=X),
    (N/\1>0,W=Y;W is Y+1-N),
    % Send new line to display
    new(L,line(X,Y,V,W)),
    send(D,display,L),
    % Set new direction depending on H and previous direction N
    M is(N-K*H)mod 4,
    D-V/W-M-Z-T-fast.
fast(X):-
    % 0s and 1s are flipped for shorter calculation (if 0 becomes if 1)
    new(D,window()),X+[1]+[1,0]+R,D-0/0-1-1-R-fast,send(D,open).

?- time(fast(25)).
% 3,374,631 inferences, 2.311 CPU in 2.319 seconds (100% CPU, 1460457 Lips)

Answer 10

R, 99 82 76 74 73 bytes

Edit: -2 bytes thanks to pajonk

function(n,`?`=cumsum){while(n<-n-1)T=c(F,F<-T)
plot(?1i^?c(1,3)*T,,"l")}

Try it at rdrr.io

while(n<-n-1)T=c(F,F<-T) generates the n-th Fibonacci word in reverse, with zeros and ones exchanged.
Then, cumsum(c(1,3)*m) calculates cumulative sum multiplied by 1 (at odd indices) or 3 (at even indices), to give the current direction. i raised to this power gives a step in the right direction, and the cumulative sum of this gives the position at each step: cumsum(1i^cumsum(c(1,3)*m)) (the function cumsum is re-assigned to the low-precedence ? operator to save bytes (and obfuscate).
So we just plot this on the complex plane, using "l" to join the points with lines.

This would be 66 bytes in R version ≥4.1 by replacing function with \, but this isn't currently supported by the online interpreter at rdrr.io.

Answer 11

HTML+Javascript, 228 216 210 bytes

f(n) draws at least n segments. The size adapts so that the fractal does not get too small.

12 bytes saved thanks to Neil

f=o=>{for(k=b=n=0,l='01';!l[o];)m=l,l+=k,k=m
d='M1,1';p=5;for(w of l)e=1-(b&2),d+='hv'[b&1]+e,b+=w|0?0:n%2*2+1,b%=4,p+=e,n++
document.write(`<svg viewBox=0,0,${p},${p} style=fill:none;stroke:#000><path d=`+d)}
f(2000)

-13 bytes with a fixed-size canvas, which limits the number of segments that are visible. (And low n are really hard to see.) For viewBox="0 0 999 999", approx. n ≤ 75000.

f=o=>{for(k=b=n=0,l='01';!l[o];)m=l,l+=k,k=m
d='M1,1';for(w of l)d+='hv'[b&1]+(1-(b&2)),b+=w|0?0:n%2*2+1,b%=4,n++
document.write(`<svg viewBox=0,0,999,999 style=fill:none;stroke:#000><path d=`+d)}
f(75000)

Non-competing bonus: I was also experimenting with a recursive solution in HTML/Pug, but it ended at 500 bytes, and it's really slow and memory-heavy. See it on Codepen.