2
\$\begingroup\$

I've solved Project Euler #28 using recursion.

If this 5 × 5 spiral pattern is extended to 1001 × 1001, what would be the sum of the red diagonals?

$$\begin{matrix} \color{red}{21} & 22 & 23 & 24 & \color{red}{25} \\ 20 & \color{red}{7} & 8 & \color{red}{9} & 10 \\ 19 & 6 & \color{red}{1} & 2 & 11 \\ 18 & \color{red}{5} & 4 & \color{red}{3} & 12 \\ \color{red}{17} & 16 & 15 & 14 & \color{red}{13} \end{matrix}$$

Is this a good enough solution, or is there some other way to optimize the code?

static long GetSumofDiagonals(int cubeSize)
    {
        long sum = 0;
        if (cubeSize == 1)
            return 1;
        else
        {
            // As the diagonal numbers follows a sequence
            // UR = n^2 - 1;
            // UL = UR - (n - 1)
            // LL = UL - (n -1 )
            // LR = LL - (n - 1)
            // This works only for odd n
            long UpperRight = (long) Math.Pow(cubeSize, 2);
            long UpperLeft = UpperRight - (cubeSize - 1);
            long LowerLeft = UpperLeft - (cubeSize - 1) ;
            long LowerRight = LowerLeft - (cubeSize - 1);
            sum = UpperRight + UpperLeft + LowerLeft + LowerRight;
            return sum + GetSumofDiagonals(cubeSize - 2);
        }
    }
\$\endgroup\$
  • 5
    \$\begingroup\$ Where did you find it? Or do you mean that you wrote it? \$\endgroup\$ – svick Jul 23 '13 at 14:08
  • \$\begingroup\$ @svick I wrote it..but I haven't thought of forming a quadratic equation from it.. \$\endgroup\$ – Naren Jul 24 '13 at 6:18
5
\$\begingroup\$

Performance is okay (linear), but I think the code can be simplified by using a loop instead of recursion, and by going from the inside-out instead of from the outside-in.

Here's how I did it, in pseudo-code:

sum = 1   # running sum
last = 1  # last number
delta = 2 # delta between numbers

for layer in 1 to (sidelength - 1) / 2:
    for num in 1 to 4:
        last += delta
        sum += last
    delta += 2 # increases by two with each layer

return sum

Also, I think this is one of those probems that can actually be calculated directly using pencil and paper, without any loops. Why don't you check out the problem forum there?

\$\endgroup\$
  • \$\begingroup\$ That's great..I never thought of it!!..to form the quadratic equation and then using a simple loop to solve it. Thanks @tobias_k \$\endgroup\$ – Naren Jul 23 '13 at 12:57
  • \$\begingroup\$ I cooked up an O(1) solution but if someone doesn't want to do maths it is much simpler than the O(n) solution that I had used earlier. \$\endgroup\$ – Aseem Bansal Jul 23 '13 at 17:25
3
\$\begingroup\$

There is a very easy solution.

In all cases I'll avoid x = 1 as it is a corner that doesn't fit the pattern.

The pattern of each ring can be generalized easily into an equation considering the rings to be numbered as x = 2, 3, 4, ... , 500

(2x - 1)(2x - 1) - (2x - 1) - 2(2x - 1) - 3(2x - 1)

The first term is for upper right corner of each ring. The second is for upper left then lower left and finally lower right. I laid it out barely to make it easy to understand but you can certainly make it shorter.

It is actually easier to find an equation by considering the rings to go from x = 3, 5, ..., 1001

4(x*x) - 6(x - 1)

Running a loop over the range 2 to 1001 with step of 2 and then adding 1 gives you the answer.

You want to simplify it further? You need the formula for summation of series of n^2 and summation of n. That makes this into an O(1) program instead of current O(n).

For example the first term would become 4 * summation(x^2) with summation running from 3 to n with step of 2. Its value is

(n * (n + 1) * (n + 2))*(2/3) + 1

I am ignoring the implementation details like it should be 2.0/3.0.

Similarly the second term is - 6 * summation(x) with summation running from 3 to n with step of 2. Third term is `6(n - 2). I'll leave calculating the second term to you.

Simply adding these 3 terms gives you an O(1) program.

\$\endgroup\$
  • \$\begingroup\$ You should name your intermediate variable something other than n, since n already has a meaning. Also, the Project Euler challenges are specifically to write a program to solve it. \$\endgroup\$ – Bobson Jul 23 '13 at 16:46
  • 1
    \$\begingroup\$ @Bobson If the optimization is done to the last level of O(1) by using sum of series then n would become exactly what it represents in the problem statement. But for other cases your comment is valid. I solved the problem nearly 2 months ago that's why the logic I presented in the answer is a little messy. I'll clean it up. \$\endgroup\$ – Aseem Bansal Jul 23 '13 at 16:59
  • \$\begingroup\$ @Bobson Is it better now? \$\endgroup\$ – Aseem Bansal Jul 23 '13 at 18:34
  • \$\begingroup\$ I think so. +1. \$\endgroup\$ – Bobson Jul 24 '13 at 15:00
2
\$\begingroup\$

A pattern like

if(someCondition) 
{
    return someValue;
}
else
{
    return someOtherValue;
}  

can be simplified by removing the else, because it is redundant:

if(someCondition) 
{
    return someValue;
}

return someOtherValue;

You should throw an ArguemntException for the case an even value is passed to the method.


Also it isn't mentioned in the naming guidelines you should name variables which are local to a method by using camelCase casing too.

\$\endgroup\$
  • 2
    \$\begingroup\$ Not only can you omit the else, you can just do: return someCondition ? someValue : someOtherValue;. \$\endgroup\$ – Abbas Mar 5 '15 at 8:25
  • 2
    \$\begingroup\$ Right, I just wanted to stay in the code in question. Using a tenary for the code in question would look strange. \$\endgroup\$ – Heslacher Mar 5 '15 at 8:27
  • \$\begingroup\$ Took a second look and indeed it would be strange. :) \$\endgroup\$ – Abbas Mar 5 '15 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.