12
\$\begingroup\$

A Hilbert Curve is a type of space-filling curve, and it basically maps a line to a plane. Each point in the line corresponds to just one point in the plane, and each point in the plane corresponds to just one point on the line. Shown are iterations 0 through 4 of the Hilbert Curve:

Iterations 0 up to 4:

The objective of this task: Write code that draws the fourth iteration of the Hilbert Curve, as defined above. Your code should be complete - in other words, if you create a function to draw the Hilbert Curve, your code must call that function. The output can either be displayed directly on the screen, or you can write the output to an image file. The curve may be rotated or flipped, but lines must intersect at right angles and the output cannot be stretched. ASCII art is appreciated but will not be accepted. Shortest code in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Is the number of times an input? Or can we choose any value at least 4? \$\endgroup\$ – Luis Mendo Nov 18 '16 at 17:28
  • \$\begingroup\$ Is ASCII art considered graphical? \$\endgroup\$ – Gabriel Benamy Nov 18 '16 at 17:39
  • \$\begingroup\$ No; sorry - then it'd be a duplicate of another question \$\endgroup\$ – J. Antonio Perez Nov 18 '16 at 17:40
  • \$\begingroup\$ @JorgePerez Can the curve have a different orientation? Like a vertically flipped or 90-deg rotate version of your examples \$\endgroup\$ – Luis Mendo Nov 18 '16 at 17:41
  • \$\begingroup\$ Yes! Although the overall shape must still be square \$\endgroup\$ – J. Antonio Perez Nov 18 '16 at 17:42
7
\$\begingroup\$

R, 90 bytes

n=scan();a=1+1i;b=1-1i;z=0;for(k in 1:n)z=c((w<-1i*Conj(z))-a,z-b,z+a,b-w)/2;plot(z,t="s")

Shameless R-port of the the algorithm used in the link posted by @Luis Mendo.

For n=5 we get:

enter image description here

\$\endgroup\$
7
\$\begingroup\$

MATL, 39 38 bytes

O5:"tZjJ*JQ-wJq+t2+&y2j+_v2/]XG25Y01ZG

This takes the number of iterations as input. If you want to hard-code it, replace i by the number.

The program is a port of the Matlab code by Jonas Lundgren shown here.

The result is shown below. You can also try it at MATL Online! It takes a couple of seconds to produce the output. This compiler is experimental; you may need to refresh the page and press "Run" again if it doesn't initially work.

enter image description here

Explanation

O          % Push 0. This is the initial value of "z" in the original code
5:"        % Do 5 times
  t        %   Duplicate
  Zj       %   Complex conjugate
  J*       %   Multiply by 1j (imaginary unit). This is "w" in the original code
  JQ-      %   Subtract 1+1j
  w        %   Swap: brings copy of "z" to top
  Jq+      %   Add 1-1j
  t        %   Duplicate
  2+       %   Add 2
  &y       %   Duplicate the third element from top
  2j+_     %   Add 2j and negate
  v        %   Concatenate the three matrices vertically
  2/       %   Divide by 2
]          % End
XG         % Plot (in complex plane). The numbers are joined by straight lines
25Y0       % Push string 'square'
1ZG        % Make axis square
\$\endgroup\$
  • \$\begingroup\$ Could you explain how your code works? \$\endgroup\$ – J. Antonio Perez Nov 18 '16 at 18:54
  • \$\begingroup\$ The algorithm is exactly as in the link. But I will add an explanation \$\endgroup\$ – Luis Mendo Nov 18 '16 at 18:55
  • \$\begingroup\$ @Jorge Explanation added \$\endgroup\$ – Luis Mendo Nov 18 '16 at 19:03
  • \$\begingroup\$ omg, the one you based yours of is so much easier than mine =/ \$\endgroup\$ – flawr Nov 18 '16 at 19:11
  • \$\begingroup\$ @flawr All credit to Jonas Lundgren :-) \$\endgroup\$ – Luis Mendo Nov 18 '16 at 19:12
