Project Euler 28 Inefficient Answer Proposal Create "Spiral Numbers"

problem

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

Answer

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

Project Euler 28 Inefficient Answer Proposal Create "Spiral Numbers"
Project Euler 10 "Sum of Prime Numbers"
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler 14
Project Euler 34
Project Euler 25
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
[Project Euler] problem1