Project Euler 199 - Iterative Circle Packing

Official link:

Thought Process

Main theorem to use here is Descartes' theorem and little more digging and you find that these type of fractal structures are called Apollonian gaskets.

If we begin with our 3 of equal radius say 1 then we find 2 new circles using equation 2 that have curvature k4 = 3 ± 2√(3)

  1. 3 - 2√(3) < 0 and therefore it is an externally tangent circle, that is, it is the main circle enclosing them all, and it has radius -1/(3 - 2√(3)) ~ 2.15

  2. 3 + 2√(3) > 0 and therefore it is an internally tangent circle, that is, it is the green circle in the middle of the initial 3 and it has radius 1/(3 + 2√(3))

Using this it is very easy to come up with a solution. I opted to use a stack first but then realised recursion is easier.

I briefly outline my use of a stack here and leave it to you to figure out the recursion counterpart

  1. Stack contains elements [a, b, c, depth] where a, b, c is the curvature of 3 circles

    • First element in the stack is [1, 1, 1, depth] if you are trying to find the area covered by the circle in the middle of the 3 initial circles

    • You need a 2nd stack for the v-shaped area, what should you initialise it with? Hint: [3 - 2√(3), 1, 1, depth]

  2. pop the first element out and find the curvature of the new circle, denoted by d, using equation 2

    • Note besides finding the very first large circle that encloses them all, we only need to find internally tangent circles

  3. Find the radius of the circle and add its area to a running area covered total (so you keep track of your area covered)

  4. if your depth is greater than 1, append the following elements to the stack, which will find the next layer of circles

    • [a, b, d, depth - 1]

    • [a, c, d, depth - 1]

    • [b, c, d, depth - 1]

Interactive Code

Enter a number (yourinput)

Code will output the fraction of the area that is not covered after yourinput iterations