ASCII Dragon's Curve
Ruby, 239 201 bytes
This is a lambda function which should be called in the same manner as the one in the ungolfed version.
Golfing improvements include: assignment of 8<<n/2
to a variable for re-use; upto
loop instead of each
loop; ternary operator instead of if..else..end
; use of [y,y+=d].max
to calculate where to print the |
; use of ?_
and ?|
instead of the equivalent '|'
and '_'
; and elimination of redundant %4
(thanks Sp3000.)
->n{a=Array.new(m=8<<n/2){" "*m}
p=q=1+x=y=m/2
r=3
1.upto(1<<n){|i|d=(r&2)-1
r%2>0?(a[y][x+=d]=?_
x+=d):(a[[y,y+=d].max][x]=?|
p=x<p ?x:p
q=x>q ?x:q)
r+=i/(i&-i)}
a.delete(a[0])
puts a.map{|e|e[p..q]}}
It relies on the following formula from Wikipedia:
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; if k mod 4 is 3 then the nth turn is L.
Wikipedia gives the following code:
There is a simple one line non-recursive method of implementing the above k mod 4 method of finding the turn direction in code. Treating turn n as a binary number, calculate the following boolean value:
bool turn = (((n & −n) << 1) & n) != 0
I improved this to i/(i&-i)%4
which uses the same technique of using the expression i&-i
to find the least significant digit but my expression gives 1 (for left turn)or 3 (for right turn) directly, which is handy as I track direction as a number 0..3
(in order north, west, south, east for golfing reasons.)
Ungolfed original in test program
f=->n{
a=Array.new(8<<n/2){" "*(8<<n/2)} #Make an array of strings of spaces of appropriate size
p=q=1+x=y=4<<n/2 #set x&y to the middle of the array, p&q to the place where the underscore for n=0 will be printed.
r=3 #direction pointer, headed East
(1..1<<n).each{|i| #all elements, starting at 1
d=(r&2)-1 #d is +1 for East and South, -1 for West and North
if r%2>0 #if horizontal
a[y][x+=d]='_' #move cursor 1 position in direction d, print underscore,
x+=d #and move again.
else #else vertical
a[(y+([d,0].max))][x]='|' #draw | on the same line if d negative, line below if d positive
y+=d #move cursor
p=x<p ?x:p #update minimum and maximum x values for whitespace truncation later
q=x>q ?x:q #(must be done for vertical bars, to avoid unnecesary space in n=0 case)
end
r=(r+i/(i&-i))%4 #update direction
}
a.delete(a[0]) #first line of a is blank. delete all blank lines.
puts a.map!{|e|e[p..q]} #use p and q to truncate all strings to avoid unnecessary whitespace to left and right.
}
f.call(0)
f.call(2)
f.call(3)
f.call(11)
Python 2, 270 222 bytes
y=X=Y=0
i=m=x=1
D={}
k=2**input()
while~k+i:j=Y+(y>0);s={2*X+x};D[j]=D.get(j,s)|s;m=min(m,*s);Y+=y;X+=x;exec i/(i&-i)*"x,y=y,-x;";i+=1
for r in sorted(D):print"".join(" | _"[(n in D[r])+n%2*2]for n in range(m,max(D[r])+1))
Now using the formula for the nth turn. I saw the (((n & −n) << 1) & n)
formula on Wikipedia, but didn't realise how useful it was until I saw it in @steveverrill's answer. I actually drop the %4
as well, so there's a lot of rotating going on, making larger inputs take a while.
Side remark: This isn't graphical output, but here's some golfed turtle code:
from turtle import*
for i in range(1,2**input()+1):fd(5);lt(i/(i&-i)*90)
C#, 337 bytes
There's a bit of rules abuse here. There's no restriction on leading space. Unfortunately, the canvas is finite, so there is an upper limit for n.
Indented for clarity:
using C=System.Console;
class P{
static void Main(string[]a){
int n=int.Parse(a[0]),d=2,x=250,y=500;
var f="0D";
while(n-->0)
f=f.Replace("D","d3t03").Replace("T","10d1t").ToUpper();
C.SetBufferSize(999,999);
foreach(var c in f){
n=c&7;
d=(d+n)%4;
if(n<1){
var b=d%2<1;
x+=n=b?1-d:0;
y+=b?0:2-d;
C.SetCursorPosition(x*2-n,y+d/3);
C.Write(b?'_':'|');
}
}
}
}