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

  • \$\begingroup\$ Appears to be a duplicate: codegolf.stackexchange.com/questions/18785/… \$\endgroup\$
    – DavidC
    Mar 29, 2014 at 21:17
  • \$\begingroup\$ False. I'm after a different algorithm :) \$\endgroup\$
    – alyx-brett
    Mar 29, 2014 at 21:18
  • \$\begingroup\$ Ok. Fair enough. You may want to consider retitling your submission to "Pythagorean Tree". \$\endgroup\$
    – DavidC
    Mar 29, 2014 at 21:33
  • \$\begingroup\$ I like trains? :) \$\endgroup\$
    – tomsmeding
    Apr 25, 2014 at 11:08

5 Answers 5


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

  • \$\begingroup\$ I know this isn't fully ontopic, but how would a version look if instead of "white noise", you used "brown noise" as angles? \$\endgroup\$ Mar 30, 2014 at 15:47
  • \$\begingroup\$ @Synthetica you mean with more angles around 90° and less at 0 and 180? \$\endgroup\$ Mar 30, 2014 at 16:36
  • \$\begingroup\$ @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. \$\endgroup\$ Mar 30, 2014 at 18:57
  • \$\begingroup\$ 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 \$\endgroup\$
    – alyx-brett
    Apr 2, 2014 at 20:04
  • \$\begingroup\$ @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 ^^ \$\endgroup\$ Apr 2, 2014 at 20:28

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[#] &
  • \$\begingroup\$ That is quite impressive. Shame I don't have mathematica to test it - could you add another couple of example outputs? \$\endgroup\$
    – alyx-brett
    Mar 29, 2014 at 21:49
  • \$\begingroup\$ @ali0sha see edit \$\endgroup\$ Mar 29, 2014 at 21:57
  • \$\begingroup\$ You don't need Show in there, and Module is also unnecessary. \$\endgroup\$
    – swish
    Mar 30, 2014 at 7:32
  • \$\begingroup\$ @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? \$\endgroup\$ Mar 30, 2014 at 10:41
  • \$\begingroup\$ @m.buettner Maybe you can use Block, which is shorter than Module. \$\endgroup\$
    – alephalpha
    Mar 30, 2014 at 11:43

Mathematica, 122 characters

Graphics[Polygon/@ReIm@NestList[Join@@({##3}+Cos[t=Random[]Pi/2]E^(I t){I Tan@t(#2-{##}),{##}-#}&)@@@#&,{{0,1,1+I,I}},#]]&

enter image description here

Ungolfed version:

next=Compile[{{z,_Complex,1},t},{z[[4]]-E^(I t) (z[[1]]-z) Cos[t],z[[3]]+I E^(I t) (z[[2]]-z) Sin[t]},RuntimeAttributes->{Listable}];

enter image description here

3D version, refer to https://mathematica.stackexchange.com/questions/213727/how-to-draw-a-pythagoras-tree-like-this/213827#213827, render by POV-Ray

enter image description here


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/

  • \$\begingroup\$ 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. \$\endgroup\$ Apr 2, 2014 at 8:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – alyx-brett
    Apr 2, 2014 at 8:58
  • \$\begingroup\$ No, you can just do s=M.sin. \$\endgroup\$ Apr 2, 2014 at 9:01
  • \$\begingroup\$ How come I can do S=M.sin, but not R=X.rotate ? \$\endgroup\$
    – alyx-brett
    Apr 2, 2014 at 9:15
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 2, 2014 at 10:02

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


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.

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

  • \$\begingroup\$ 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 \$\endgroup\$
    – alyx-brett
    Apr 2, 2014 at 20:02
  • \$\begingroup\$ @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 ;) \$\endgroup\$ Apr 2, 2014 at 22:55
  • \$\begingroup\$ I think you should do it - make it a bit more competitive in here :) \$\endgroup\$
    – alyx-brett
    Apr 3, 2014 at 6:15

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.