問題

1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:

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
両対角線上の数字の合計は101であることが確かめられる.

1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?

回答

久しぶりに燃えた問題。
n2 + an + b
的な公式に当てはめた回答もできるけど、ここは効率悪く「螺旋状に並んだ数」を作成してみることとした。

螺旋状に並んだ数は、次のルールで作られる。
・前回が上方向への移動であった場合‥右があいていれば右、右があいていなければ上
・前回が下方向への移動であった場合‥左があいていれば左、左があいていなければ下
・前回が右方向への移動であった場合‥下があいていれば下、下があいていなければ右
・前回が左方向への移動であった場合‥上があいていれば上、上があいていなければ左

あとは、このルールをコードに落とし込めばらせん状に並んだ数を再現することが出来る。
度の処理を関数化するなどが残といったところだろうか。

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()