Draw the Hilbert curve using slashes

Question

The Hilbert curve is a space filling fractal that can be represented as a Lindenmayer system with successive generations that look like this:

^{Thanks to http://www.texample.net/tikz/examples/hilbert-curve/ for the image.}

Goal

Write the shortest program possible (in bytes) that takes a positive integer n from stdin and draws the nth order Hilbert curve to stdout using only forward slash, backward slash, space, and newline.

For example, if the input is 1 the output must be

 \
\/

If the input is 2 the output must be

  /
  \/\
/\   \
 / /\/
 \ \
  \/

If the input is 3 the output must be

       \
     /\/
    /   /\
    \/\ \ \
  /\  / / /
 / /  \/  \/\
 \ \/\  /\   \
\/   / / / /\/
  /\/ /  \ \
  \   \/\ \/
   \/\   \
     / /\/
     \ \
      \/

And so on. (They look nicer if you paste them into something with less line spacing.)

The output should not contain newlines above or below the extremities of the curve, nor any trailing spaces on any lines.

Answer 1

Ruby, 247 230 205 characters

r=?D
y=d=0
z=(1..2*x=2**gets.to_i.times{r.gsub!(/\w/){$&<?H?'-H~+D~D+~H-':'+D~-H~H-~D+'}}-1).map{' '*2*x}
r.bytes{|c|c>99?(z[y-=s=-~d/2%2][x-=1-d/2]='/\\'[d%2]
x+=d/2
y+=1-s):d-=c
d%=4}
puts z.map &:rstrip

An ASCII-turtle approach using the Lindenmayer representation (try here).

Big thank you to @Ventero for some more golfing.

Answer 2

Python, 282

from numpy import*
def r(n):
 x=2**n-2;b=3*x/2+1;c=x/2+1;a=zeros((x*2+2,)*2,int);a[x+1,x+1]=1;a[b,x/2]=a[x/2,b]=-1
 if n>1:s=r(n-1);a[:x,c:b]=rot90(s,3)*-1;a[c:b,:x]|=rot90(s)*-1;a[c:b,x+2:]|=s;a[x+2:,c:b]|=s
 return a
for l in r(input()):print''.join(' /\\'[c] for c in l).rstrip()

This uses a recursive approach to construct the nth order Hilbert curve out of the previous curve. The curves are represented as a 2d numpy array for better slicing and manipulation.

Here are some examples:

$ python hilbert.py
2
  /
  \/\
/\   \
 / /\/
 \ \
  \/
$ python hilbert.py
3
       \
     /\/
    /   /\
    \/\ \ \
  /\  / / /
 / /  \/  \/\
 \ \/\  /\   \
\/   / / / /\/
  /\/ /  \ \
  \   \/\ \/
   \/\   \
     / /\/
     \ \
      \/
$ python hilbert.py
4
              /
              \/\
            /\   \
           / / /\/
           \ \ \  /\
         /\/  \/  \ \
        /   /\  /\/ /
        \/\ \ \ \   \/\
      /\  / /  \ \/\   \
     / /  \/ /\/   / /\/
     \ \/\  /   /\/ /   /\
   /\/   /  \/\ \   \/\ \ \
  /   /\/ /\  / / /\  / / /
  \/\ \  / /  \/ / /  \/  \/\
/\   \ \ \ \/\   \ \/\  /\   \
 / /\/  \/   / /\/   / / / /\/
 \ \  /\  /\/  \  /\/ /  \ \
  \/  \ \ \  /\/  \   \/\ \/
    /\/ / / /   /\ \/\   \
    \   \/  \/\ \ \  / /\/
     \/\  /\  / / /  \ \
       / / /  \/  \/\ \/
       \ \ \/\  /\   \
        \/   / / / /\/
          /\/ /  \ \
          \   \/\ \/
           \/\   \
             / /\/
             \ \
              \/

Answer 3

Malsys - 234 221 characters

I smell some L-systems here :) Malsys is online L-system interpreter. This is not really serious entry but I felt like this solution is somewhat interesting.

Syntax of Malsys is not really good for golfing since it contains a lot of lengthy keywords but still, it's quite short, readable, and expressive.

lsystem HilbertCurveAscii {
    set symbols axiom = R;
    set iterations = 5;
    set rightAngleSlashMode = true;
    interpret F as DrawLine;
    interpret + as TurnLeft;
    interpret - as TurnRight;
    rewrite L to + R F - L F L - F R +;
    rewrite R to - L F + R F R + F L -;
}
process all with HexAsciiRenderer;

