Saturday, May 7, 2011

Connecting Capacitances - Project Euler Problem#155

8 - May - 2011
I came across an interesting problem. Given N capacitors (or inductors, resistors) of same value say C (unit is Farad). How many difference capacitances can be derived from these N capacitors connected in series, parallel and series-parallel combination.
For example if N = 1, only one way it can be connected. If N = 2, they can be connected in two different ways of series and parallel. If N = 3, they can be connected in 7 different ways. That means we can derive 7 different capacitance values from given 3 capacitors of same value. These 7 combinations can be found pictorially on the Project Euler page.
Can we generalize it? Yes. Say the total possible capacitances are represented as S(n). If we observe, only the difference between S(n-1) and S(n-2) will participate using next capacitor. For example to calculate S(n) we need the difference DELTA = S(n-1) - S(n-2), and all combinations upto S(n-1). The new capacitor C(n) can be connected in series and parallel with every combination of DELTA..
With an example it will be clear. We know S(1) = 1, S(2) = 3 and S(3) = 7. To calculate S(4) we need DELTA = S(3) - S(2) = 4. We can connect the 4-th capacitor in series and parallel with these 4 combinations, overall it adds 4 * 2 = 8 more combination to the existing 7 combination upto S(3). So, clearly S(4) = 2 x DELTA + S(3) = 15. There is a recursive formula. It is evident from the recursion tree given below for S(5).


Solution can be generalized as
         S(n) = 2 x (S(n-1) - S(n-2)) + S(n-1)
              = 3 x S(n-1) - 2 x S(n-2)

Base case S(1) = 1, S(2) = 3 and S(3) = 7.

We can code above formula using recursion easily.

int totalPossibleCapacitances(int n)
{
    static int S[] = {1, 3, 7};
    if(n > 3)
        // Non trival case
 return 3*totalPossibleCapacitances(n-1) - 2*totalPossibleCapacitances(n-2)
    else
        // Trivial case
        return S[n - 1];
}
Complexity: What will be the complexity? If we observe the recursion tree, the problems are overlapped. Similar to the Fibonacci series. The characteristic equation of generalized solution can be written as

x ^ 2 - 3*x + 2 = 0 whose roots are x1 = 1 and x2 = 2. The solution is in the form

S(n) = A(x1)^n + B(x2)^n where A and B are constants that depends on initial conditions. After substitution of S(2) and S(3) we get,

S(n) = 1.2 * (2)^n - 3 which is exponential.
So, the above function runs with exponential complexity. Can we do better? Yes, the well known technique "Dynamic Programming".
If we observe from S(4), every number is depending on past two numbers only. S(n) = 3*S(n-1) - 2*S(n-2), i.e. we need to store only the past two values to find next number. A three element array will be sufficient. Given below pseudo code,

int totalPossibleCapacitances(int n)
{
    // For efficiency purpose
    // static
    int S[] = {1, 3, 7};

    if(n > 3)
    {
        // Non trivial
        int activeIndex = 0;

        for(int i = 4; i <= n; i++)
        {
            S[activeIndex] = 3*S[ (activeIndex + 2) % 3 ] - 2*S[ (activeIndex + 1) % 3 ];

            activeIndex++;
            activeIndex %= 3;
        }

        if(activeIndex)
            activeIndex--;

        return S[activeIndex];
    }
    else
    {
        // Trivial
        return (n > 0 ? S[n - 1] : -1);
    }
}

Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.

3 comments:

Anonymous said...

Well, your answers are incorrect.
I think you are forgetting that S(10) will also have some involvement from S(7) and S(3)

Nipuna said...

Dude you have to consider all possibilities of making n, Ex:n=5 , consider making n using S(4)+S(1),S(3)+S(2) and have to check whether there are overlaps. Also I must say that it is obviously not going to be easy to consider all the partitions of n when n is very large.

Anonymous said...

Can u give the answer for facebook problem???