6
\$\begingroup\$

MATLAB, 264 262 161 bytes

This works still very much the same, except that we basically calculate the "derivative" of the hilbert curve, that we then "integrate" via `cumsum``. This reduces the code size by quite a bunch of bytes.

function c;plot(cumsum([0,h(1,1+i,4)]));axis equal;end function v=h(f,d,l);v=d*[i*f,1,-i*f];if l;l=l-1;D=i*d*f;w=h(f,d,l);x=h(-f,D,l);v=[x,D,w,d,w,-D,-x];end;end

Old version

This is just a plain recursive approach. I used complex numbers to store vectorial information for simplicity. You can change the curve at the part h(0,1,1+i,4). The first argument p=0 is the initial position, the second argument f is a flag for the orientation (+1 or -1), the third argument d is the direction/rotation in which the curve should be drawn and the fourth one l is the recursion depth.

function c;hold on;h(0,1,1+i,4);axis equal;end function p=h(p,f,d,l);q=@plot;if l;l=l-1;d=i*d*f;p=h(p,-f,d,l);q(p+[0,d]);p=p+d;d=-i*d*f;p=h(p,f,d,l);q(p+[0,d]);p=p+d;p=h(p,f,d,l);d=-i*d*f;q(p+[0,d]);p=p+d;p=h(p,-f,d,l);else;q(p + d*[0,i*f,1+i*f,1]);p=p+d;end;end

This is what it looks like in older versions:

This is what it looks like in 2015b:

-->
\$\endgroup\$
  • 1
    \$\begingroup\$ In Matlab R2015b it plots in colors <3 \$\endgroup\$ – Luis Mendo Nov 18 '16 at 19:16
  • \$\begingroup\$ Haha so cool :) \$\endgroup\$ – flawr Nov 18 '16 at 19:20
  • \$\begingroup\$ @LuisMendo I was now able to golf it a bit with the cumsum idea which is just brilliant! \$\endgroup\$ – flawr Nov 18 '16 at 20:36
3
\$\begingroup\$

MATLAB/Octave, 202 bytes

I noticed the version @LuisMendo linked is was way shorter than previous "handmade" solution but uses an entirely different approach. I'm posting a golfed version here now as a CW:

This version is based on the Lindenmayer system approach:

A=zeros(0,2);B=A;C=A;D=A;n=[0,1];e=[1,0];for k=1:4;a=[B;n;A;e;A;-n;C];b=[A;e;B;n;B;-e;D];c=[D;-e;C;-n;C;e;A];D=[C;-n;D;-e;D;n;B];A=a;B=b;C=c;end;A=[0,0;cumsum(A)];plot(A(:,1),A(:,2));axis off;axis equal

enter image description here

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 266 ... 233 232 bytes

A SVG rendering of the Hilbert Curve.

document.write('<svg><path fill=none stroke=red d="M8 8'+(f=(i,s='2',d=x=y=8)=>i?f(i-1,s.replace(/./g,c=>[32410401423,,10432423401][+c]||c)):s.replace(/./g,c=>c-4?(d+=c&1&&c-2,''):`L${x+=4-'4840'[d&=3]} ${y+=4-'0484'[d]}`))(5)+'">')

Saved 1 byte thanks to Neil

\$\endgroup\$
  • 1
    \$\begingroup\$ Try fill=none \$\endgroup\$ – Neil Jan 8 '17 at 17:11
2
\$\begingroup\$

Python 3, 177 175 171 bytes

A simple implementation of the Lindenmayer system for the Hilbert curve. Golfing suggestions welcome!

Edit: -2 bytes thanks to Kade. -3 bytes from restructuring how the Hilbert curve is built. -1 byte with thanks to ETHproductions.

from turtle import*;s="a";exec('t=""\nfor c in s:t+=c>"F"and"+-abFF-+baFFba-+FFab+-"[c<"b"::2]or c\ns=t;'*5)
for c in s:
 if"-">c:rt(90)
 elif"F">c:lt(90)
 elif"a">c:fd(9)

enter image description here

Ungolfing

import turtle

hilbert_seq = "a"

for _ in range(5):
    new_seq = ""
    for char in hilbert_seq:
        if char == "a":
            new_seq += "-bF+aFa+Fb-"
        elif char == "b":
            new_seq += "+aF-bFb-Fa+"
        else:
            new_seq += char
    hilbert_seq = new_seq

for char in hilbert_seq:
    if char == "F":
        turtle.forward(9)
    elif char == "+":
        turtle.right(90)
    elif char == "-":
        turtle.left(90)
\$\endgroup\$
  • \$\begingroup\$ Changing how you form t can save two bytes: t+=[[c,"+AF-BFB-FA+"][c=="B"],"-BF+AFA+FB-"][c=="A"]. Since the pattern is almost the same for the two of them I wonder if there's some way to use that.. \$\endgroup\$ – Kade Dec 6 '16 at 18:43
  • \$\begingroup\$ Perhaps change if c>"E": to if"E"<c: to save a byte? \$\endgroup\$ – ETHproductions Dec 7 '16 at 4:10
1
\$\begingroup\$

MSWLogo (Version 6.5b), 136 bytes

Based on the final Hilbert curve program here.

to h :n :a :l
if :n=0[stop]
rt :a
h :n-1(-:a):l
fd :l
lt :a
h :n-1 :a :l
fd :l
h :n-1 :a :l
lt :a
fd :l
h :n-1(-:a):l
rt :a
end
h 5 90 9

A function h is defined, which takes number of iterations :n (1-based), angle :a, length :l. It is recursive, calling a lower iteration of itself with the angle :a negated in two instances to get the orientation correct.

  • rt :a, lt :a rotate the turtle (triangle thingy whose path is traced) right, left by :a degrees.
  • fd :l moves the turtle forward by :l steps.

Finally, the function is called: h 5 90 9. The turtle can be hidden for an extra 2 bytes, ht.

(5-1)-th iteration

\$\endgroup\$
  • \$\begingroup\$ What's happening on the top left corner? \$\endgroup\$ – flawr Nov 19 '16 at 9:43
  • \$\begingroup\$ @flawr That's the turtle. It can be hidden by appending ht. \$\endgroup\$ – u54112 Nov 19 '16 at 9:43
1
\$\begingroup\$

Mathematica 128 Bytes

Graphics[Line@AnglePath[Total/@Split[Cases[Nest[#/.{-2->(s=##&@@#&)[l={-1,2,0,1,-2,0,-2,1,0,2,-1}],2->s@-l}&,{-2},4],-1|1|0],#!=0&][[;;-2,;;-2]]*Pi/2]]

Replace the 4 above with a different number of iterations if you like.

Done as a Lindenmayer system with integer sequences rather than string sequences so the second production rule is just the negative of the first rule. This version is 151 bytes.

The port of Jonas Lundgren's MATLAB code is only 128 bytes.

z=0;Graphics[Line[{Re[#],Im[#]}&/@Flatten[Table[w=I*Conjugate[z];z={w-(a=1+I),z-(b=1-I),z+a,b-w}/2,{k,5}][[5]]]],AspectRatio->1]

I see that in a future version of Mathematica, this may become really short, something like:

Graphics@HilbertCurve[n]

http://mathworld.wolfram.com/HilbertCurve.html

\$\endgroup\$
1
\$\begingroup\$

LindenMASM, 63 Bytes

Another question with a LindenMASM answer? Awesome!

STT
AXI A
INC 5
SET F 0
RPL A -BF+AFA+FB-
RPL B +AF-BFB-FA+
END

Once again, due to some drawing bugs with Python's turtle, sometimes when you run this the whole drawing isn't there. However you can see it does actually work:

4th iteration

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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