ASCII Art of the Day #2 - Flow Snakes

A Flow Snake, also known as a Gosper curve, is a fractal curve, growing exponentially in size with each order/iteration of a simple process. Below are the details about the construction and a few examples for various orders:

Order 1 Flow Snake:

____
\__ \
__/

Order 2 Flow Snake:

____
____ \__ \
\__ \__/ / __
__/ ____ \ \ \
/ __ \__ \ \/
\ \ \__/ / __
\/ ____ \/ /
\__ \__/
__/

Order 3 Flow Snake:

____
____ \__ \
\__ \__/ / __
__/ ____ \ \ \    ____
/ __ \__ \ \/ / __ \__ \
____ \ \ \__/ / __ \/ / __/ / __
____ \__ \ \/ ____ \/ / __/ / __ \ \ \
\__ \__/ / __ \__ \__/ / __ \ \ \ \/
__/ ____ \ \ \__/ ____ \ \ \ \/ / __
/ __ \__ \ \/ ____ \__ \ \/ / __ \/ /
\ \ \__/ / __ \__ \__/ / __ \ \ \__/
\/ ____ \/ / __/ ____ \ \ \ \/ ____
\__ \__/ / __ \__ \ \/ / __ \__ \
__/ ____ \ \ \__/ / __ \/ / __/ / __
/ __ \__ \ \/ ____ \/ / __/ / __ \/ /
\/ / __/ / __ \__ \__/ / __ \/ / __/
__/ / __ \ \ \__/ ____ \ \ \__/ / __
/ __ \ \ \ \/ ____ \__ \ \/ ____ \/ /
\ \ \ \/ / __ \__ \__/ / __ \__ \__/
\/ / __ \/ / __/ ____ \ \ \__/
\ \ \__/ / __ \__ \ \/
\/      \ \ \__/ / __
\/ ____ \/ /
\__ \__/
__/

Construction

Consider the order 1 Flow Snake to be built of a path containing 7 edges and 8 vertices (labelled below. Enlarged for feasibility):

4____5____6
\         \
3\____2   7\
/
0____1/

Now for each next order, you simply replace the edges with a rotated version of this original order 1 pattern. Use the following 3 rules for replacing the edges:

1 For a horizontal edge, replace it with the original shape as is:

________
\       \
\____   \
/
____/

2 For a / edge (12 in the above construction), replace it with the following rotated version:

/
/   ____
\  /   /
\/   /
/
____/

3 For a \ edge (34and 67 above), replace it with the following rotated version:

/
/   ____
\   \   \
\   \   \
\  /
\/

So for example, order 2 with vertices from order 1 labelled will look like

________
\       \
________   \____   \6
\       \      /   /
\____   \5___/   /   ____
/            \   \   \
4___/   ________   \   \   \7
/        \       \   \  /
/   ____   \____   \2  \/
\   \   \      /   /
\   \   \3___/   /   ____
\  /            \  /   /
\/   ________   \/   /
\       \      /
\____   \1___/
/
0___/

Now for any higher order, you simply break up the current level into edges of lengths 1 /, 1 \ or 2 _ and repeat the process. Do note that even after replacing, the common vertices between any two consecutive edges are still coinciding.

Challenge

• You have to write a function of a full program that receives a single integer N via STDIN/ARGV/function argument or the closest equivalent and prints the order N Flow Snake on STDOUT.
• The input integer is always greater than 0.
• There should not be any leading spaces which are not part of the pattern.
• There should be either no trailing spaces or enough trailing spaces to pad the pattern to fill the minimum bounding rectangle completely.
• Trailing newline is optional.

Fun Facts

• Flow Snakes is a word play of Snow Flakes, which this pattern resembles for order 2 and above
• The Flow and Snakes actually play a part in the pattern as the pattern is made up of a single path flowing throughout.
• If you notice carefully, the order 2 (and higher as well) pattern comprises of rotations of order 1 pattern pivoted on the common vertex of the current and the previous edge.
• There is a Non ASCII variant of Flow Snakes which can be found here and at several other locations.

This is so shortest code in bytes win!

The first post of the series generates a leaderboard.

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes
• If I understand correctly, the shapes 1,2,3 are enlarged 2x, so the bottom row in 2 should be made of 4 undescores, not 3. May 20 '15 at 19:06
• @edc65 The shapes in the examples are perfectly sized. If you are talking about the Construction part, yes, that is enlarged and there are 3 underscores so that the edge number takes up the 4th's place May 20 '15 at 19:09
• But there is no edge numbers in shape 2 (in construction part, yes). The bottom of shape 2 should be equal to the bottom of shape 1. May 20 '15 at 19:14
• @edc65 Oh, there!. Fixed! May 20 '15 at 19:21
• I read the title as "Snow Flakes" and didn't even notice the real title until you called attention to the difference. May 20 '15 at 19:25

