# Project Euler 28 - Number Spiral Diagonals

Project Euler problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

$$\begin{array}{rrrrr} \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{array}$$

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

I realized that the spiral was essentially an arithmetic sequence, so I based my code off of that.

from timeit import default_timer as timer
start = timer()

def spiral_diag_sum(n):
if n < 1: return None
elif n == 1: return 1
elif n % 2 == 0: return None
else:
numbers = [1]
while len(numbers) < (2*n - 1):
increment = int(len(numbers) * 0.5 + 1.5)
for p in range(4):
numbers.append(numbers[-1] + increment)
return sum(numbers)

ans = spiral_diag_sum(1001)
elapsed_time = (timer() - start) * 1000 # s --> ms
print "Found %d in %r ms." % (ans, elapsed_time)

-
Metric Marvin says, "1s = 1000ms." :) –  David Harkness Apr 13 at 20:23

from timeit import default_timer as timer

start = timer()


This line of code belongs with the code at the end of the program that times the call to spiral_diag_sum.

def spiral_diag_sum(n):


It's always a good idea to add a docstring. Several of the later Project Euler problems rely on finding a solution to earlier ones (though perhaps not this one), so you'll find yourself building up a library of useful code to reuse, in which case a good docstring makes it much easier to import.

    if n < 1: return None
elif n == 1: return 1
elif n % 2 == 0: return None
else:


Checking that your arguments are sane is good. However, here you've got (in sequence) an error condition, a successful return, an error condition and (following the else) the main body of the function. It's better to separate the error conditions and handle them first.

You're also returning None as the error value, but you're not checking for that value after you call spiral_diag_sum at the end of the program. Add code to check that, or better yet, raise an exception here indicating the error. Since both the n < 1 and n % 2 == 0 clauses are checking the same argument's validity, you can combine them into one if-statement:

    if n < 1 or n % 2 == 0:
raise ValueError("argument must be an odd-valued integer >= 1")


Resuming with the if n == 1: return 1 from the original code:

    if n == 1:
return 1


Even when it's a short piece of code like here, I like to keep separate statements on their own line. Most Python code that you see will do that.

    else:
numbers = [1]
while len(numbers) < (2*n - 1):
increment = int(len(numbers) * 0.5 + 1.5)
for p in range(4):
numbers.append(numbers[-1] + increment)
return sum(numbers)


The formulas here need more thought than is required. Calculate and store the (2*n -1) formula in a variable with a descriptive name. The increment starts at 2 for the first row out from the center, and goes up by two for every subsequent row, so this whole thing could be:

        numbers_needed = 2 * n - 1
increment = 2
while len(numbers) < numbers_needed:
for p in range(4):
numbers.append(numbers[-1] + increment)
increment += 2
return sum(numbers)


This other answer already explains about the downsides of using a list to hold all the numbers and shows how to calculate the number at each corner. You can go even further and derive a mathematical formula for the total contributed by the four corners of an NxN square, then use that formula iterating from the central 1x1 square out to the final NxN.

Hint: the last corner of an NxN square will have the value N2. The values of the other three corners can be derived from that value. The same formula also works for the central 1x1 square so you don't even need to have a special case for it.

ans = spiral_diag_sum(1001)
elapsed_time = (timer() - start) * 100 # s --> ms
print "Found %d in %r ms." % (ans, elapsed_time)


Following from some things I mentioned earlier: making this into a module that you can use in later problems, checking for a valid return value from spiral_diag_sum, and keeping all the timing code together:

if __name__ == "__main__":       # Allows standalone use or as a library module.
start = timer()              # This code moved from above.
ans = spiral_diag_sum(2)
elapsed_time = (timer() - start) * 100 # s --> ms
if ans:                      # Check for valid answer (or use try / except)
print "Found %d in %r ms." % (ans, elapsed_time)
else:
print "No answer returned"

-

Accumulating all the numbers in a list is unnecessary, and with large numbers you might reach the memory limit. This is equivalent and more efficient:

count = 1
lastnum = 1
total = lastnum
while count < (2 * n - 1):
increment = count * 0.5 + 1.5
for p in range(4):
lastnum += increment
total += lastnum
count += 1


This has the added benefit that the result is already summed, no need to run sum(...) on a potentially large list.

I dropped an unnecessary cast in int(count * 0.5 + 1.5). This gives a noticeable improvement in elapsed_time.

In your original code, you misplaced the indent of return sum(numbers): it is outside of the else block, so it's a bit dirty.

This may be a matter of taste, but I like to flatten this kind of if-else code like this:

if n < 1:
return None
if n == 1:
return 1
if n % 2 == 0:
return None
....


In any case, PEP8 recommends to break the line after :. It's good to run pep8 and pyflakes on your code and follow the recommendations.

-

I think that the special cases in the beginning are a bit clumsy:

def spiral_diag_sum(n):
if n < 1: return None
elif n == 1: return 1
elif n % 2 == 0: return None
else:
# Build the numbers list here
…
return sum(numbers)


Those cases are there for validation; they shouldn't look like a part of the calculation. Furthermore, n = 1 does not need to be a special case, so you shouldn't write it as such.

def spiral_diag_sum(n):
if n < 1 or n % 2 == 0:
raise ValueError(n)

numbers = [1]
…


I don't like this foray into floating point:

increment = int(len(numbers) * 0.5 + 1.5)


$$increment = \left\lfloor \frac{\mathrm{len}(numbers)}{2} + \frac{3}{2} \right\rfloor = \left\lfloor \frac{\mathrm{len}(numbers) + 3}{2} \right\rfloor$$

That should be written in Python as

increment = (len(numbers) + 3) // 2


But, as @NiallC points out, it suffices to write

increment += 2


since len(numbers) increases by 4 each time.

-

There is no need for a list or nested loops in this algorithm.

Here is how I solved by making use of the pattern exhibited in the description:

• corner1=i**2 (NE corner, where i is the height/width dimension of each concentric square)
• corner2=corner1-(i-1) (NW corner)
• corner3=corner2-(i-1) (SW corner)
• corner4=corner3-(i-1) (SE corner)

def problem28():
total=1
for i in xrange(3,1002,2):
total+=i**2 + (i**2-(i-1)) + (i**2-2*(i-1)) + (i**2-3*(i-1))