# 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!

# Leaderboard

The first post of the series generates a leaderboard.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

# 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. – edc65 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 – Optimizer 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. – edc65 May 20 '15 at 19:14
• @edc65 Oh, there!. Fixed! – Optimizer 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. – mbomb007 May 20 '15 at 19:25

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! – Optimizer 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). – Anders Kaseorg May 27 '15 at 11:32 • Its okay as the login thing only needed my email id for confirmation .. – Optimizer 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[0] 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. – Anders Kaseorg May 23 '15 at 3:05 • You are right. I corrected it – Damien 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 – proud haskeller May 23 '15 at 13:38

# 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.

Example run at http://codepad.org/ZGc648Xi

• 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) – Spikatrix 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. – Optimizer 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=[0]
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[0]*(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 = [0]
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 – Matty 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;
{
S = quadgen(-12);  \\ sqrt(-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. – Anders Kaseorg 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 :-). – Kevin Ryde 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.) – Anders Kaseorg May 24 '15 at 10:58
• Ah dear, when the endpoint is the x maximum. Hmm. – Kevin Ryde May 25 '15 at 9:59