Draw a Dragon Curve

Question

You task for today: draw a dragon curve!

In case you don't know what a Dragon Curve is, here is an introductory ViHart video (Really cool, please watch!)

Your task: draw a dragon curve, iterated at least 9 times. You don't have to show iterations 1 through 9, you just have to show the final curve produced after completing (at least) 9 iterations. The curve must be drawn as straight lines connecting the points on the curve; the output should match one of the images below that shows 9 or more iterations (up to reflection, rotation, scaling, and variation in line width, line color, and background color). Your output must be large enough that the individual lines and the "boxes" that they form can be distinguished from each other; if two lines don't intersect in the curve, they shouldn't occupy the same or adjacent pixels in the output (there should be at least one pixel of the background visible between them). You can either display the image to the screen or saved the image to a file is accepted. The output must be graphical - it can't be ASCII art.

The shortest code in bytes wins, however include directives for libraries shouldn't be included in the byte count, and you may use graphics libraries or other libraries written for your language of choice if they were written before the posting.

Please include an image of the output of your program.

Skip this paragraph if you watched the video: For those of you who decided not to watch the video, the first 12 iterations of the dragon curve are shown below. For the purposes of this task, a dragon curve is a curve generated by the following rule: take the end-point of the current curve, create a second curve rotated 90 degrees around that end-point so that the end-point of the original curve is the starting point of the new curve, and join the two curves into a single curve where they meet. In the images shown below, each new iteration is generated by rotating the previous iteration 90 degrees clock-wise around the end-point each iteration. When the curve is displayed on the screen, it's not obvious which end counts as the "end-point", however when the curve is stored as a array of points, it's easy to define the "end-point" as the last point in the array.

Ascii art is appreciated, but not accepted: This is graphical output, not ascii-art.

Answer 1

x86, MSDOS, 16 bytes

I wrote this a while ago, to my knowledge the smallest routine for producing a dragon fractal. It uses no real iterations, rather plots every contained discrete pixel inside the fractal directly, showing the final image. It's included with many other tiny productions in this pack. The 16 byte version was the end of my effort to get the dragon fractal as small as possible, starting 2014 with this 32 byte production.

Hex

14 10 19 CA D1 FA 10 DE 01 D1 CD 10 B4 0C EB F0

Code

S: 
adc al,0x10
sbb dx,cx       
sar dx,0x01 
adc dh,bl
add cx,dx
int 0x10
mov ah,0x0C
jmp short S

Answer 2

Python 2/3, 169 167 150 111 98 78 Bytes

Note that the import is not included in the byte count, according to the challenge specs.

Thanks to @AlexHall for saving 39(!) bytes and @nedla2004 for another 13

from turtle import*
o=[90]
for z in o*9:o+=[90]+[-x for x in o[::-1]]
fd(5)
for i in o:rt(i);fd(5)

Starts by generating a list or right (90) and left (-90) turns, then goes through the list and moves the turtle.

Generated Output:

EDIT: If this is too boring too watch, add speed(0) right before the first fd(5). It will run the same, except the turtle will move much faster.

Answer 3

Logo, 43 bytes

for[i 1 512][fd 9 lt :i/(bitand :i -:i)*90]

Try with interpreter at http://www.calormen.com/jslogo/#

This uses the same principle as my previous ASCII art answer and the formula on at wikipedia except I reversed the direction to match the image in the question:

First, express n in the form k*(2^m) where k is an odd number. The direction of the nth turn is determined by k mod 4 i.e. the remainder left when k is divided by 4. If k mod 4 is 1 then the nth turn is R L; if k mod 4 is 3 then the nth turn is L R

bitand :i -:i finds the least significant bit of i. We divide i by this to shitft i right the required amount, giving the required odd number k. There is no need to distinguish between left and right turns; we just turn left by k*90 degrees and rely on the fact that rotation is a modulo 360 operaton to perform the modulo for us.

Output

use ht to hide turtle if required.

Output (modified)

The following shows how the curve is a single strand.

bk 6 for[i 1 512][fd 6 rt :i/(bitand :i -:i)%4*45-90 fd 3 rt :i/(bitand :i -:i)%4*45-90]

Answer 4

LindenMASM, 51 Bytes

LindenMASM was a language I created for a challenge a while ago that will forever live in the Sandbox. It makes use of the concept of Lindenmayer systems to draw things like Dragon curves, fractal plants, Sierpinski triangles, etc.

