Project Euler 28: sum of spiral diagonals using recursion

Question

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);
        }
    }

Answer 1

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?

Answer 2

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.

Answer 3

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.