[PYTHON] Projekt Euler 28 Ineffizienter Antwortvorschlag Erstellen Sie "Spiral Lined Numbers"

Problem

Gehen Sie ab 1 nach rechts und erhöhen Sie die Zahl im Uhrzeigersinn. Eine 5 × 5-Spirale wird wie folgt erzeugt:

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 Es wird bestätigt, dass die Summe der Zahlen auf beiden Diagonalen 101 beträgt.

Was ist die Summe der Zahlen auf der Diagonale, wenn auf die gleiche Weise eine 1001 × 1001-Spirale erzeugt wird?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2028

Antworten

Das Problem, das nach langer Zeit brannte. n2 + an + b Ich kann eine Antwort geben, die für die Formel gilt, aber ich habe beschlossen, eine "Spiralzahl" ineffizient zu erstellen.

Die spiralförmig angeordneten Zahlen werden nach folgenden Regeln erstellt. ・ Wenn die vorherige Bewegung nach oben war ... Wenn die rechte offen ist, die rechte, wenn die rechte nicht offen ist, die obere ・ Wenn die vorherige Bewegung nach unten war ... Wenn die linke Seite offen ist, die linke, wenn die linke Seite nicht geöffnet ist, die untere ・ Wenn der vorherige Zug nach rechts war ... Wenn der Boden offen ist, ist der Boden offen, wenn der Boden nicht offen ist, rechts ・ Wenn der vorherige Zug nach links war ... Wenn die Oberseite offen ist, ist die Oberseite nach oben, wenn die Oberseite nicht offen ist, nach links

Danach können Sie diese Regel in den Code einfügen und die spiralförmig angeordnete Zahl reproduzieren. Gibt es noch etwas zu tun, wie die Verarbeitung von Abschlüssen zu einer Funktion zu machen?

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