ASCII Art of the Day #2 - Flow Snakes

Question

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 code-golf 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

Answer 1

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

Answer 2

Python 2, 428 411 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[0]*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

Answer 3

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[2];--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[2];--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>

Answer 4

Haskell, 265 bytes

(?)=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!

Answer 5

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.

Answer 6

Haskell, 469 419 390 385 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]

Answer 7

Python 2, 523 502 475 473 467 450 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)

Answer 8

C, 479 474 468 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

Answer 9

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.