- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 28:数のらせんの対角線
原文 Problem 28: Number spiral diagonals
問題の要約:図のように1から順番にマスにらせん状に書いて行ったとき1001 x 1001のマスが埋まったときの対角線の数の合計を求めよ
なんとなく規則性はつかめそうに思えますが。まず規則通りにマスを埋めるプログラムを書いてみます。
import numpy as np
N = 9
vectors = np.array([[-1,0],[0,1],[1,0],[0,-1]]) # direction (0:up, 1:right, 2:down, 3:left )
matrix = np.array([0]*(N**2)).reshape(N,N) # Fill 0s in N x N matrix
pos = np.array([(N-1)//2, (N-1)//2]) # Start position
dir = 0 # direction index (0:up, 1:right, 2:down, 3:left )
for i in range(1,N**2+1):
matrix[pos[0],pos[1]] = i # put the number
rpos = pos + vectors[(dir+1)%4]
if matrix[rpos[0],rpos[1]] == 0: # if right pos is 0, then turn right
dir = (dir+1)%4 # right direction
pos = pos + vectors[dir] # next position
print(matrix)
N=9でできたマス目を表示します。
[[73 74 75 76 77 78 79 80 81]
[72 43 44 45 46 47 48 49 50]
[71 42 21 22 23 24 25 26 51]
[70 41 20 7 8 9 10 27 52]
[69 40 19 6 1 2 11 28 53]
[68 39 18 5 4 3 12 29 54]
[67 38 17 16 15 14 13 30 55]
[66 37 36 35 34 33 32 31 56]
[65 64 63 62 61 60 59 58 57]]
これをじっと見ていると規則性が見えてきます。一辺の長さは2つづつ増えているので、間隔dで4つの角を数字求めて、dを2つ増やすのを繰り返せばいいですね。その合計が答えということです。
N = 9
dg = [1]
n, d = 1, 0
for i in range((N-1)//2):
d += 2
for i in range(4):
n += d
dg.append(n)
print(sum(dg), dg)
#537 [1, 3, 5, 7, 9, 13, 17, 21, 25, 31, 37, 43, 49, 57, 65, 73, 81]
(開発環境:Google Colab)