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} &amp;22 &amp;23 &amp;24 &amp;\color{red}{25}\\
20 &amp; \color{red}{7} &amp; 8 &amp; \color{red}{9} &amp;10\\
19 &amp; 6 &amp; \color{red}{1} &amp; 2 &amp;11\\
18 &amp; \color{red}{5} &amp; 4 &amp; \color{red}{3} &amp;12\\
\color{red}{17} &amp;16 &amp;15 &amp;14 &amp;\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 &lt; 1: return None
    elif n == 1: return 1
    elif n % 2 == 0: return None
    else:
        numbers = [1]
        while len(numbers) &lt; (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 --&gt; ms
print "Found %d in %r ms." % (ans, elapsed_time)
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 &lt; 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 &lt; 1 and n % 2 == 0 clauses are checking the same argument's validity, you can combine them into one if-statement:

    if n &lt; 1 or n % 2 == 0: 
        raise ValueError("argument must be an odd-valued integer &gt;= 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) &lt; (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) &lt; 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 --&gt; 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 --&gt; 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"