Python 2, 428411 388 bytes

This one was pretty tricky. The patterns don't retain their ratios after each step meaning its very difficult to procedurally produce an image from its predecessor. What this code does, though its pretty unreadable after some intense math golfing, is actually draw the line from start to finish using the recursively defined D function.

The size was also an issue, and I ended up just starting in the middle of a 5*3**n sided square and cropping things afterward, though if I can think of better way to calculate the size I might change it.

n=input();s=5*3**n
r=[s*[" "]for i in*s]
def D(n,x,y,t=0):
if n<1:
x-=t%2<1;y+=t%3>1;r[y][x]='_/\\'[t/2]
if t<2:r[y][x+2*t-1]='_'
return[-1,2,0,1,0,1][t]+x,y-(2<t<5)
for c in[int(i)^t%2for i in"424050035512124224003"[t/2::3]][::(t^1)-t]:x,y=D(n-1,x,y,c)
return x,y
D(n,s/2,s/2)
S=[''.join(c).rstrip()for c in r]
for l in[c[min(c.find('\\')%s for c in S):]for c in S if c]:print l
• Wow, this is awesome. Wanna give a shot at AAoD #1 ? May 21 '15 at 8:25
• r=[s*[" "]for i in range(s)] -> r=[[" "]*s]*s] will shave a few bytes May 21 '15 at 16:01
• @sirpercival unfortunately that won't work because of how * repeats mutable objects.
– grc
May 21 '15 at 16:05
• oh, right, i forgot May 21 '15 at 16:06
• You can save some bytes by inlining l, switching print'\n'.join() to printing inside a for loop, using return[...][t]+x,, and removing the parentheses from (t%2). Also, you could use min(c.find('\\')%s for c in S) if you change the name of the list S so it doesn't overwrite the initial value of s.
– grc
May 21 '15 at 16:38

JavaScript (ES6), 356 362 370

That's a difficult one ...

Each shape is stored as a path. There are 6 basic building blocks (3 + 3 backward)

• 0 diagonal up left to bottom right (4 backward)
• 1 diagonal bottom left to up right (5 backward)
• 2 horizontal left to right (6 backward)

For each one, there is a replacing step to be applied when increasing order:

• 0 --> 0645001 (backward 4 --> 5441024)
• 1 --> 2116501 (backward 5 --> 5412556)
• 2 --> 2160224 (backward 6 --> 0664256)

values prefilled in theh array, even if the elements 4..6 can be obtained from 0..2 using

;[...h[n]].reverse().map(x=>x^4).join('')

To obtain the shape for the given order, the path is built in the p variable applying the substitutions repeatedly. Then the main loop iterates on the p variable and draw the shape inside the g[] array, where each element is a row.
Starting at position (0,0), each index can become negative (y index at high orders). I avoid negative y indexes shifting all the g array whenever I find a negative y value. I don't care if the x index becomes negative, as in JS negative indexes are allowed, just a little more difficult to manage.
In the last step, I scan the main array using .map, but for each row I need to use an explicit for(;;) loop using the b variable that holds the least x index reached (that will be < 0).
In the console.log version there is a handy leading newline, that can be easily made a trailing newline swapping 2 rows, as in the snippet version.

f=o=>{
g=[],x=y=b=0,
h='064500192116501921602249954410249541255690664256'.split(9);
for(p=h;--o;)p=p.replace(/./g,c=>h[c]);
for(t of p)
z='\\/_'[s=t&3],
d=s-(s<1),
t>3&&(x-=d,y+=s<2),
y<0&&(y++,g=[,...g]),r=g[y]=g[y]||[],
s?s>1?r[x]=r[x+1]=z:r[x]=z:r[x-1]=z,
t<3&&(x+=d,y-=s<2),
x<b?b=x:0;
g.map(r=>
{
o+='\n';
for(x=b;x<r.length;)o+=r[x++]||' '
},o='');
console.log(o)
}

Handy snippet to test (in Firefox) :

f=o=>{
g=[],x=y=b=0,
h='064500192116501921602249954410249541255690664256'.split(9);
for(p=h;--o;)p=p.replace(/./g,c=>h[c]);
for(t of p)
z='\\/_'[s=t&3],
d=s-(s<1),
t>3&&(x-=d,y+=s<2),
y<0&&(y++,g=[,...g]),r=g[y]=g[y]||[],
s?s>1?r[x]=r[x+1]=z:r[x]=z:r[x-1]=z,
t<3&&(x+=d,y-=s<2),
x<b?b=x:0;
g.map(r=>
{
for(x=b;x<r.length;)o+=r[x++]||' ';
o+='\n'
},o='');
return o
}

