Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

...so this is a challenge to make me a tree.

Produce a program or function called tree which takes a single integer argument, N and draws a Pythagorean Tree N levels deep, where level 0 is just the trunk.

Each junction of the tree should place the vertex of the triangle at a random point on the perimeter (this point should be uniformly distributed over at least 5 equally spaced points, or uniformly over the whole semicircle).

Optionally your tree may be 3d, be colourful, or be lit according to the time of day. However, this is code-golf, so the smallest file wins.

EDIT: I'll shut the contest and accept the smallest answer when it's a week old

share|improve this question
    
Appears to be a duplicate: codegolf.stackexchange.com/questions/18785/… –  David Carraher Mar 29 at 21:17
    
False. I'm after a different algorithm :) –  ali0sha Mar 29 at 21:18
    
Ok. Fair enough. You may want to consider retitling your submission to "Pythagorean Tree". –  David Carraher Mar 29 at 21:33
    
I like trains? :) –  tomsmeding Apr 25 at 11:08
add comment

4 Answers 4

up vote 14 down vote accepted

Mathematica, 246 234 221 characters

g[n_,s_:1]:={p=RandomReal[q=Pi/2],r=##~Rotate~(o={0,0})&,t=Translate}~With~If[n<0,{},Join[#~t~{0,s}&/@(#~r~p&)/@g[n-1,s*Cos@p],t[#,s{Cos@p^2,1+Sin[2p]/2}]&/@(r[#,p-q]&)/@g[n-1,s*Sin@p],{Rectangle[o,o+s]}]]
f=Graphics@g@#&

This is certainly not the most elegant/shortest way to do this.

Usage: f[8]

enter image description here

And here are example outputs for f[6] and f[10] respectively.

enter image description here enter image description here

Somewhat ungolfed:

g[n_, s_:1] := With[{p},
  r = Rotate;
  t = Translate;
  p = RandomReal[q = Pi/2];
  If[n < 0, {},
   Join[
    (t[#, {0, s}] &) /@ (r[#, p, {0, 0}] &) /@ g[n - 1, s*Cos[p]],
    (t[#, s {Cos[p]^2, 1 + Sin[2 p]/2}] &) /@ (r[#, p - q, {0, 0}] &) /@
       g[n - 1, s*Sin[p]],
    {Rectangle[{0, 0}, {s, s}]}
    ]
   ]
  ]
f = Graphics@g[#] &
share|improve this answer
    
That is quite impressive. Shame I don't have mathematica to test it - could you add another couple of example outputs? –  ali0sha Mar 29 at 21:49
    
@ali0sha see edit –  Martin Büttner Mar 29 at 21:57
    
You don't need Show in there, and Module is also unnecessary. –  swish Mar 30 at 7:32
    
@swish Thanks for the Show hint, but how can I get rid of Module? If I don't declare p local, it will be overwritten in the recursive calls, so I couldn't do both calls with the same p, right? –  Martin Büttner Mar 30 at 10:41
    
@m.buettner Maybe you can use Block, which is shorter than Module. –  alephalpha Mar 30 at 11:43
show 3 more comments

CFDG, 134 characters

This one isn't exactly valid, because you cannot limit the recursion depth. But the problem just calls for a solution in this one. :)

startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5]t[trans 0 1 c(w) d(w)]t[trans c(w) d(w) 1 1]}

The results look something like this

enter image description here

For another 46 characters (180 characters in total), you can even colour it in:

startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5 h 25 sat 1 b .2]t[trans 0 1 c(w) d(w) b .08 .8 h 2.2]t[trans c(w) d(w) 1 1 b .08 .8 h 2.2]}

enter image description here

share|improve this answer
    
I know this isn't fully ontopic, but how would a version look if instead of "white noise", you used "brown noise" as angles? –  ɐɔıʇǝɥʇuʎs Mar 30 at 15:47
    
@Synthetica you mean with more angles around 90° and less at 0 and 180? –  Martin Büttner Mar 30 at 16:36
    
@Synthetica Similar to this. I couldn't implement actual random-walk noise, because that requires taking an input parameter (the last random value), adjusting it and passing it on. This would make the grammar context-sensitive and is hence not supported by CFDG. I slightly faked it, by simply pushing the random values a bit more towards π/2 using a simple cubic function on the random sample. –  Martin Büttner Mar 30 at 18:57
    
I think that your imgur link is broken, and also much though I enjoy the colour and shape, I think I have to disqualify this one for the reason you mentioned –  ali0sha Apr 2 at 20:04
    
@ali0sha you're right, here is the fixed link. Disqualifying this one is absolutely fair, I just wanted to share Context Free Art with some people and it seemed like a neat approach for the problem. ;) ... Well I've still got the Mathematica answer ^^ –  Martin Büttner Apr 2 at 20:28
add comment

Postscript, 322 270

Edit: It appears that realtime can't be used as proper random generator seed. Therefore, we'll use environment variable for this purpose and run the program like that:

gs -c 20 $RANDOM -f tree.ps

or

gswin32c -c 20 %RANDOM% -f tree.ps

Now our trees are less predictable. 14 bytes are added to total count. Other changes: 1) Program argument is now passed on command line. 2) No explicit iteration counter - stack size serves for this purpose (left branch rotation angle is stored on stack, to draw right branch, later). 3) There's no named variable for required depth - stack size is its offset, on stack. It's left there on exit, i.e. it is not consumed.

