23
\$\begingroup\$

Given an integer n output the nth iteration of the Hilbert Curve in ASCII using the characters _ and |.

Here are the first 4 iterations:

n=1
 _ 
| |

n=2
 _   _ 
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _ 
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_ 
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _ 
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_ 
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _ 
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_ 

Clarifications

  • My question is similar to Draw the Hilbert Curve and Draw the Hilbert curve using slashes.
  • The conversion between underscores (_) and vertical bars (|) is u=2*v-1 where u is the number of _s and v is the number of |s.
  • To maintain consistency with my original post the curve must start and end at the bottom.
  • You can have a full program or a function.
  • Output to stdout (or something similar).
  • You can have leading or trailing white-spaces, the output just needs to line up so that it looks like the examples.
  • This is code-golf so shortest answer in bytes wins.
\$\endgroup\$
  • 3
    \$\begingroup\$ Could you please include a definition of the Hilbert Curve in you post, and the exact specifications for how the ASCII version is constructed? \$\endgroup\$ – Loovjo Dec 24 '16 at 11:15
  • \$\begingroup\$ @Bobas_Pett: Not kolmogorov-complexity \$\endgroup\$ – shooqie Dec 24 '16 at 11:20
  • \$\begingroup\$ @shooqie there's some debate on that on meta \$\endgroup\$ – trichoplax Dec 24 '16 at 11:25
  • \$\begingroup\$ @Loovjo I added in a point about the lengths of underscores (_) and vertical bars (|) under "Clarifications", if more information or a rigorous definition is still needed please tell me. \$\endgroup\$ – Bobas_Pett Dec 24 '16 at 13:09
  • \$\begingroup\$ @shooqie i removed the tag \$\endgroup\$ – Bobas_Pett Dec 24 '16 at 13:12
5
\$\begingroup\$

Befunge, 444 368 323 bytes

&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

Try it online!

The typical approach to drawing the Hilbert Curve is to follow the path as a series of strokes and turns, rendering the result into a bitmap or some area of memory, and then writing out that rendering when the path is complete. This is just not feasible in Befunge when we only have 2000 bytes of memory to work with, and that includes the source of the program itself.

So the approach we've taken here is to come up with a formula that tells us exactly which character to output for a given x,y coordinate. To understand how this works, it's easiest to ignore the ASCII rendering to start with, and just think of the curve as made up of box characters: , , , , , and .

When we look at the curve like that, we can immediately see that right hand side is an exact mirror of the left hand side. Characters on the right can simply be determined by looking up their partner on the left, and reflecting it horizontally (i.e. occurrences of and are swapped, as are and ).

Level 3 Hilbert Curve showing the reflection across the vertical axis

Then looking at the bottom left corner, again we can see that the lower half is a reflection of the top half. Thus the characters on the bottom are simply determined by looking up their partner above, and reflecting it vertically (i.e. occurrences of and are swapped, as are and ).

Level 3 Hilbert Curve showing the reflection across the horizontal axis in the bottom left corner

The remaining half of this corner is a little less obvious. The right hand block can be derived from a vertical reflection of the block diagonally adjacent to it.

Level 3 Hilbert Curve showing how the top right block of the bottom left corner can be derived

And the left hand block can be derived from a vertical reflection of the block in the very top left of the full curve.

Level 3 Hilbert Curve showing how the top left block of the bottom left corner can be derived

At this point, all we're left with is the top left corner, which is just another Hilbert Curve one iteration lower. In theory, we should now just need to repeat the process again, but there's a bit of a catch - at this level, the left and right halves of the block aren't exact mirrors of each other.

So at anything other than the top level, the bottom corner characters need to be handled as a special case, where the character is reflected as , and the character is reflected as .

Level 3 Hilbert Curve showing how the top left block of the bottom left corner can be derived

But other than that, we really can just repeat this process recursively. At the last level we hardcode the top left character as , and the character below it as .

Sequence of images showing how the remaining parts of the curve are derived

Now that we have a way to determine the shape of the curve at a particular x,y coordinate, how do we translate that into the ASCII rendering? It's actually just a simple mapping that translates each possible tile into two ASCII characters.

  • becomes  _ (space plus underscore)
  • becomes    (two spaces)
  • becomes |_ (vertical bar plus underscore)
  • becomes (vertical bar plus space)
  • becomes (again a vertical bar plus space)
  • becomes __ (two underscores)

This mapping isn't intuitive at first, but you can see how it works when looking at two corresponding renderings side by side.

Level 2 Hilbert Curve rendered as ASCII art and with box characters

And that's basically all there is to it. Actually implementing this algorithm in Befunge is another problem altogether, but I'll leave that explanation for another time.

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

C, 267 bytes

const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

Try it online!

h() uses recursion to generate the strokes of hlibert curve. t() only prints out the stroke character if the pen position p is equal to the current output position q.

This is inefficient but simple.

If the curve starts at top-left, the code can be reduced to 256 bytes.

\$\endgroup\$
  • \$\begingroup\$ Suggest puts("") instead of putchar(10) and "..."+l*8+d*2 instead of &"..."[l*8+d*2] and n--?h(d+r...-r,n):0 instead of n--&&(h(d+r...-r,n)) \$\endgroup\$ – ceilingcat Jul 21 '18 at 23:25

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.