// TEST

fs=9;
O.style.fontSize=fs+'px'

function zoom(d) {
d += fs;
if (d > 1 && d < 40)
fs=d, O.style.fontSize=d+'px'
}
#O {
font-size: 9px;
line-height: 1em;
}
<input id=I value=3><button onclick='O.innerHTML=f(I.value)'>-></button>
<button onclick="zoom(2)">Zoom +</button><button onclick="zoom(-2)">Zoom -</button>
<br>
<pre id=O></pre>

(?)=div
(%)=mod
t[a,b]=[3*a+b,2*b-a]
_#[0,0]=0
0#_=3
n#p=[352,6497,2466,-1]!!((n-1)#t[(s+3)?7|s<-p])?(4^p!!0%7)%4
0&_=0
n&p=(n-1)&t p+maximum(abs<$>sum p:p) n!b=n&[1,-b] f n=putStr$unlines[["__ \\/   "!!(2*n#t[a?2,-b]+a%2)|a<-[b-n!2+1..b+n!2+0^n?3]]|b<-[-n!0..n!0]]

(Note: on GHC before 7.10, you will need to add import Control.Applicative or replace abs<$> with map abs$.)

Run online at Ideone.com

f n :: Int -> IO () draws the level n flowsnake. The drawing is computed in bitmap order rather than along the curve, which allows the algorithm to run in O(n) space (that is, logarithmic in the drawing size). Nearly half of my bytes are spent computing which rectangle to draw!

• I logged in and it works now! Nice! May 27 '15 at 8:22
• It turns out this previously didn’t run on Ideone.com because I was assuming 64-bit Int. Fixed now (sacrificing 2 bytes). May 27 '15 at 11:32
• Its okay as the login thing only needed my email id for confirmation .. May 27 '15 at 11:34

Perl, 334 316 309

$_=2;eval's/./(map{($_,"\1"x7^reverse)}2003140,2034225,4351440)[$&]/ge;'x($s=<>);
s/2|3/$&$&/g;$x=$y=3**$s-1;s!.!'$r{'.qw($y--,$x++ ++$y,--$x $y,$x++ $y,--$x
$y--,--$x ++$y,$x++)[$&]."}=$&+1"!eeg;y!1-6!//__\\!,s/^$x//,s/ *$/
/,print for
grep{/^ */;$x&=$&;$'}map{/^/;$x=join'',map$r{$',$_}||$",@f}@f=0..3**$s*2 Parameter taken on the standard input. Test me. Haskell, 469419390385 365 bytes the function f::Int->IO() takes an integer as input and print the flow snake e 0=[0,0];e 5=[5,5];e x=[x] f n=putStr.t$e=<<g n
k=map$(53-).fromEnum g 0=id g n=g(n-1).(=<<)(k.(words"5402553 5440124 1334253 2031224 1345110 2003510"!!)) x=s$k"444666555666"
y=s$k"564645554545" r l=[minimum l..maximum l] s _[]=[];s w(x:y)=w!!(x+6):map(+w!!x)(s w y) t w=unlines[["_/\\\\/_ "!!(last$6:[z|(c,d,z)<-zip3(x w)(y w)w,c==i&&d==j])|i<-r.x$w]|j<-r.y$w]
• This produces 2× enlarged figures. I think the question is asking for the smaller figures at the top, and only used 2× enlarged figures to explain how the flowsnake is constructed. May 23 '15 at 3:05
• You are right. I corrected it May 23 '15 at 6:09
• You could use $in the definition of k, and replace (!!)a with (a!!) which can get rid from some parentheses. Other than that, you seem to know lots of tricks by yourself. Nice May 23 '15 at 13:38 CJam, 144 bytes 0_]0a{{_[0X3Y0_5]f+W@#%~}%}ri*{_[YXW0WW]3/If=WI6%2>#f*.+}fI]2ew{$_0=\1f=~-
"__1a /L \2,"S/=(@\+\~.+}%_2f<_:.e>\:.e<:M.-:)~S*a*\{M.-~3$3$=\tt}/zN*

Newline added to avoid scrolling. Try it online

The program works in several steps:

1. The initial fractal (order 1) is encoded as a sequence of 7 angles (conceptually, multiples of 60°) representing the direction of movement
2. The fractal is "applied" to a horizontal segment (order 0 fractal) N times to generate all the "movements" in the order N fractal
3. Starting from [0 0], the movements are translated into a sequence of points with [x y] coordinates
4. Each segment (pair of points) is converted to 1 or 2 [x y c] triplets, representing the character c at coordinates x, y
5. The bounding rectangle is determined, the coordinates are adjusted and a matrix of spaces is generated
6. For each triplet, the character c is placed at position x, y in the matrix, and the final matrix is adjusted for output
• This answer is long enough to benefit from byte encoding: goo.gl/D1tMoc Jun 10 '15 at 20:33
• @Dennis I'm not sure I'm done golfing it... and why did you put it in a block? Jun 10 '15 at 20:38
• I'm not really sure... Your answer is quite impressive. I spent an entirely day trying to get this right. Jun 10 '15 at 20:43
• @Dennis Thanks; btw, do you think it's generally ok to use non-printable/control characters? I usually try to avoid them Jun 10 '15 at 20:51
• If I can avoid them without increasing the byte count, I do. But shorter is shorter. :P In cases like this one where I compress the code itself rather than some string or array, I usually include both versions in the answer. Jun 10 '15 at 20:54

C, 479474468 427 bytes

There's no beating the Perl and Haskell guys I guess, but since there's no C submission here yet:

#define C char
C *q="053400121154012150223433102343124450553245";X,Y,K,L,M,N,i,c,x,y,o;F(C*p,
int l,C d){if(d){l*=7;C s[l];for(i=0;i<l;i++)s[i]=q[(p[i/7]%8)*7+i%7];return F
(s,l,d-1);}x=0;y=0;o=32;while(l--){c=*p++%8;for(i=!(c%3)+1;i--;) {K=x<K?x:K;L=
y<L?y:L;M=x>M?x:M;N=y>N?y:N;y+=c&&c<3;x-=c%5>1;if(x==X&y==Y)o="_\\/"[c%3];y-=c
>3;x+=c%5<2;}}return X<M?o:10;}main(l){F(q,7,l);for(Y=L;Y<N;Y++)for(X=K;X<=M;X
++)putchar(F(q,7,l));}

To save space on a atoi() call, the number of arguments passed to the program is used for the level.

The program runs in O(n^3) or worse; first the path is calculated once to find the min/max coordinates, then for each (x,y) pair it is calculated once to find the character on that specific location. Terribly slow, but saves on memory administration.

• Use X,Y,K,L,M,N,i,j,c; instead of int X,Y,K,L,M,N,i,j,c; and main(l) instead of void main(int l) May 23 '15 at 12:06
• Yeah, thanks, I already shaved off those and a bit more, I'll put up a new version.
– Zevv
May 23 '15 at 14:48
• The output in the latest version seems to be trimmed and a bit off on the ends. May 23 '15 at 15:00
• I uploaded the wrong blob, this one should be fine.
– Zevv
May 23 '15 at 15:13

Python 2, 523502475473467450 437 bytes

l=
for _ in l*input():l=sum([map(int,'004545112323312312531204045045050445212331'[t::6])for t in l],[])
p=[]
x=y=q=w=Q=W=0
for t in l:T=t|4==5;c=t in{2,4};C=t<3;q=min(q,x);Q=max(Q,x+C);w=min(w,y);W=max(W,y);a=C*2-1;a*=2-(t%3!=0);b=(1-T&c,-1)[T&1-c];x+=(a,0)[C];y+=(0,b)[c];p+=[(x,y)];x+=(0,a)[C];y+=(b,0)[c]
s=[[' ']*(Q-q)for _ in*(W-w+1)]
for t,(x,y)in zip(l,p):x-=q;s[y-w][x:x+1+(t%3<1)]='_/\_'[t%3::3]
for S in s:print''.join(S)

Pffft, costed me a like 3 hours, but was fun to do!

The idea is to split the task in multiple steps:

1. Calculate all the edges (encoded as 0-5) in order of appearence (so from the beginning of the snake to the end)
2. Calculate the position for each of the edges (and save the min and max values for x and y)
3. Build the strings it consists of (and use the min values to offset, so that we don't get negative indices)
4. Print the strings

Here is the code in ungolfed form:

# The input
n = int(input())

# The idea:
# Use a series of types (_, /, \, %), and positions (x, y)
# Forwards:   0: __  1: /  2: \
# Backwards:  3: __  4: /  5: \

# The parts
pieces = [
"0135002",
"0113451",
"4221502",
"5332043",
"4210443",
"5324551"
]
# The final types list
types = 
for _ in range(n):
old = types
types = []
for t in old:
types.extend(map(int,pieces[t]))

# Calculate the list of positions (and store the mins and max')
pos = []
top = False
x = 0
y = 0
minX = 0
minY = 0
maxX = 0
maxY = 0
for t in types:
# Calculate dx
dx = 1 if t < 3 else -1
if t%3==0:
dx *= 2         # If it's an underscore, double the horizontal size
# Calculate dy
top = t in {1, 5}
dy = 0
if top and t in {0, 3, 1, 5}:
dy = -1
if not top and t in {2, 4}:
dy = 1
# If backwards, add dx before adding the position to the list
if t>2:
x += dx
# If top to bottom, add dy before adding the position to the list
if t in {2,4}:
y += dy
# Add the current position to the list
pos += [(x, y)]
# In the normal cases (going forward and up) modify the x and y after changing the position
if t<3:
x += dx
if t not in {2, 4}:
y += dy
# Store the max and min vars
minX = min(minX, x)
maxX = max(maxX, x + (t<3)) # For forward chars, add one to the length (we never end with __'s)
minY = min(minY, y)
maxY = max(maxY, y)

# Create the string (a grid of charachters)
s = [[' '] * (maxX - minX) for _ in range(maxY - minY + 1)]
for k, (x, y) in enumerate(pos):
x -= minX
y -= minY
t = types[k]
char = '/'
if t % 3 == 0:
char = '__'
if t % 3 == 2:
char = '\\'
s[y][x : x + len(char)] = char

# Print the string
for printString in s:
print("".join(printString))

Edit: I changed the language to python 2, to be compatible with my answer for #3 (and it also saves 6 more bytes)

• Nice job; one simple improvement you could make would be changing l.extend(x) to l+=x. Also you can probably use codegolf.stackexchange.com/questions/54/… instead of the .split() you use (I did something similar in my answer)
– KSab
May 21 '15 at 0:50
• @KSab Thanks, I feel really stupid now for using extend May 21 '15 at 1:29

Pari/GP, 395

Looping over x,y character positions and calculating what char to print. Moderate attempts at minimizing, scored with whitespace and comments stripped.

k=3;
{
w = (1 + S)/2;     \\ sixth root of unity
b = 2 + w;         \\ base

\\ base b low digit position under 2*Re+4*Im mod 7 index
P = [0, w^2, 1, w, w^4, w^3, w^5];
\\ rotation state table
T = 7*[0,0,1,0,0,1,2, 1,2,1,0,1,1,2, 2,2,2,0,0,1,2];
C = ["_","_",  " ","\\",  "/"," "];

\\ extents
X = 2*sum(i=0,k-1, vecmax(real(b^i*P)));
Y = 2*sum(i=0,k-1, vecmax(imag(b^i*P)));

for(y = -Y, Y,
for(x = -X+!!k, X+(k<3),  \\ adjusted when endpoint is X limit
z = (x- (o = (x+y)%2) - y*S)/2;
v = vector(k,i,
z = (z - P[ d = (2*real(z) + 4*imag(z)) % 7 + 1 ])/b;
d);
print1( C[if(z,3,
r = 0;
forstep(i=#v,1, -1, r = T[r+v[i]];);
r%5 + o + 1)]) );  \\ r=0,7,14 mod 5 is 0,2,4
print())
}

Each char is the first or second of a hexagon cell. A cell location is a complex number z split into base b=2+w with digits 0, 1, w^2, ..., w^5, where w=e^(2pi/6) sixth root of unity. Those digits are kept just as a distinguishing 1 to 7 then taken high to low through a state table for net rotation. This is in the style of flowsnake code by Ed Shouten (xytoi) but only for net rotation, not making digits into an "N" index along the path. The extents are relative to an origin 0 at the centre of the shape. As long as the limit is not an endpoint these are the middle of a 2-character hexagon and only 1 of those chars is needed. But when the snake start and/or end are the X limit 2 chars are needed, which is k=0 start and k<3 end. Pari has "quads" like sqrt(-3) builtin but the same can be done with real and imaginary parts separately.

• This does not quite satisfy the rules regarding leading and trailing whitespace. May 23 '15 at 3:00
• Thanks, I amended. Your haskell beat me by an hour to an x,y loop did it. Should've posted before waiting to see if further inspiration would come :-). May 24 '15 at 9:06
• Now an end of the snake is cut off for k = 0, 1, 2. (The math is irritating that way—I had to deal with it too.) May 24 '15 at 10:58
• Ah dear, when the endpoint is the x maximum. Hmm. May 25 '15 at 9:59