I couldn't sleep tonight so I took a challenge with Python to create some fractals in Turtle. I had fun coming up with the solution so I thought I'd blog about it here. Thank you, Dr. Ian Parberry, for your algorithms analysis class all those years ago. I use the techniques you taught me every day!
Here is the lab I worked on: Python Fractal Labs
I solved this problem in three steps.
Step 1: Induction If there's anything we know about fractals, it is that they are infinite surfaces. You will never solve an infinite surface unless you can solve every element of that surface. So, the first thing I did is guessed at the relative size of the squares. I thought that the squares looked to be about half the size of the originals, so that's where I began. In mathematical terms, I induced that
n = (n - 1)/2
. In coding terms, it's
childBoxSize = parentBoxSize / 2
Step 2: Solve the pattern Next, I had to figure out where to place the squares in relation to the nth box. To give a precise cursor position, you only have to figure out three coordinates to place all 8 boxes:
1) Max -- This describes the largest integer value at which you will place your cursor 2) Min -- This describes the smallest integer value at which you will place your cursor 3) Middle -- this describes the value which is exactly 1 unit distance between the two
Once you figure that out, you can plug in these coordinates in a criss-cross pattern to end up at the bottom left corner of each of the 8 boxes. Since I was guessing at half for the size of the box, I thought it might work out that the distance was half as well. (this was wrong, by the way.)
Step 3: Recurse The algorithm has three things to do:
1) If this is the base case, don't repeat the pattern 2) If this is NOT the base case, set up the pattern and recurse 3) Draw this case
The "base case" is the limit of the algorithm - it's where you want to stop so you don't fry your computer. I set my base case very high in the beginning, and as the code became more robust, I made the base case smaller and smaller.
Results Here are the results in pseudocode:
LayCarpet (mySize, myCoordinate): if mySize > 1: 8_points = setCoordinates(min, max, middle, myCoordinate) for coordinate in 8_points: LayCarpet(mySize / 2, coordinate) drawBox(mySize, myCoordinate)