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_word37 start with F_wordCharn=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.
AutoHotkey
Prints F_Word30 currently. Segment length and F_Wordn can be adjusted.
Requires: Gdip.ahk as a Lib or #Include. <lang AutoHotkey>SetBatchLines, -1
- #MaxMem 200 ; Increased memory required for F_Word > 37
p := 0.3 ; Segment length (pixels) F_Word := 30
SysGet, Mon, MonitorWorkArea W := FibWord(F_Word), d := 1, x1 := 0, y1 := MonBottom , Width := A_ScreenWidth, Height := A_ScreenHeight
If (!pToken := Gdip_Startup()) { MsgBox, 48, gdiplus error!, Gdiplus failed to start. Please ensure you have gdiplus on your system ExitApp } OnExit, Exit
Gui, 1: -Caption +E0x80000 +LastFound +AlwaysOnTop +ToolWindow +OwnDialogs Gui, 1: Show, NA
hwnd1 := WinExist(), hbm := CreateDIBSection(Width, Height), hdc := CreateCompatibleDC() , obm := SelectObject(hdc, hbm), G := Gdip_GraphicsFromHDC(hdc), Gdip_SetSmoothingMode(G, 4) , pPen := Gdip_CreatePen(0xffff0000, 1)
Loop, Parse, W { if (d = 0) x2 := x1 + p, y2 := y1 else if (d = 1 || d = -3) x2 := x1, y2 := y1 - p else if (d = 2 || d = -2) x2 := x1 - p, y2 := y1 else if (d = 3 || d = -1) x2 := x1, y2 := y1 + p Gdip_DrawLine(G, pPen, x1, y1, x2, y2) if (!Mod(A_Index, 1500)) UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height) if (A_LoopField = 0) { if (!Mod(A_Index, 2)) d += 1 else d -= 1 } x1 := x2, y1 := y2, d := Mod(d, 4) } UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height) , Gdip_DeletePen(pPen), UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height) , SelectObject(hdc, obm), DeleteObject(hbm), DeleteDC(hdc), Gdip_DeleteGraphics(G) return
FibWord(n, FW1=1, FW2=0) { Loop, % n - 2 FW3 := FW2 FW1, FW1 := FW2, FW2 := FW3 return FW3 }
Esc:: Exit: Gdip_DeletePen(pPen), UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height), SelectObject(hdc, obm) , DeleteObject(hbm), DeleteDC(hdc), Gdip_DeleteGraphics(G), Gdip_Shutdown(pToken) ExitApp</lang> Some portions of code from Gdip examples by tic (Tariq Porter).
D
This uses the turtle module from the Dragon Curve Task, and the module from the Grayscale Image task.
<lang d>import std.range, grayscale_image, turtle;
void drawFibonacci(Color)(Image!Color img, ref Turtle t,
in string word, in real step) {
foreach (immutable i, immutable c; word) {
t.forward(img, step);
if (c == '0') {
if ((i + 1) % 2 == 0)
t.left(90);
else
t.right(90);
}
}
}
void main() {
auto img = new Image!Gray(1050, 1050);
auto t = Turtle(30, 1010, -90);
const w = recurrence!q{a[n-1] ~ a[n-2]}("1", "0").drop(24).front;
img.drawFibonacci(t, w, 1);
img.savePGM("fibonacci_word_fractal.pgm");
}</lang> It prints the level 25 word as the Python entry.
Icon and Unicon
This probably only works in Unicon. It also defaults to showing the factal for F_word25 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>
Perl
Creates file fword.png containing the Fibonacci Fractal. <lang perl>use strict; use warnings; use GD;
my @fword = ( undef, 1, 0 );
sub fword { my $n = shift; return $fword[$n] if $n<3; return $fword[$n] //= fword($n-1).fword($n-2); }
my $size = 3000; my $im = new GD::Image($size,$size); my $white = $im->colorAllocate(255,255,255); my $black = $im->colorAllocate(0,0,0); $im->transparent($white); $im->interlaced('true');
my @pos = (0,0); my @dir = (0,5); my @steps = split //, fword 23; my $i = 1; for( @steps ) { my @next = ( $pos[0]+$dir[0], $pos[1]+$dir[1] ); $im->line( @pos, @next, $black ); @dir = ( $dir[1], -$dir[0] ) if 0==$_ && 1==$i%2; # odd @dir = ( -$dir[1], $dir[0] ) if 0==$_ && 0==$i%2; # even $i++; @pos = @next; }
open my $out, ">", "fword.png" or die "Cannot open output file.\n"; binmode $out; print $out $im->png; close $out; </lang>
Python
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>
Tcl
<lang tcl>package require Tk
- OK, this stripped down version doesn't work for n<2…
proc fibword {n} {
set fw {1 0}
while {[llength $fw] < $n} {
lappend fw [lindex $fw end][lindex $fw end-1]
} return [lindex $fw end]
} proc drawFW {canv fw {w {[$canv cget -width]}} {h {[$canv cget -height]}}} {
set w [subst $w] set h [subst $h]
# Generate the coordinate list using line segments of unit length
set d 3; # Match the orientation in the sample paper
set eo [set x [set y 0]]
set coords [list $x $y]
foreach c [split $fw ""] {
switch $d { 0 {lappend coords [incr x] $y} 1 {lappend coords $x [incr y]} 2 {lappend coords [incr x -1] $y} 3 {lappend coords $x [incr y -1]} } if {$c == 0} { set d [expr {($d + ($eo ? -1 : 1)) % 4}] } set eo [expr {!$eo}]
}
# Draw, and rescale to fit in canvas
set id [$canv create line $coords]
lassign [$canv bbox $id] x1 y1 x2 y2
set sf [expr {min(($w-20.) / ($y2-$y1), ($h-20.) / ($x2-$x1))}]
$canv move $id [expr {-$x1}] [expr {-$y1}]
$canv scale $id 0 0 $sf $sf
$canv move $id 10 10
# Return the item ID to allow user reconfiguration
return $id
}
pack [canvas .c -width 500 -height 500] drawFW .c [fibword 23]</lang>