Sign up ×
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. 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:… – David Carraher Mar 29 '14 at 21:17
False. I'm after a different algorithm :) – alexander-brett Mar 29 '14 at 21:18
Ok. Fair enough. You may want to consider retitling your submission to "Pythagorean Tree". – David Carraher Mar 29 '14 at 21:33
I like trains? :) – tomsmeding Apr 25 '14 at 11:08

4 Answers 4

up vote 15 down vote accepted

Mathematica, 246 234 221 characters


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, {},
    (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? – alexander-brett Mar 29 '14 at 21:49
@ali0sha see edit – Martin Büttner Mar 29 '14 at 21:57
You don't need Show in there, and Module is also unnecessary. – swish Mar 30 '14 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 '14 at 10:41
@m.buettner Maybe you can use Block, which is shorter than Module. – alephalpha Mar 30 '14 at 11:43

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
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
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 '14 at 15:47
@Synthetica you mean with more angles around 90° and less at 0 and 180? – Martin Büttner Mar 30 '14 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 '14 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 – alexander-brett Apr 2 '14 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 '14 at 20:28

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


gswin32c -c 20 %RANDOM% -f

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.

250 99 translate
50 50 scale
    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
        dup rotate
        dup cos dup scale
        dup cos dup dup mul
        exch 2 index sin mul translate
        dup 90 sub rotate
        sin dup scale 1

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
250 99<AD>$
50 50<8B>$
1 le{
0(>)$ 0<9D>$
0 0 1 1<80>$
0 1<AD>$
rand 5 mod 1 add 15 
2(X)$ sin<6CAD38>$
90<A988>$ sin<388B>$

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 – alexander-brett Apr 2 '14 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 ;) – Vadim Apr 2 '14 at 22:55
I think you should do it - make it a bit more competitive in here :) – alexander-brett Apr 3 '14 at 6:15

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.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.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:

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 '14 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. – alexander-brett Apr 2 '14 at 8:58
No, you can just do s=M.sin. – Martin Büttner Apr 2 '14 at 9:01
How come I can do S=M.sin, but not R=X.rotate ? – alexander-brett Apr 2 '14 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 '14 at 10:02

Your Answer


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.