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 fractal as described here:
- For F_wordm 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.
Also see the Gdip examples.
<lang AutoHotkey>#NoEnv SetBatchLines, -1 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, Shutdown
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) }
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:: Shutdown: Gdip_DeletePen(pPen) SelectObject(hdc, obm) DeleteObject(hbm) DeleteDC(hdc) Gdip_DeleteGraphics(G) Gdip_Shutdown(pToken) ExitApp</lang>
C
Writes an EPS file that has the 26th fractal. This is probably cheating. <lang c>#include <stdio.h>
int main(void) { puts( "%!PS-Adobe-3.0 EPSF\n" "%%BoundingBox: -10 -10 400 565\n" "/a{0 0 moveto 0 .4 translate 0 0 lineto stroke -1 1 scale}def\n" "/b{a 90 rotate}def");
char i; for (i = 'c'; i <= 'z'; i++) printf("/%c{%c %c}def\n", i, i-1, i-2);
puts("0 setlinewidth z showpage\n%%EOF");
return 0; }</lang>
C++
<lang cpp>
- include <windows.h>
- include <string>
using namespace std;
class myBitmap { public:
myBitmap() : pen( NULL ) {}
~myBitmap()
{
DeleteObject( pen );
DeleteDC( hdc );
DeleteObject( bmp );
}
bool create( int w, int h )
{
BITMAPINFO bi;
ZeroMemory( &bi, sizeof( bi ) );
bi.bmiHeader.biSize = sizeof( bi.bmiHeader );
bi.bmiHeader.biBitCount = sizeof( DWORD ) * 8;
bi.bmiHeader.biCompression = BI_RGB; bi.bmiHeader.biPlanes = 1; bi.bmiHeader.biWidth = w; bi.bmiHeader.biHeight = -h; HDC dc = GetDC( GetConsoleWindow() ); bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 ); if( !bmp ) return false; hdc = CreateCompatibleDC( dc ); SelectObject( hdc, bmp ); ReleaseDC( GetConsoleWindow(), dc ); width = w; height = h; clear(); return true;
}
void clear()
{
ZeroMemory( pBits, width * height * sizeof( DWORD ) );
}
void setPenColor( DWORD clr )
{
if( pen ) DeleteObject( pen ); pen = CreatePen( PS_SOLID, 1, clr ); SelectObject( hdc, pen );
}
void saveBitmap( string path )
{
BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; DWORD* dwpBits; DWORD wb; HANDLE file;
GetObject( bmp, sizeof( bitmap ), &bitmap ); dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight]; ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) ); ZeroMemory( &infoheader, sizeof( BITMAPINFO ) ); ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) );
infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8; infoheader.bmiHeader.biCompression = BI_RGB; infoheader.bmiHeader.biPlanes = 1; infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader ); infoheader.bmiHeader.biHeight = bitmap.bmHeight; infoheader.bmiHeader.biWidth = bitmap.bmWidth; infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD );
fileheader.bfType = 0x4D42; fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER ); fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage;
GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS );
file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL ); WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL ); WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL ); WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL ); CloseHandle( file );
delete [] dwpBits;
}
HDC getDC() { return hdc; }
int getWidth() { return width; }
int getHeight() { return height; }
private:
HBITMAP bmp; HDC hdc; HPEN pen; void *pBits; int width, height;
}; class fiboFractal { public:
fiboFractal( int l )
{
bmp.create( 600, 440 ); bmp.setPenColor( 0x00ff00 ); createWord( l ); createFractal(); bmp.saveBitmap( "path_to_save_bitmap" );
}
private:
void createWord( int l )
{
string a = "1", b = "0", c; l -= 2; while( l-- ) { c = b + a; a = b; b = c; } fWord = c;
}
void createFractal()
{
int n = 1, px = 10, dir, py = 420, len = 1, x = 0, y = -len, goingTo = 0;
HDC dc = bmp.getDC(); MoveToEx( dc, px, py, NULL ); for( string::iterator si = fWord.begin(); si != fWord.end(); si++ ) { px += x; py += y; LineTo( dc, px, py ); if( !( *si - 48 ) ) { // odd if( n & 1 ) dir = 1; // right else dir = 0; // left switch( goingTo ) { case 0: // up y = 0; if( dir ){ x = len; goingTo = 1; } else { x = -len; goingTo = 3; } break; case 1: // right x = 0; if( dir ) { y = len; goingTo = 2; } else { y = -len; goingTo = 0; } break; case 2: // down y = 0; if( dir ) { x = -len; goingTo = 3; } else { x = len; goingTo = 1; } break; case 3: // left x = 0; if( dir ) { y = -len; goingTo = 0; } else { y = len; goingTo = 2; } }
}
n++;
} }
string fWord; myBitmap bmp;
}; int main( int argc, char* argv[] ) {
fiboFractal ff( 23 ); return system( "pause" );
} </lang>
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.
Elixir
<lang elixir>defmodule Fibonacci do
def fibonacci_word, do: Stream.unfold({"1","0"}, fn{a,b} -> {a, {b, b<>a}} end)
def word_fractal(n) do
word = fibonacci_word |> Enum.at(n)
walk(to_char_list(word), 1, 0, 0, 0, -1, %{{0,0}=>"S"})
|> print
end
defp walk([], _, _, _, _, _, map), do: map
defp walk([h|t], n, x, y, dx, dy, map) do
map2 = Dict.put(map, {x+dx, y+dy}, (if dx==0, do: "|", else: "-"))
|> Dict.put({x2=x+2*dx, y2=y+2*dy}, "+")
if h == ?0 do
if rem(n,2)==0, do: walk(t, n+1, x2, y2, dy, -dx, map2),
else: walk(t, n+1, x2, y2, -dy, dx, map2)
else
walk(t, n+1, x2, y2, dx, dy, map2)
end
end
defp print(map) do
xkeys = Dict.keys(map) |> Enum.map(fn {x,_} -> x end)
xmin = Enum.min(xkeys)
xmax = Enum.max(xkeys)
ykeys = Dict.keys(map) |> Enum.map(fn {_,y} -> y end)
ymin = Enum.min(ykeys)
ymax = Enum.max(ykeys)
Enum.each(ymin..ymax, fn y ->
IO.puts Enum.map_join(xmin..xmax, fn x -> Dict.get(map, {x,y}, " ") end)
end)
end
end
Fibonacci.word_fractal(16)</lang> Output is same as Ruby.
FreeBASIC
On a Windows 32bit system F_word35 is the biggest that can be drawn. <lang FreeBASIC>' version 23-06-2015 ' compile with: fbc -s console "filename".bas
Dim As String fw1, fw2, fw3 Dim As Integer a, b, d , i, n , x, y, w, h Dim As Any Ptr img_ptr, scr_ptr
' data for screen/buffer size Data 1, 2, 3, 2, 2, 2, 2, 2, 7, 10, 8, 14 Dim As Integer s(38,2) For i = 3 To 9
Read s(i,1) : Read s(i,2)
Next For i = 9 To 38 Step 6
s(i, 1) = s(i -1, 1) +2 : s(i, 2) = s(i -1, 1) + s(i -1, 2) s(i +1, 1) = s(i, 2) +2 : s(i +1, 2) = s(i, 2) s(i +2, 1) = s(i, 1) + s(i, 2) : s(i +2, 2) = s(i, 2) s(i +3, 1) = s(i +1, 1 ) + s(i +2, 1) : s(i +3, 2) = s(i ,2) s(i +4, 1) = s(i +3, 1) : s(i +4, 2) = s(i +3, 1) + 2 s(i +5, 1) = s(i +3, 1) : s(i +5, 2) = s(i +3, 2) + s(i +4, 2) +2
Next
' we need to set screen in order to create image buffer in memory Screen 21 scr_ptr = ScreenPtr() If (scr_ptr = 0) Then
Print "Error: graphics screen not initialized." Sleep End -1
End If
Do
Cls Do
Print
Print "For wich n do you want the Fibonacci Word fractal (3 to 35)."
While Inkey <> "" : fw1 = Inkey : Wend ' empty keyboard buffer
Input "Enter or a value smaller then 3 to stop: "; n
If n < 3 Then
Print : Print "Stopping."
Sleep 3000,1
End
EndIf
If n > 35 then
Print : Print "Fractal is to big, unable to create it."
Sleep 3000,1
Continue Do
End If
Loop Until n < 36
fw1 = "1" : fw2 = "0" ' construct the string
For i = 3 To n
fw3 = fw2 + fw1
Swap fw1, fw2 ' swap pointers of fw1 and fw2
Swap fw2, fw3 ' swap pointers of fw2 and fw3
Next
fw1 = "" : fw3 = "" ' free up memory
w = s(n, 1) +1 : h = s(n, 2) +1
' allocate memory for a buffer to hold the image
' use 8 bits to hold the color
img_ptr = ImageCreate(w,h,0,8)
If img_ptr = 0 Then ' check if we have created a image buffer
Print "Failed to create image."
Sleep
End -1
End If
x = 0: y = h -1 : d = 1 ' set starting point and direction flag
PSet img_ptr, (x, y) ' set start point
For a = 1 To Len(fw2)
Select Case As Const d
Case 0
x = x + 2
Case 1
y = y - 2
Case 2
x = x - 2
Case 3
y = y + 2
End Select
Line img_ptr, -(x, y)
b = fw2[a-1] - Asc("0")
If b = 0 Then
If (a And 1) Then
d = d + 3 ' a = odd
Else
d = d + 1 ' a = even
End If
d = d And 3
End If
Next
If n < 24 Then ' size is smaller then screen dispay fractal
Cls
Put (5, 5),img_ptr, PSet
Else
Print
Print "Fractal is to big for display."
End If
' saves fractal as bmp file (8 bit palette)
If n > 23 Then h = 80
Draw String (0, h +16), "saving fractal as fibword" + Str(n) + ".bmp."
BSave "F_Word" + Str(n) + ".bmp", img_ptr
Draw String (0, h +32), "Hit any key to continue."
Sleep
ImageDestroy(img_ptr) ' free memory holding the image
Loop</lang>
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>
J
Plotting the fractal as a parametric equation, this looks reasonably nice:
<lang J>require 'plot' plot }:+/\ 0,*/\(^~ 0j_1 0j1 $~ #)'0'=_1{::F_Words 20</lang>
Note that we need the definition of F_Words from the Fibonacci word page:
<lang J>F_Words=: (,<@;@:{~&_1 _2)@]^:(2-~[)&('1';'0')</lang>
However, image uploads are currently disabled, and rendering images of this sort as wikitext gets bulky.
Instead, I'll just describe the algorithm:
This draws a discrete parametric curve. Right turn is 0j_1, left turn is 0j1 (negative and positive square roots of negative 1), straight ahead is 1. So: build a list of alternating 0j_1 and 0j1 and raise them to the first power for the 0s in the fibonacci word list and raise them to the 0th power for the 1s in that list. Then compute the running product, shift a 0 onto the front of the list of products and compute the running sum. (Of course, this would translate to a rather simple loop, also, once you see the pattern.)
Logo
fibonacci.word.fractal can draw any number of line segments. A Fibonacci number shows the self-similar nature of the fractal. The Fibonacci word values which control the turns are generated here by some bit-twiddling iteration.
<lang Logo>; Return the low 1-bits of :n
- For example if n = binary 10110111 = 183
- then return binary 111 = 7
to low.ones :n
output ashift (bitxor :n (:n+1)) -1
end
- fibbinary should be a fibbinary value
- return the next larger fibbinary value
to fibbinary.next :fibbinary
localmake "filled bitor :fibbinary (ashift :fibbinary -1) localmake "mask low.ones :filled output (bitor :fibbinary :mask) + 1
end
to fibonacci.word.fractal :steps
localmake "step.length 5 ; length of each step
localmake "fibbinary 0
repeat :steps [
forward :step.length
if (bitand 1 :fibbinary) = 0 [
ifelse (bitand repcount 1) = 1 [right 90] [left 90]
]
make "fibbinary fibbinary.next :fibbinary
]
end
setheading 0 ; initial line North fibonacci.word.fractal 377</lang>
Mathematica / Wolfram Language
<lang mathematica>(*note, this usage of Module allows us to memoize FibonacciWord
without exposing it to the global scope*)
Module[{FibonacciWord, step},
FibonacciWord[1] = "1";
FibonacciWord[2] = "0";
FibonacciWord[n_Integer?(# > 2 &)] :=
(FibonacciWord[n] = FibonacciWord[n - 1] <> FibonacciWord[n - 2]);
step["0", {_?EvenQ}] = N@RotationTransform[Pi/2];
step["0", {_?OddQ}] = N@RotationTransform[-Pi/2];
step[___] = Identity;
FibonacciFractal[n_] := Module[{steps, dirs},
steps = MapIndexed[step, Characters[FibonacciWord[n]]];
dirs = ComposeList[steps, {0, 1}];
Graphics[Line[FoldList[Plus, {0, 0}, dirs]]]]];</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>
Perl 6
<lang perl6>constant @fib-word = '1', '0', { $^b ~ $^a } ... *;
sub MAIN($m = 17, $scale = 3) {
(my %world){0}{0} = 1;
my $loc = 0+0i;
my $dir = i;
my $n = 1;
for @fib-word[$m].comb {
when '0' {
step;
if $n %% 2 { turn-left }
else { turn-right; }
}
$n++;
}
braille-graphics %world;
sub step {
for ^$scale {
$loc += $dir;
%world{$loc.im}{$loc.re} = 1;
}
}
sub turn-left { $dir *= i; }
sub turn-right { $dir *= -i; }
}
sub braille-graphics (%a) {
my ($ylo, $yhi, $xlo, $xhi);
for %a.keys -> $y {
$ylo min= +$y; $yhi max= +$y; for %a{$y}.keys -> $x { $xlo min= +$x; $xhi max= +$x; }
}
for $ylo, $ylo + 4 ...^ * > $yhi -> \y {
for $xlo, $xlo + 2 ...^ * > $xhi -> \x { my $cell = 0x2800; $cell += 1 if %a{y + 0}{x + 0}; $cell += 2 if %a{y + 1}{x + 0}; $cell += 4 if %a{y + 2}{x + 0}; $cell += 8 if %a{y + 0}{x + 1}; $cell += 16 if %a{y + 1}{x + 1}; $cell += 32 if %a{y + 2}{x + 1}; $cell += 64 if %a{y + 3}{x + 0}; $cell += 128 if %a{y + 3}{x + 1}; print chr($cell); } print "\n";
}
}</lang>
- Output:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢈⣉⡁⠀⠀⠀⢈⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠸⠤⡄⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢰⠒⡆⢰⠒⠃⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣏⣉⠀⣉⣉⠀⠀⠀⠀⣉⣉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣉⣉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠈⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣸⠉⣇⣀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⢤⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⡖⢲⠀⡖⠚⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢈⣉⡁⠀⠀⠀⢈⣉⡁⢈⣉⡇⢸⣉⡁⢈⣉⡁⠀⠀⠀⢈⣉⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢈⣉⡁⠀⠀⠀⢈⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠧⢤⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⡄⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⣀⣀⠀⣉⣹⠀⣏⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⣀⣀⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⠇⠀⠀⠀⠸⠤⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⢰⠒⠃⠘⠒⡆⢰⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⢰⠒⠃⠘⠒⡆⢰⠒⡆⠀⠀⠀⢰⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣉⠀⠀⠀⠀⣉⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣉⠀⠀⠀⠀⣉⣉⠀⣉⣹⠀⣏⣉⠀⣉⣉⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⢈⣉⡇⢸⣉⡁⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⢈⣉⡇⢸⣉⡁⢀⣀⡀⠀⠀⠀⢀⣀⡀⢈⣉⡇⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⡖⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⡖⢲⠀⡖⠚⠀⠓⢲⠀⡖⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⢈⣉⡁⢈⣉⡇⢸⣉⡁⢈⣉⡁⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⢈⣉⡁⢈⣉⡇⢸⣉⡁⢈⣉⡁⠀⠀⠀⢈⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠧⢤⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⡄⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⢲⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⣀⣀⠀⣉⣹⠀⣏⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⢠⠤⠇⠸⠤⠇⠀⠀⠀⠸⠤⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⠀⠀⠀⢰⠒⡆⢰⠒⠃⠘⠒⡆⢰⠒⡆⠀⠀⠀⢰⠒⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⠀⠀⠀⢰⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⠉⠉⠀⠀⠀⠀⠉⠉⠀⣉⣹⠀⣏⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⢤⠀⡤⠼⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⠃⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣸⠉⣇⣸⠉⠁⠈⠉⣇⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⢤⠀⡤⢤⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢰⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⠃⠘⠒⡆⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢀⣀⡀⢈⣉⡇⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⡤⠼⠀⠧⠼⠀⠀⠀⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠧⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠓⢲⠀⡖⢲⠀⠀⠀⠀⡖⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡖⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠈⠉⠁⢈⣉⡇⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣉⡁⢈⣉⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠸⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠤⠇⠀⠀⠀⠸⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⡆⠀⠀⠀⢰⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⣉⠀⣉⣹⠀⣏⣉⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⠃⠀⠀⠀⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃
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.
REXX
Programming note: the starting point (.) and the ending point (∙) are also shown to help visually identify the end points.
About half of the REXX program is dedicated to plotting the appropriate characters. <lang rexx>/*REXX program generates a Fibonacci word, then displays the fractal curve.*/ parse arg ord . /*obtain optional arguments from the CL*/ if ord== then ord=23 /*Not specified? Then use the default*/ s=FibWord(ord) /*obtain the order of Fibonacci word.*/
x=0; maxX=0; dx=0; b=' '; @.=b; xp=0
y=0; maxY=0; dy=1; @.0.0=.; yp=0
do n=1 for length(s); x=x+dx; y=y+dy /*advance the plot for the next point. */
maxX=max(maxX,x); maxY=max(maxY,y) /*set the maximums for displaying plot.*/
c='│'; if dx\==0 then c='─'; if n==1 then c='┌' /*The 1st plot?*/
@.x.y=c /*assign a plotting character for curve*/
if @(xp-1,yp)\==b & @(xp,yp-1)\==b then call @ xp,yp,'┐' /*fix-up.*/
if @(xp-1,yp)\==b & @(xp,yp+1)\==b then call @ xp,yp,'┘' /* " */
if @(xp+1,yp)\==b & @(xp,yp+1)\==b then call @ xp,yp,'└' /* " */
if @(xp+1,yp)\==b & @(xp,yp-1)\==b then call @ xp,yp,'┌' /* " */
xp=x; yp=y; z=substr(s,n,1) /*save old x,y; assign plot character.*/
if z==1 then iterate /*Is Z equal to unity? Then ignore it.*/
ox=dx; oy=dy; dx=0; dy=0 /*save DX,DY as the old versions. */
d=-n//2; if d==0 then d=1 /*determine the sign for the chirality.*/
if oy\==0 then dx=-sign(oy)*d /*Going north|south? Go east|west */
if ox\==0 then dy= sign(ox)*d /* " east|west? " south|north */
end /*n*/
call @ x,y,'∙' /*set the last point that was plotted. */
do r=maxY to 0 by -1; _= /*show single row at a time, top first.*/
do c=0 to maxX; _=_ || @.c.r; end /*c*/
if _\= then say strip(_,'T') /*if not blank, then display a line. */
if _\= then call lineout 'FIBFRACT.OUT',strip(_,'T') /*write to file*/
end /*r*/ /* [↑] only display the non-blank rows*/
exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ @: parse arg xx,yy,p; if arg(3)== then return @.xx.yy; @.xx.yy=p; return /*────────────────────────────────────────────────────────────────────────────*/ FibWord: procedure; arg x; !.=0; !.1=1 /*obtain the order of Fibonacci word. */
do k=3 to x; k1=k-1; k2=k-2 /*generate the Kth Fibonacci word. */
!.k=!.k1 || !.k2 /*construct the next Fibonacci word. */
end /*k*/ /* [↑] generate a Fibonacci word. */
return !.x /*return the Xth Fibonacci word. */</lang> output when using the input: 14
∙
│ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
└─┘ │ │ └─┘ │ │ └─┘ │
┌┘ └┐ ┌┘ └┐ ┌┘
│ │ │ ┌─┐ │ │
└┐ ┌┘ └─┘ └─┘ └┐
┌─┐ │ │ ┌─┐ ┌─┐ │
│ └─┘ └─┘ │ │ └─┘
└┐ ┌─┐ ┌─┐ ┌┘ └┐
│ │ └─┘ │ │ │
┌┘ └┐ ┌┘ └┐ ┌┘
│ ┌─┐ │ │ ┌─┐ │ │ ┌─┐
└─┘ └─┘ └─┘ └─┘ └─┘ │
┌─┐ ┌─┐ ┌┘
│ └─┘ │ │
└┐ ┌┘ └┐
│ │ ┌─┐ │
┌┘ └─┘ └─┘
│ ┌─┐
└─┘ │
┌┘
│
└┐
┌─┐ │
│ └─┘
└┐ ┌─┐ ┌─┐
│ │ └─┘ │
┌┘ └┐ ┌┘
│ ┌─┐ │ │
└─┘ └─┘ └┐
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ │
│ └─┘ │ │ └─┘ │ │ └─┘
└┐ ┌┘ └┐ ┌┘ └┐
│ │ ┌─┐ │ │ │
┌┘ └─┘ └─┘ └┐ ┌┘
│ ┌─┐ ┌─┐ │ │ ┌─┐
└─┘ │ │ └─┘ └─┘ │
┌┘ └┐ ┌─┐ ┌─┐ ┌┘
│ │ │ └─┘ │ │
└┐ ┌┘ └┐ ┌┘ └┐
┌─┐ │ │ ┌─┐ │ │ ┌─┐ │
. └─┘ └─┘ └─┘ └─┘ └─┘
The output of this REXX program for this Rosetta Code task requirements can be seen here ───► Fibonacci word/fractal/FIBFRACT.REX.
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>
Ruby
<lang ruby>def fibonacci_word(n)
words = ["1", "0"]
(n-1).times{ words << words[-1] + words[-2] }
words[n]
end
def print_fractal(word)
area = Hash.new(" ")
x = y = 0
dx, dy = 0, -1
areax,y = "S"
word.each_char.with_index(1) do |c,n|
areax+dx, y+dy = dx.zero? ? "|" : "-"
x, y = x+2*dx, y+2*dy
areax, y = "+"
dx,dy = n.even? ? [dy,-dx] : [-dy,dx] if c=="0"
end
(xmin, xmax), (ymin, ymax) = area.keys.transpose.map(&:minmax)
for y in ymin..ymax
puts (xmin..xmax).map{|x| areax,y}.join
end
end
word = fibonacci_word(16) print_fractal(word)</lang>
- Output:
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
+ +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ +
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+ + +-+-+ + + + + +-+-+ + + + + +-+-+ + + + + +-+-+ + +
| | | | | | | | | | | | | | | | | | | | | | | |
+-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+
| | | | | | | |
+ +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ +
| | | | | | | | | | | | | | | | | | | | | | | |
+-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+
| | | | | | | |
+-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+
| | | | | | | | | | | | | | | |
+ + + +-+-+ + + + + + + +-+-+ + + +
| | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | |
+-+-+ + + +-+-+ + + +-+-+ + + +-+-+ +-+-+ + + +-+-+ + + +-+-+ + + +-+-+
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ + + +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +
| | | |
+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+
| | | | | | | | | | | | | | | | | | | |
+ + +-+-+ + + +-+-+ + + + + +-+-+ + + +-+-+ + +
| | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | |
+ +-+-+ + + + + +-+-+ + + +-+-+ + + + + +-+-+ +
| | | | | | | | | | | | | | | | | | | |
+-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+
| | | |
+-+-+ + + +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ + + +-+-+
| | | | | | | | | | | | | | | | | | | |
+ +-+-+ +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ +-+-+ +
| | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | |
+ + + + +-+-+ + + + +
| | | | | | | | | |
+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+
| | | | | |
+ +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ +
| | | | | | | | | | | | | | | | | |
+-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+
| | | | | |
+-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+
| | | | | | | | | | | | | | | | | | | | | |
+ +-+-+ + + + + +-+-+ + + + + +-+-+ + + + + +-+-+ +
| | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | |
+ + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + +
| | | | | | | | | | | | | | | | | | | | | | | | | |
+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+
| |
+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +
| | | | | | | | | | | | | | | | | | | | | |
+-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+
| | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | |
+ + + +-+-+ + + + + +-+-+ + + +
| | | | | | | | | | | | | |
+-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+
| | | | | |
+-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+
| | | | | | | | | | | | | | | | | |
+ +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ +
| | | | | |
+-+ +-+-+ +-+-+ +-+ +-+ +-+ +-+ +-+-+ +-+-+ +-+
| | | | | | | | | | | | | |
+ + +-+-+ + + + + + + +-+-+ + +
| | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | |
+ +-+-+ + + +-+-+ + + +-+-+ +-+-+ + + +-+-+ + + +-+-+ +
| | | | | | | | | | | | | | | | | | | | | |
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ + + +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
| |
+-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+
| | | | | | | | | |
+ +-+-+ + + + + +-+-+ +
| | | | | |
+-+ +-+ +-+ +-+ +-+ +-+
| | | | | |
+ + +-+-+ + + +-+-+ + +
| | | | | | | | | |
+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+
| |
+ +-+-+ +-+-+ +
| | | | | |
+-+-+ + + +-+-+
| |
+-+ +-+
| |
+ +
| |
+-+ +-+
| |
+-+-+ + + +-+-+
| | | | | |
+ +-+-+ +-+-+ +
| |
+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+
| | | | | | | | | |
+ + +-+-+ + + +-+-+ + +
| | | | | |
+-+ +-+ +-+ +-+ +-+ +-+
| | | | | |
+ +-+-+ + + + + +-+-+ +
| | | | | | | | | |
+-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+
| |
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ + + +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | | | | | | | | | | | | | | | |
+ +-+-+ + + +-+-+ + + +-+-+ +-+-+ + + +-+-+ + + +-+-+ +
| | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | |
+ + +-+-+ + + + + + + +-+-+ + +
| | | | | | | | | | | | | |
+-+ +-+-+ +-+-+ +-+ +-+ +-+ +-+ +-+-+ +-+-+ +-+
| | | | | |
+ +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ +
| | | | | | | | | | | | | | | | | |
+-+-+ + + +-+-+ +-+-+ + + +-+-+ +-+-+ + + +-+-+
| | | | | |
+-+ +-+ +-+-+ +-+-+ +-+ +-+ +-+-+ +-+-+ +-+ +-+
| | | | | | | | | | | | | |
+ + + +-+-+ + + + + +-+-+ + + +
| | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | |
+-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+ + + +-+-+
| | | | | | | | | | | | | | | | | | | | | |
S +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+
Scala
Note: will be computing an SVG image - not very efficient, but very cool. worked for me in the scala REPL with -J-Xmx2g argument. <lang scala> def fibIt = Iterator.iterate(("1","0")){case (f1,f2) => (f2,f1+f2)}.map(_._1)
def turnLeft(c: Char): Char = c match {
case 'R' => 'U' case 'U' => 'L' case 'L' => 'D' case 'D' => 'R'
}
def turnRight(c: Char): Char = c match {
case 'R' => 'D' case 'D' => 'L' case 'L' => 'U' case 'U' => 'R'
}
def directions(xss: List[(Char,Char)], current: Char = 'R'): List[Char] = xss match {
case Nil => current :: Nil
case x :: xs => x._1 match {
case '1' => current :: directions(xs, current)
case '0' => x._2 match {
case 'E' => current :: directions(xs, turnLeft(current))
case 'O' => current :: directions(xs, turnRight(current))
}
}
}
def buildIt(xss: List[Char], old: Char = 'X', count: Int = 1): List[String] = xss match {
case Nil => s"$old$count" :: Nil case x :: xs if x == old => buildIt(xs,old,count+1) case x :: xs => s"$old$count" :: buildIt(xs,x)
}
def convertToLine(s: String, c: Int): String = (s.head, s.tail) match {
case ('R',n) => s"l ${c * n.toInt} 0"
case ('U',n) => s"l 0 ${-c * n.toInt}"
case ('L',n) => s"l ${-c * n.toInt} 0"
case ('D',n) => s"l 0 ${c * n.toInt}"
}
def drawSVG(xStart: Int, yStart: Int, width: Int, height: Int, fibWord: String, lineMultiplier: Int, color: String): String = {
val xs = fibWord.zipWithIndex.map{case (c,i) => (c, if(c == '1') '_' else i % 2 match{case 0 => 'E'; case 1 => 'O'})}.toList
val fractalPath = buildIt(directions(xs)).tail.map(convertToLine(_,lineMultiplier))
s"""<?xml version="1.0" encoding="utf-8"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"><svg version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px" width="${width}px" height="${height}px" viewBox="0 0 $width $height"><path d="M $xStart $yStart ${fractalPath.mkString(" ")}" style="stroke:#$color;stroke-width:1" stroke-linejoin="miter" fill="none"/></svg>"""
}
drawSVG(0,25,550,530,fibIt.drop(18).next,3,"000") </lang>
- Output:
output string saved as an SVG file - BTW, would appreciate help on getting the image to display here nicely. couldn't figure out how to do that...
Sidef
<lang ruby>var(m=17, scale=3) = @ARGV.map{.to_i};
(var world = Hash.new){0}{0} = 1; var loc = Complex(0, 0); var dir = Complex::i;
var fib = ['1', '0']; func fib_word(n) {
fib[n] \\= (fib_word(n-1) + fib_word(n-2));
}
func step {
scale.times {
loc += dir;
world{loc.im}{loc.re} = 1;
}
}
func turn_left { dir *= Complex::i }; func turn_right { dir *= -Complex::i };
var n = 1; fib_word(m).each_char { |c|
if (c == '0') {
step();
n % 2 == 0 ? turn_left()
: turn_right()
} else { n++ }
}
func braille_graphics(a) {
var (xlo, xhi, ylo, yhi) = +([Math.inf, -Math.inf]*2)...;
a.each_key { |y|
ylo.min!(y.to_i);
yhi.max!(y.to_i);
a{y}.each_key { |x|
xlo.min!(x.to_i);
xhi.max!(x.to_i);
}
}
range(ylo, yhi, 4).each { |y|
range(xlo, xhi, 2).each { |x|
var cell = 0x2800;
a{y+0}{x+0} && (cell += 1);
a{y+1}{x+0} && (cell += 2);
a{y+2}{x+0} && (cell += 4);
a{y+0}{x+1} && (cell += 8);
a{y+1}{x+1} && (cell += 16);
a{y+2}{x+1} && (cell += 32);
a{y+3}{x+0} && (cell += 64);
a{y+3}{x+1} && (cell += 128);
print cell.chr;
};
print "\n";
}
}
braille_graphics(world);</lang>
- Output:
$ sidef fib_word_fractal.sf 12 3 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⢤⠀⡤⠼⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠒⠃⠘⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⣇⣸⠉⣇⣀⠀⣀⣸⠉⣇⣀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⡖⢲⠀⠀ ⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢈⣉⡁⠀⠀⠀⢈⣉⡁⢈⣉⡇ ⠀⠀⠀⡤⠼⠀⠧⢤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠼⠀⠧⢤⠀⡤⠼⠀⠧⠼⠀⠀ ⠀⠀⠀⠓⢲⠀⡖⠚⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢲⠀⡖⠚⠀⠓⢲⠀⠀⠀⠀⠀ ⠉⢹⣀⡏⠉⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠉⢹⣀⡏⠉⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢠⠤⡄⢠⠤⠇⠸⠤⡄⢠⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⡖⠚⠀⠓⠚⠀⠀⠀⠀⠓⠚⠀⠓⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠉⢹⣀⡏⢹⣀⡀⢀⣀⡏⢹⣀⡏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠤⠇⠸⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠒⡆⢰⠒⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
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>
zkl
Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl
<lang zkl>fcn drawFibonacci(img,x,y,word){ // word is "01001010...", 75025 characters
dx:=0; dy:=1; // turtle direction
foreach i,c in ([1..].zip(word)){ // Walker.zip(list)-->Walker of zipped list
a:=x; b:=y; x+=dx; y+=dy;
img.line(a,b, x,y, 0x00ff00);
if (c=="0"){
dxy:=dx+dy;
if(i.isEven){ dx=(dx - dxy)%2; dy=(dxy - dy)%2; }// turn left else { dx=(dxy - dx)%2; dy=(dy - dxy)%2; }// turn right
} }
}
img:=PPM(1050,1050); fibWord:=L("1","0"); do(23){ fibWord.append(fibWord[-1] + fibWord[-2]); } drawFibonacci(img,20,20,fibWord[-1]); img.write(File("foo.ppm","wb"));</lang>
- Output:
Pretty much the same as the Python output but in a PPM file
http://www.zenkinetic.com/Images/RosettaCode/fibonacci_word_fractal.jpg