The source code is as follows:

STT
AXI FX
INC 9
SET F 0
RPL X X+YF+
RPL Y -FX-Y
END

To set this up for n = 6 for example:

STT
AXI FX
INC 6
SET F 0
RPL X X+YF+
RPL Y -FX-Y
END

This produces the following image via Python 3's turtle:

There may be a slight numbering difference for iterations, as in the Lindenmayer system the first iteration is a single line. Here's what it looks like for n = 10:

Just for fun, here's what it looks like with 15 generations (with an added instruction MOV 2 to make it a bit smaller):

Once you get up to 20 generations (with MOV 0.5) you can't really see the lines anymore, and it takes a LOT of steps to create (pairs of +- and -+ are not optimized out). Here's what you get:

^{Note that the current interpreter may present graphical issues for smaller amounts of generations, i.e. possibly not drawing to the screen. Unfortunately when this interpreter was created there were no issues, a possible change in Python 3 could have caused this or it could just be my system}

Answer 5

MATL, 26 bytes

0J1_h9:"tPJ*h]hYsXG15Y01ZG

If different scales in the two axes are accepted, the code can be reduced to 19 bytes:

0J1_h9:"tPJ*h]hYsXG

The figures below correspond to the equal-scale (26-byte) version.

The code above produces the 9-th (0-based) iteration, that is, the tenth image in the challenge:

For other values change the 9 in the code, or replace it by i to take the number as user input. For example, the result for 13 is:

Explanation

This uses a loop to gradually build an array of the steps followed by the curve in the complex plane. For example, the first two steps are 1j (up) and -1 (left).

In each iteration, the array of steps so far is copied. The copy of the array is reversed, multiplied by 1j (to rotate 90 degrees), and concatenated to the original.

After the loop, a cumulative sum of the steps gives the actual points, which are then plotted in the complex plane.

0                          % Push 0
 J1_h                      % Push array [1j, -1]. This defines the first two steps
     9:                    % Push [1, 2, ..., 9]
       "                   % For each
        t                  %   Duplicate the array of steps so far
         P                 %   Reverse
          J*               %   Multiply by 1j
            h              %   Concatenate horizontally to previous steps
             ]             % End
              h            % Concatenate with the initial 0
               Ys          % Cumulative sum
                 XG        % Plot. Complex numbers are plotted with real and imag as x and y
                   15Y0    % Push string 'equal'
                       1ZG % Set equal scale in the two axes

Answer 6

Underload, 196 bytes

