python - 螺旋图案 : how do I find a number given coordinates?

Question

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

4 < 3 < 2
v       ^
5   0 > 1
v
6 > 7 > 8

如果输入是(1, -1)，该函数将返回8。

我不是在寻找代码。我正在寻找有关螺旋模式如何工作的解释，因为我对编程相对较新(参加介绍性在线类(class))，而且我从未遇到过这样的事情。我也想了解其中涉及的算法。

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

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

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

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

Answer 1

这里尝试使用一些代码来说明我的想法 had in mind 。我不确定它是否完全没有错误，但也许您可以发现并修复任何错误:)(我是否错过了 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