Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Hilbert curve is a space filling fractal that can be represented as a Lindenmayer system with successive generations that look like this:
Hilbert curve
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.

share|improve this question
    
I've just noticed that the question says "non-negative integer n". What should the output be if the input is 0? /? –  Peter Taylor Jul 21 at 20:10
    
@PeterTaylor Sorry, I meant positive. –  Calvin's Hobbies Jul 21 at 20:15

5 Answers 5

up vote 8 down vote accepted

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.

share|improve this answer
    
Golfed this a bit more, hope you don't mind: ideone.com/kvcPWT - the .map(&:rstrip) had to be added to fulfill the "no trailing spaces" requirement. –  Ventero Jul 22 at 7:12
    
@Ventero Thank you. Hope you don't mind that I took your solution - you may even discard the parantheses around the map argument. –  Howard Jul 22 at 7:25
    
Ah, of course! I also just realized that it's possible to inline the definition of x and shorten the assignment to y and d, for a total of 205 characters (see the same link as before). –  Ventero Jul 22 at 7:27

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
              /
              \/\
            /\   \
           / / /\/
           \ \ \  /\
         /\/  \/  \ \
        /   /\  /\/ /
        \/\ \ \ \   \/\
      /\  / /  \ \/\   \
     / /  \/ /\/   / /\/
     \ \/\  /   /\/ /   /\
   /\/   /  \/\ \   \/\ \ \
  /   /\/ /\  / / /\  / / /
  \/\ \  / /  \/ / /  \/  \/\
/\   \ \ \ \/\   \ \/\  /\   \
 / /\/  \/   / /\/   / / / /\/
 \ \  /\  /\/  \  /\/ /  \ \
  \/  \ \ \  /\/  \   \/\ \/
    /\/ / / /   /\ \/\   \
    \   \/  \/\ \ \  / /\/
     \/\  /\  / / /  \ \
       / / /  \/  \/\ \/
       \ \ \/\  /\   \
        \/   / / / /\/
          /\/ /  \ \
          \   \/\ \/
           \/\   \
             / /\/
             \ \
              \/
share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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)
share|improve this answer
    
You could save some characters by using alert instead of console.log. You also have an extra space after the for on the fourth line, and you should be able to get rid of that last line break. –  Bob Jul 22 at 0:43
    
@Bob yes in fact I can save some 15 characters more, I gave up seeing I im over 300 anyway. I don't like using 'alert' because the image is completely unrecognizable without a fixed pitch font –  edc65 Jul 22 at 4:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.