31
\$\begingroup\$

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.

\$\endgroup\$
0

6 Answers 6

12
\$\begingroup\$

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
              /
              \/\
            /\   \
           / / /\/
           \ \ \  /\
         /\/  \/  \ \
        /   /\  /\/ /
        \/\ \ \ \   \/\
      /\  / /  \ \/\   \
     / /  \/ /\/   / /\/
     \ \/\  /   /\/ /   /\
   /\/   /  \/\ \   \/\ \ \
  /   /\/ /\  / / /\  / / /
  \/\ \  / /  \/ / /  \/  \/\
/\   \ \ \ \/\   \ \/\  /\   \
 / /\/  \/   / /\/   / / / /\/
 \ \  /\  /\/  \  /\/ /  \ \
  \/  \ \ \  /\/  \   \/\ \/
    /\/ / / /   /\ \/\   \
    \   \/  \/\ \ \  / /\/
     \/\  /\  / / /  \ \
       / / /  \/  \/\ \/
       \ \ \/\  /\   \
        \/   / / / /\/
          /\/ /  \ \
          \   \/\ \/
           \/\   \
             / /\/
             \ \
              \/
\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ventero
    Jul 22, 2014 at 7:12
  • \$\begingroup\$ @Ventero Thank you. Hope you don't mind that I took your solution - you may even discard the parantheses around the map argument. \$\endgroup\$
    – Howard
    Jul 22, 2014 at 7:25
  • \$\begingroup\$ 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). \$\endgroup\$
    – Ventero
    Jul 22, 2014 at 7:27
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 90 bytesSBCS

⎕∘←¨' +$'⎕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

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bob
    Jul 22, 2014 at 0:43
  • \$\begingroup\$ @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 \$\endgroup\$
    – edc65
    Jul 22, 2014 at 4:57
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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