1997 Mathematica Developer Conference Challenge Problem

Problem Statement

Create the function TreeGraphic[d_Integer] that produces a Graphics object for a tree with 3·(2^d) leaves, arranged and connected as shown below.

In particular, the 3·(2^d) leaves should be arranged on a circle, their 3·(2^(d - 1)) neighbors should be arranged between them on a smaller concentric circle, and so on, until one vertex is placed at the center of all the circles. As you can see, every non-leaf vertex is connected to exactly three other vertices. If your output differs from that shown below by only a rotation, that's fine.

Show[GraphicsArray[{ TreeGraphic[3],  TreeGraphic[5]}]];

Winning Solution by Richard Mercer
Department of Mathematics and Statistics
Wright State University

Program

Leaves[0,n_]:= Pi/2 + n*2Pi/3;
Leaves[k_,n_]:= 
	Leaves[k-1,Quotient[n,2]]+(-1)^Mod[n,2]*Pi/(3*2^k); 
Leaves[k_]:= Table[Leaves[k,n],{n,0,3*2^k-1}];
Polar[r_,th_]:= {r Cos[th],r Sin[th]};
Pts[k_]:= Polar[k+1,#]& /@ Leaves[k];
Lines[0] = Line[{{0,0},#}]& /@ Pts[0];
Lines[k_]:=
Apply[{Line[{#1,First[#2]}],Line[{#1,Last[#2]}]}&,
Transpose[{Pts[k-1],Partition[Pts[k],2]}],{1}];

TreeGraphic[d_Integer]:=
Show[Graphics[Table[Lines[k],{k,0,d}],
{AspectRatio->Automatic}]];

Examples

TreeGraphic[1];

TreeGraphic[2];

TreeGraphic[3];

Other Items

Report

What is given above under Program and Examples is exactly what I submitted during the contest with two minor modifications : 
(1) "Pi" has replaced the actual Greek letter to improve readability.
(2) A semicolon was added to the line beginning "Lines[0] =" to suppress output.

We had 90 minutes  to work on this problem and submit a solution. I thought that would be plenty of time, as  I had often done harder things in 90 minutes, as had many others in the room. Boy was I wrong! I felt like I was not thinking clearly, and the time went by quickly. One solution was submitted in a little over an hour, and one began to hear numerous muttered curses (including a few of my own) as the deadline approached. I was fortunate to find something that worked, and submitted my solution with a few minutes to spare. The deadline was extended to 10:20, and apparently two other solutions were submitted by that time. Reportedly solutions continued to come until after midnight; I left the room after the 10:20 deadline.

We had been told the solutions would be based on elegance. Elegance is subjective, of course. I spent a lot of time trying to decide whether to write a constructive program like Matthew Cook's  sample solution (below), or to write a recursive solution like the one I submitted. I would have preferred to use a constructive solution as they tend to be shorter and faster, but they are also more subtle to construct. As time grew shorter, I decided the first condition of elegance is that the program should work, and that was the only thing I could accomplish within the time limit! That turned out to be the right strategy. My solution won not because it was elegant (I don't claim that it is) but because it was the only one of the four submitted "on time" that actually did what it was supposed to do.

Incidentally, I just have to mention that my solution actually produces the picture given to us during the contest, without rotation. Matthew's solution produces an image rotated 90 degrees. But then he said it was OK to do so!

Matthew Cook's Example Solution

\(TreeGraphic[d_Integer] := \ 

      Graphics[Table[
          \(Line[{k + 1, k, k + 1} #]&\)\ /@

            Partition[
              Table[\({Cos[#], Sin[#]}&\)[2  Pi\ t/\((6*2^k)\)], 
                
{t, 1 + 6*2^k}], 3, 4], {k, 0, d}], 
        AspectRatio -> Automatic]\)

Thanks

I want to express my thanks to:
-- Wolfram Research for the generous prize of my choice of application package. (I chose Wavelet Explorer.)
-- Matthew Cook, who came up with a problem of appropriate difficulty, not too easy but not impossible , and the other employees of Wolfram Research who helped administer the contest that evening.
-- All the contestants in the competition, probably 25-30 altogether, who joined in the spirit of competition for the fun of it.