srand
250 99 translate
50 50 scale
/f{
    count
    dup index div dup 1 le{
        0 exch 0 setrgbcolor
        0 0 1 1 rectfill
        0 1 translate
        rand 5 mod 1 add 15 mul
        gsave
        dup rotate
        dup cos dup scale
        f
        grestore
        dup cos dup dup mul
        exch 2 index sin mul translate
        dup 90 sub rotate
        sin dup scale 1
        f
        pop
    }{pop}ifelse
}def
f

I think it's pretty obvious - graphics state is prepared and f procedure is called recursively for each consecutive level of depth, twice - for 'left' and 'right' branches. Working with rectangle of 1x1 size (see original scale) saves the trouble of multiplying by side length. Angle of rotation of left branch is randomized - one of 5 random equally spaced divisions is used - I think it prevents possible ugly cases for uniform randomness.

It might be slow for required depth of more than 20 or so.

Next is golfed version, using ASCII-encoded binary tokens (see luser droog's answer from linked topic). Note, cos, sin, rand can not use this notation.

/${{<920>dup 1 4 3 roll put cvx exec}forall}def srand 250 99<AD>$ 50 50<8B>$/f{count(8X68)$ 1 le{0(>)$ 0<9D>$ 0 0 1 1<80>$ 0 1<AD>$ rand 5 mod 1 add 15<~CecsG2u~>$ cos<388B>$ f(M8)$ cos(88l>)$ 2(X)$ sin<6CAD38>$ 90<A988>$ sin<388B>$ 1 f pop}{pop}(U)$}def f

.

/${{<920>dup 1 4 3 roll put cvx exec}forall}def
srand
250 99<AD>$
50 50<8B>$
/f{
count(8X68)$
1 le{
0(>)$ 0<9D>$
0 0 1 1<80>$
0 1<AD>$
rand 5 mod 1 add 15 
<~CecsG2u~>$
cos<388B>$ 
f
(M8)$
cos(88l>)$
2(X)$ sin<6CAD38>$
90<A988>$ sin<388B>$
1
f
pop
}{pop}(U)$
}def
f

enter image description here

share|improve this answer
    
I think the style here is that command line arguments need to be added so this scores 344... I have to say that even by codegolf standards this is pretty impressively foreign-looking. How far could you get it with binary tokens? You're not far off Mathematica surely –  ali0sha Apr 2 at 20:02
    
@ali0sha, -dGraphicsAlphaBits is a flag to anti-alias output to prevent jagged edges of larger squares, it can be omitted (or 'hidden' in e.g. environment variable). Some people may like it more without this flag (tree leaves get more 'volume'). Well, those 20 bytes not that much important. I'd say 20-25% off using ascii-encoded binary tokens (judging by linked topic answer). Maybe 50% off without ascii-encoding, 2 binary bytes per system name token. Will look like some usually winning languages ;) –  VadimR Apr 2 at 22:55
    
I think you should do it - make it a bit more competitive in here :) –  ali0sha Apr 3 at 6:15
add comment

Coffeescript 377B 352B

I feel dirty writing coffeescript but I can't find a decent drawing package for python3 :-/

Q=(n)->X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=400;M=Math;T=[[175,400,50,i=0]];S=M.sin;C=M.cos;while [x,y,l,a]=T[i++]
 X.save();X.translate x,y;X.rotate -a;X.fillRect 0,-l,l,l;X.restore();T.push [e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2] if i<2**n

Javascript 393B 385B

Slightly prettier in javascript and I'm much happier with the for-loop but without the [x,y,z]=A syntax I just can't make it short enough to beat coffeescript

function Q(n){X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=600;M=Math;T=[[275,400,50,i=0]];while(A=T[i++]){X.save();X.translate(x=A[0],y=A[1]);X.rotate(-(a=A[3]));X.fillRect(0,-(l=A[2]),l,l);X.restore();S=M.sin;C=M.cos;i<M.pow(2,n)&&T.push([e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2])}}

Got to say I'm a bit galled this is almost twice as long as the mathematica solution :-/ see it in action: http://jsfiddle.net/FK2NX/3/

share|improve this answer
    
A few suggestions: You can save at least 16 characters by using semicolons instead of line breaks in CoffeeScript. In both cases, if any of the methods on X return X, you can chain them. And you can save another good bunch of characters by saving M.sin and M.cos in single-character variables. –  Martin Büttner Apr 2 at 8:09
    
Unfortunately context operations don't return the context, which I was pretty upset by. Also, you can rename M.sin to M.s, but the line M.s=M.sin takes up more characters than it saves... I'll look at stripping out the spaces. –  ali0sha Apr 2 at 8:58
    
No, you can just do s=M.sin. –  Martin Büttner Apr 2 at 9:01
    
How come I can do S=M.sin, but not R=X.rotate ? –  ali0sha Apr 2 at 9:15
    
I suppose rotate uses this, and sin doesn't. You'd need to do something like R=X.rotate.bind(X), but that's probably not worth it any more. –  Martin Büttner Apr 2 at 10:02
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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