[CCC] 2004 J4 Fractal, someone explain the logic for solution plz

[riveryu]

Gah... I am stuck on J5 for 2004. Other problems took me 10mins but I came to a halt there. I completely blanked out.
How do you do it? What is your logic?

J5 PDF : http://www.cemc.uwaterloo.ca/ccc/2004/stage1/juniorEn.pdf
Working Answer in Turing : http://access.mmhs.ca/ccc/2004/j5fractals.txt

Yes, I know there is another topic on this question some years ago and it didn't help me since I don't even recognize the language the answer was in.

Also, is some degree of math required for this problem, if so tell me what I have to learn?

P.S. I only understand Turing and very readable Java.

[nike52]

You could probably understand it by examining the answer code line by line.

[Tony]

There seem to be three major parts to the problem:

generating the fractal -- usually easier to do with recursion.

storing the generated fractal in some data structure.

search for requested values in the data structure above.

You may attempt the problem doing one of the above steps at a time.

[Brightguy]

Last time I gave a VB solution. This time I'll use PHP.

php:

<?php $level = 4; $width = 81; $x = 38; function grow($fractal) {       $new = array(array(0, 1));         for($i=1; $i<count($fractal); $i++)         {       $X = array(($fractal[$i][0]-$fractal[$i-1][0])/3, ($fractal[$i][1]-$fractal[$i-1][1])/3);                 $Y = array(-($fractal[$i][1]-$fractal[$i-1][1])/3, ($fractal[$i][0]-$fractal[$i-1][0])/3);                 $new[] = array($X[0]+$fractal[$i-1][0], $X[1]+$fractal[$i-1][1]);                 $new[] = array($X[0]+$Y[0]+$fractal[$i-1][0], $X[1]+$Y[1]+$fractal[$i-1][1]);                 $new[] = array(2*$X[0]+$Y[0]+$fractal[$i-1][0], 2*$X[1]+$Y[1]+$fractal[$i-1][1]);                 $new[] = array(2*$X[0]+$fractal[$i-1][0], 2*$X[1]+$fractal[$i-1][1]);                 $new[] = $fractal[$i];         }         return $new; } function contains($fractal, $x, $y) {       for($i=1; $i<count($fractal); $i++)         {       $x1 = min($fractal[$i-1][0], $fractal[$i][0]);                 $x2 = max($fractal[$i-1][0], $fractal[$i][0]);                 $y1 = min($fractal[$i-1][1], $fractal[$i][1]);                 $y2 = max($fractal[$i-1][1], $fractal[$i][1]);                 if($x>=$x1 && $x<=$x2 && $y>=$y1 && $y<=$y2)                         return(true);         }         return(false); } $fractal = array(array(0, 1), array($width, 1)); for($i=0; $i<$level; $i++)         $fractal = grow($fractal); for($y=1; $y<=($width+1)/2; $y++)         if(contains($fractal, $x, $y))                 echo("$y "); echo("\n"); ?>

The grow function loops through every line in the fractal and splits it into five lines according to the fractal generation rule. How are the points of the five lines calculated? Given a vector Z, let X be Z/3 and Y be X rotated 90? counterclockwise. Then X, X+Y, 2X+Y, 2X and 3X=Z will give you the endpoints you need to split the line represented by Z.

[riveryu]

Whats a vector?The only vector I know is from Java Vector Class. How did you figure out the "fractal generation rule"?

O my god, I'm gonna get owned on the contest by questions like these.

[Brightguy]

Think of a vector as a direction and a length in two dimensions (for this problem). Any two points in a 2D plane will determine a vector (actually two, depending how you order the points).

The fractal generation rule is given in the problem: you are supposed to replace every line in the fractal with a "bumped" line consisting of 5 smaller lines. For every line, the first of the smaller lines will be in the same direction as the original line but it will have one-third of its length, which is where X=Z/3 comes from.

I think they could have explained the problem better. Here's an animated gif of the fractal if you can't visualize it.

[riveryu]

They sure know how to keep it vague but possible... Looks like I have some math to do.

Edit : I get it now, it seems so easy now and I realized just how badly the question is worded.
It could have been waaay more clearer.