http://malsys.cz/g/3DcVFMWn

Interpreter: http://malsys.cz/Process

Golfed version:

lsystem H{set symbols axiom=R;set iterations=3;set
rightAngleSlashMode=1;interpret.as DrawLine;interpret+as
TurnLeft;interpret-as TurnRight;rewrite L to+R.-L.L-.R+;rewrite
R to-L.+R.R+.L-;}process H with HexAsciiRenderer;

And how about Ascii hexagonal Gosper curve? :)

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

http://malsys.cz/g/ae5v5vGB

Answer 4

APL (Dyalog Unicode), 90 bytes^SBCS

⎕∘←¨' +$'⎕r''¨↓1↓∘⍉∘⌽⍣4⊢' /\'[{3|(⊢+⍉)2@(¯1 0+3 1×s÷2)s⊢(¯.5×≢⍵)⊖(2×s←⍴⍵)↑⍵,⍨-⊖⍵}⍣⎕⊢2 2⍴0]

Try it online!

2 2⍴0 a 2x2 matrix of zeroes

{ }⍣⎕ input N and apply a function N times

⍵,⍨-⊖⍵ concatenate to the left of the matrix a vertically reversed and negated copy of itself

(2×s←⍴⍵)↑ pad with zeroes so that the dimensions (remembered as s) are twice the argument's

¯.5×≢⍵ rotate down in order to centre it vertically, sandwiched between the padding zeroes

2@(¯1 0+3 1×s÷2) put 2-s at specific locations - these are the linking slashes between smaller instances of the fractal

(⊢+⍉) add the matrix with its transposed self

3| modulo 3; we used negation, so please note that -1≡2 (mod 3) and -2≡1 (mod 3)

' /\'[ ] use the matrix elements as indices in the string ' /\'

1↓∘⍉∘⌽⍣4 trim the 1-element-wide empty margin from all sides

↓ split into lines

' +$'⎕r''¨ remove trailing spaces from each (this challenge requires it)

⎕∘←¨ output each

Answer 5

JavaScript (ES6) 313 340

Edit Some character removed using really bad practices - like global variable w instead of a return value from function H

Converting x,y position to distance d (see Wikipedia) for each x,y and verifying if the nearest positions are connected,

Test in FireFox console. Input via popup, output via console.log.

There are no trailing spaces and no newlines above or below the image. But each line is terminated with a newline, I think it's the correct way to make an Ascii art image.

n=1<<prompt(),d=n-1
H=(s,x,y)=>{for(w=0;s>>=1;)p=x&s,q=y&s,w+=s*s*(3*!!p^!!q),q||(p&&(x=s-1-x,y=s-1-y),[x,y]=[y,x])}
for(r=t='';++r<d+n;t+='\n')for(r>d?(x=r-d,f=x-1):(f=d-r,x=0),t+=' '.repeat(f),z=r-x;x<=z;)
h=H(n,y=r-x,x)|w,H(n,y,x-1),x?t+=' \\'[h-w<2&w-h<2]:0,H(n,y-1,x++),y?t+=' /'[h-w<2&w-h<2]:0
console.log(t)

Answer 6

Perl, 270 Characters

Super golfed

$_=A,%d=<A -BF+AFA+FB- B +AF-BFB-FA+>,$x=2**($n=<>)-2;eval's/A|B/$d{$&}/g;'x$n;s/A|B//g;map{if(/F/){if($r+$p==3){$y+=$p<=>$r}else{$x+=$r<2?$r-$p:$p-$r}$s[($r-1)%4>1?$x--:$x++][$r>1?$y--:$y++]=qw(/ \\)[($p=$r)%2]}else{($r+=2*/-/-1)%=4}}/./g;map{print map{$_||$"}@$_,$/}@s

Not so much golfed

$_=A,%d=<A -BF+AFA+FB- B +AF-BFB-FA+>,$x=2**($n=<>)-2;
eval's/A|B/$d{$&}/g;'x$n;
s/A|B//g;
map{if(/F/){
    if($r+$p==3){$y+=$p<=>$r}else{$x+=$r<2?$r-$p:$p-$r}
        $s[($r-1)%4>1?$x--:$x++][$r>1?$y--:$y++]=qw(/ \\)[($p=$r)%2]
    }else{
        ($r+=2*/-/-1)%=4
    }
}/./g;
map{print map{$_||$"}@$_,$/}@s

Could probably golf it down more if I better understood Perl. Uses a Lindenmayer system approach using production rules defined in line 1.