()()(<svg width="99" height="147">)S(<g transform="translate):S((33,33)">)S((3,0)rotate)*a(*a(~*)*~("><path d="M0h3" stroke="#"/>)~*a(*)**:(-90)a~^~(90)a~^)*::*:**:*^S(</g>)(:*)::*:**:*^S(</svg>)S

I thought it might be interesting to try this challenge in a low-powered esolang; Underload does fairly well for a language with such a low number of commands.

The output is an SVG file with very heavily nested tags, and some golfing shortcuts. So far, I haven't found a browser that can display it (Firefox hangs for several minutes trying to load it, and both Firefox and Chromium give a blank screen). Most image processing programs can't load it either (making it hard to convert to another format), but I managed to load it in the image viewer Eye of Gnome (which is part of the default install on Ubuntu). So I took a screenshot of the image so that you can see it (the actual image has a transparent background, but you can't really screenshot transparent):

We need to specify the image size explicitly. Picking an appropriate orientation for the image, drawing everything at the minimum legal size, and doing the minimum number of iterations specified by the challenge, gives us an image that just fits into 99 pixels wide, saving a byte. It's nice when things work out like that.

The general algorithm used for drawing the image is to maintain two variables (Underload doesn't name variables, but I thought of them as x and y), both initially empty. Then we repeatedly replace (x, y) with (x, turn left and move forward, y) and (x, turn right and move forward, y). After ten iterations, both x and y hold a nine-iteration dragon curve.

There are a few micro-optimizations and Underload-specific tricks, too. In order to avoid too much messing around with the top of the stack, each loop iteration, we start by combining x and y into the function "return the string created by concatenating: x, a turn instruction, the function argument, a move-forward instruction, and y." This function only takes up one space on the stack, so we can duplicate it, call it with -90 as an argument, swap the return value under the duplicate, and call it with 90 as an argument, to get hold of new values for x and y without ever needing to touch more than the top two elements of the stack (which are by far the most commonly accessible). This function is code-generated at runtime. The generator itself is also code-generated at runtime, in order to allow it to reuse the string <g transform="translate that's also used to set the origin of the image. We generate all the open tags first, and then because all the close tags are just </g>, we can output 1024 close tags via simply repeating the string, without worrying about matching them to the open tags. (Writing numbers efficiently in Underload is an interesting problem in its own right; (:*)::*:**:* is probably the most efficient way to write 1024, though, translating to "2 to the power of (1 + 2×2) × 2".

Underload doesn't have any graphics libraries, so I produce SVG using a combination of drawing lines in a fixed position, and rotating the image around a given point; instead of turning the pen, we turn the paper. The idea is that by drawing a line, rotating the entire image, drawing another line, rotating the image again, etc., we can effectively simulate turtle graphics without having to do any arithmetic or use any graphics libraries, as all the lines are drawn in the same location. Of course, that means that we have some very heavily nested rotate-the-image tags, which confuses many SVG viewers.

Styling the image would count against the byte count, so I needed to give the minimum styling needed to display the image. This turns out to be stroke="#", which more or less translates as "the line needs to be some color"; this seems to be expanded to drawing it in black. (Normally you'd specify the color as, say, "#000".) The background is transparent by default. We don't specify a stroke width, but the choice picked by Eye of Gnome leaves everything visible.

Many Underload interpreters struggle with this program, e.g. the one on Try It Online crashes, because it generates some very large strings internally. The original online Underload interpreter works, though. (Interestingly, the very first interpreter was online, so the language was usable online before it was usable offline.)

Something I'm slightly uneasy about is that there only seem to be 1023 line segments here, and we'd expect 1024. It could be that one of the segments at the end isn't being drawn with this algorithm (it'd be drawn on the next iteration instead). If that's disqualifying, it may be possible to adapt the program, but it might well end up considerably longer. (It's not like this challenge is going to win the competition anyway; there are already several shorter entries.)

Answer 7

Mathematica 86 bytes

{1,-1}
r=Reverse;Graphics@Line@Nest[Join[l=Last@#;h=#-l&/@#,r[r@#%&/@h]]&,{{0,0},%},9]

How it works: {1,-1} Outputs {1,-1}. It basically "pushes it to the stack". This value can be recalled with %. r=Reverse basically just renames the Reverse function because I use it twice in the code. The Graphics@Line@ just takes a list of points and draws a line connecting them. The real meat of the problem happens in this code segment: Nest[Join[l=Last@#;h=#-l&/@#,r[r@#%&/@h]]&,{{0,0},%},9]. Lemme tell you - that segment is complicated as f******ck. Here's what Nest does: Nest[f,x,9]outputs the result of calling f[f[f[f[f[f[f[f[f[x]]]]]]]]].

In my code, this first argument f is: Join[l=Last@#;h=#-l&/@#,r[r@#%&/@h]]&, the second argument x is {{0,0},%} (which evaluates to {{0,0},{1,-1}}), and the third argument is n, which is just 9 (which will just apply the first argument to the second argument 9 times).

The most complex part of all is this first argument: Join[l=Last@#;h=#-l&/@#,r[r@#%&/@h]]&, which is a giant mess of almost pure syntactic sugar. I was really abusing mathematica's syntactic sugar for this one. That line of code represents mathematica's version of an anonymous function, except to shorten things I actually defined two separate anonymous functions within that anonymous function. Yep, that's legal, folks. Let's break it down.

Join takes two arguments. The first is l=Last@#;h=#-l&/@#, and the second is r[r@#%&/@h].

The first argument of Join: Inside the "main" anonymous function, # is a list of all the points at the current iteration in the curve. So l=Last@#; means "Take the point in the list of points you recieved as input, and assign that point to the variable l. The next segment, h=#-l&/@#, is a little more complex. It means "You have a function. This function takes a point as input, subtracts l from it, and returns the result. Now, apply that function to every element in the list of points you received as input to generate a list of shifted points, and assign that new list to the variable h.

The second argument of Join: r[r@#%&/@h] has literally the most complex syntax I've ever written. I can't believe any code segment could contain something like @#%&/@ - it looks like I'm cursing like a cartoon character in the middle of a program! But it's possible to break it down. Remember - r[x] takes a list of points and returns that list in reverse order. r@#%& is an anonymous function that reverses it's input, then multiplies it by the value storied in % (which is {1,-1}), and returns the result. Basically it rotates it's input 90 degrees, but in code as short as I could possibly write. Then r@#%&/@h means "Output a new list that is every point in h rotated 90 degrees."

So overall, Join[l=Last@#;h=#-l&/@#,r[r@#*%&/@h]]& is a function that takes a list of points as an input, and adds on that same list of points rotated 90 degrees to get the next iteration of the curve. This is repeated 9 times to get the dragon curve. Then it's the resulting list of points is drawn to the screen as a line. And the output:

Answer 8

Python 2, 43 bytes

This answer is 43 bytes not including the import statement and it's largely based on Level River St's Logo answer and their use of i/(i&-i) in their code. Try it online at trinket.io

from turtle import*
for i in range(1,513):fd(9);rt(90*i/(i&-i))

Here is a picture of the output.

Answer 9

Mathematica, 56 55 bytes

Graphics@Line@AnglePath[Pi/2JacobiSymbol[-1,Range@512]]

Explanation: OEIS A034947

Just for fun, here is a colored version of the 19th iteration.

Answer 10

Mathematica, 63 bytes

Using AnglePath

Graphics@Line@AnglePath[Pi/2Nest[Join[#,{1},-Reverse@#]&,{},9]]

Answer 11

HTML + JavaScript, 182

<canvas id=C></canvas><script>c=C.getContext("2d")
C.width=C.height=400
s=n=9
x=y=200
for(i=d=0;i<=1<<n;d+=++i/(i&-i))
c.lineTo(x,y),
d&1?y+=d&2?s:-s:x+=d&2?-s:s
c.stroke()</script>

Answer 12

Haskell + diagrams, 179 bytes

import Diagrams.Prelude
import Diagrams.Backend.SVG
d 1=hrule 1<>vrule 1
d n=d(n-1)<>d(n-1)#reverseTrail#rotateBy(1/4)
main=renderSVG"d"(mkWidth 99)$strokeT(d 9::Trail V2 Double)

Output is a 99 pixels wide svg file with transparent background (an image 9 pixels wide would have a stroke too thick to recoqnize anything). Here it is rescaled and composed over a white background:

Answer 13

tosh, 518 bytes

tosh is Scratch, but with text instead of blocks. At 518 bytes, this answer is probably even worse than Java.

This answer uses the same logic as @Theo's Python answer, but with strings of "L" and "R" instead of numbers, as Scratch's (and thus tosh's) list capabilities are awful.

You can run it as a Scratch project here. (tosh compiles to Scratch projects)

when flag clicked
set path to "R"
go to x: -50 y: 100
point in direction 90
pen down
set pen size to 2
clear
repeat 9
    set path copy to path
    set path to join (path) "R"
    set i to length of path copy
    repeat length of path copy
        if letter i of path copy = "R" then
            set path to join (path) "L"
        else
            set path to join (path) "R"
        end
        change i by -1
    end
end
set i to 0
repeat length of path
    change i by 1
    if letter i of path = "R" then
         turn cw 90 degrees
    else
         turn ccw 90 degrees
    end
    move 7 steps
end  

Explanation:

when flag clicked
set path to "R"
go to x: -50 y: 100
point in direction 90
pen down
set pen size to 2
clear

This first part makes the program run when the green flag is clicked (when flag clicked), sets the path variable to "R", and gets the sprite and stage in the proper state to be ready to draw.

repeat 9
    set path copy to path
    set path to join (path) "R"
    set i to length of path copy
    repeat length of path copy
        if letter i of path copy = "R" then
            set path to join (path) "L"
        else
            set path to join (path) "R"
        end
        change i by -1
    end
end

Now we get to the path generation code. It uses the same logic as @Theo's Python answer, except with strings of "R" and "L" instead of numbers, and we use nested loops instead of list comprehensions.

set i to 0
repeat length of path
    change i by 1
    if letter i of path = "R" then
         turn cw 90 degrees
    else
         turn ccw 90 degrees
    end
    move 7 steps
end  

Finally, we draw the path by going through each letter of the path variable and turning left or right depending on the letter.