螺旋图案：如何找到给定坐标的数字？

Question

给定一个螺旋图案，我的工作是编写一个函数，该函数采用特定坐标并 returns 这些坐标处的数字。例如：

如果输入是 (1, -1)，函数将 return 8.

我不是在寻找代码。我正在寻找关于螺旋模式如何工作的解释，因为我对编程比较陌生（参加介绍性在线课程）而且我从未遇到过这样的事情。我也想了解其中涉及的算法。

同样，我不需要任何代码，因为我正在寻找自己解决这个问题。我只是要求一个解释。

更新：我想出了这段代码，它有效地确定了外部正方形的最小数量并迭代直到达到要求的坐标。

def spiral_index(x, y):
    small = max(x, y)*2 - 1
    min_number = small**2

    xpos = max(x, y)
    ypos = -max(x, y) + 1
    count = min_number

    while xpos != x:
          xpos -= 1
          count += 1
    while ypos != y:
          ypos += 1
          count += 1

    return count

但是，我的在线课程提交页面拒绝了代码，因为执行时间太长。所以我需要一种对初学者友好的快速方法。

Answer 1

我会先考虑这些事情：给定 x 和 y 坐标中的较远者，(1) 我们正在查看的正方形有多大？（其中有多少条目）； (2) 我们是否处于数字上升或下降的列？（行和 right/left 相同）； (3) 如果我们完成当前正方形，将我们的目标放在正方形的外边界上，目标的 "ahead" 有多少个数字？显然，如果我们知道总共有多少个广场，我们知道有多少个在前面，我们就可以计算出目标。

让我们将您的示例扩展到 (3, -1):

  c c c c c c
  b a a a a c
  b 4 3 2 a c
  b 5 0 1 a c
  b 6 7 8 a T
  b b b b b c

注意 a 正在完成 4x4 正方形； bs 5x5；和 cs，我们的目标 T 所在的 6x6。一个 6x6 的正方形有 36 个条目。我们认为 T 之前有 9 个条目，所以 T = 35 - 9 = 26.

Answer 2

考虑递归公式。

c c c c c
c b b b c
c b a b c
c b b b c
c c c c c

沿着枚举的螺旋线依次为 1 a、8 b、16 c、24 d 等。如果我们认为 a 为 0 级（特殊情况），b 为 1 级，依此类推，则每个正方形大小为 2*level+1 的有 8*level 字母。

从那里开始，坐标在正方形的哪一侧有4种情况（右，上，左，下）。确定坐标在哪个正方形中，简单的算术确定螺旋数。

Answer 3

下面是对一些代码的尝试，以让您了解我的内容。我不确定它是否完全没有错误，但也许您可以发现并修复任何错误:)（我错过了 x 等于 y 的情况吗？）

（注意，在线评估者可能不喜欢函数体中的打印语句。）

"""
  c  c  c  T2 c  c
  b  a  a  a  a  c
  T4 4  3  2  a  c
  b  5  0  1  a  c
  b  6  7  8  a  T1
  b  T3 b  b  b  c
"""

def f(x, y):
  square_size = 1

  if x > 0:
    square_size = 2 * x
  elif x < 0:
    square_size = -2 * x + 1
  if y > 0:
    square_size = max(square_size, 2 * y)
  elif y < 0:
    square_size = max(square_size, -2 * y + 1)

  corner_length = square_size * 2 - 1
  offset = square_size // 2

  # Top-right corner (even square side)
  if square_size % 2 == 0:
    # Target is on the right
    if abs(x) > abs(y):
      num_ahead = corner_length - (offset + y)
    # Target is on the top
    else:
      num_ahead = offset + x - 1

  # Bottom-left corner (odd square side)
  else:
    # Target is on the left
    if abs(x) > abs(y):
      num_ahead = corner_length - (offset - y) - 1
    # Target is on the bottom
    else:
      num_ahead = offset - x

  print ""
  print "Target: (%s, %s)" % (x, y)
  print "Square size: %sx%s" % (square_size, square_size)
  print "Corner length: %s" % corner_length
  print "Num ahead: %s" % num_ahead

  return square_size * square_size - 1 - num_ahead

T1 = (3, -1)
T2 = (1, 3)
T3 = (-1, -2)
T4 = (-2, 1)

print f(*T1)
print f(*T2)
print f(*T3)
print f(*T4)

输出（参见代码片段顶部的插图）：

Target: (3, -1)
Square size: 6x6
Corner length: 11
Num ahead: 9
26

Target: (1, 3)
Square size: 6x6
Corner length: 11
Num ahead: 3
32

Target: (-1, -2)
Square size: 5x5
Corner length: 9
Num ahead: 3
21

Target: (-2, 1)
Square size: 5x5
Corner length: 9
Num ahead: 7
17

螺旋图案：如何找到给定坐标的数字？

Spiral Pattern: how do I find a number given coordinates?

python

algorithm

spiral