Starting from 1, go to the right and increase the number clockwise, and a 5 × 5 spiral is generated as follows:
21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 It is confirmed that the sum of the numbers on both diagonals is 101.
When generating a 1001 × 1001 spiral in the same way, what is the sum of the numbers on the diagonal?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2028
The problem that burned after a long time. n2 + an + b I can give an answer that applies to a typical formula, but I decided to create a "spiral number" inefficiently.
The numbers arranged in a spiral are made according to the following rules. ・ If the previous move was upward ... If the right is open, the right, if the right is not open, the upper ・ If the previous move was downward ... If the left is open, the left, if the left is not open, the bottom ・ If the previous move was to the right ... If the bottom is open, the bottom is open, if the bottom is not open, the right ・ If the previous move was to the left ... If the top is open, the top is up, if the top is not open, the left
After that, you can incorporate this rule into the code and reproduce the numbers arranged in a string. Is there anything left to do, such as making the processing of degrees into a function?
UPPER = 'upper'
UNDER = 'under'
RIGHT = 'right'
LEFT = 'left'
def nextupper(domain,i,j):
return (UPPER,i-1,j)
def nextunder(domain,i,j):
return (UNDER,i+1,j)
def nextright(domain,i,j):
return (RIGHT,i,j+1)
def nextleft(domain,i,j):
return (LEFT,i,j-1)
def nowupper(domain,i,j):
if domain[i][j+1]:
return nextupper(domain,i,j)
else:
return nextright(domain,i,j)
def nowunder(domain,i,j):
if domain[i][j-1]:
return nextunder(domain,i,j)
else:
return nextleft(domain,i,j)
def nowright(domain,i,j):
if domain[i+1][j]:
return nextright(domain,i,j)
else:
return nextunder(domain,i,j)
def nowleft(domain,i,j):
if domain[i-1][j]:
return nextleft(domain,i,j)
else:
return nextupper(domain,i,j)
def next(domain,drct, i, j):
if drct == UPPER:
return nowupper(domain,i,j)
elif drct == UNDER:
return nowunder(domain,i,j)
elif drct == RIGHT:
return nowright(domain,i,j)
else:
return nowleft(domain,i,j)
def cof():
#MAX = 5
MAX = 1001
START = MAX//2
seq = range(MAX)
domain = [[0 for i in seq] for j in seq]
v = 1
(drct, i, j) = (UPPER,START,START)
while i < MAX and j < MAX:
domain[i][j] = v
(drct, i, j) = next(domain, drct, i, j)
v += 1
#for i in seq: print domain[i]
ans = 0
for m in seq:
ans += domain[m][m]
for m in seq:
ans += domain[m][MAX-m-1]
ans -= domain[START][START]
print ans
cof()
Recommended Posts