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

Question

给定一个螺旋形的数字，其中数字以三角形的形式排列，我需要编写一个函数，它接受一个数字和 returns 这个数字的坐标

           15
           16 14
           17 3  13
           18 4  2  12
           19 5  0> 1  11
           20 6  7  8  9  10
           21 22 23 24 25 26 27 28

例如 17 结果在 x 和 y 中是 (-2, 2)

我已经做过类似的任务，但螺旋线是方形的，程序接收坐标 (x, y) 作为输入并返回一个数字。简而言之，我计算了正方形的大小和偏移量。

我很乐意提供任何帮助

Answer 1

TL;DR: 底部的工作代码

首先考虑每个三角形中有多少个数字：

第一个在每条边上包含 3 个数字
第二个每边包含6个数字
第三个每条边有9个数字

这就是我们的模式。三角形 i 包含 9i 个数字，在我们做任何其他事情之前，我们需要将我们的数字除以 9 并找到结果的 triangle root（并将其向下舍入）：

找出直角三角形后，还剩下三件事要做：

你需要找到起点

这很简单，因为三角形 i 的“最后一点”将始终是 (2i, i)。

你需要找到正确的边缘

您已经知道您的三角形有 i 长边，因此通过取余数之和（来自原始 divmod 和求根）并将其除以 3，您可以找到右边缘。

你需要找到这条边上的正确点

这一点很简单 - 你有 3 种类型的边，水平、垂直和对角线。根据您必须将“最终剩余价值”应用于“边缘原点”的类型：

(-r, -r)对角线
(0, r) 为垂直
(r, 0) 为横向

相对于 上一个 三角形的最大点到达右边缘，您只需应用这些换位的累积和：

(-r, -r)对角线
(-i, -i+r) 为垂直
(-i+r, 0)为横向

综合起来

def triangle_root(x):
    return int((8 * x + 1) ** 0.5 - 1) // 2

def spiral(v):
    # Identify the current triangle
    i = min(v, triangle_root(max(0, (v - 1) / 9)) + 1)
    # Compute the coordinates for the max value of this triangle
    xi, yi = 2 * i, i
    # Compute the point index in the current triangle
    # In other words, subtract the previous triangle max
    r = v - 9 * (i - 1) * i // 2
    # Compute the edge length for the current triangle
    length = 3 * max(1, i)
    # Compute the current edge and the location in that edge
    edge, r = divmod(r, length)
    # Apply the relevant transform depending on the edge
    if edge == 1: # vertical
        dx, dy = -length, r - length
    elif edge == 2: # horizontal
        dx, dy = r - length, 0
    else: # diagonal
        dx, dy = -r, -r
    
    return xi + dx, yi + dy

Answer 2

No code, but I would start with something like the following:

rearrange the numbers to understand the structure of the triangle-spiral

 0
 1  2
 3  4  5
 6  7  8  9
10 11 12 13 14
15 16 17 18 19 20
21 22 23 24 25 26 27 
...

Please note that if we take complete lines and arrange them back to spiral form, we will arrive at complete triangles.

Add the coordinates (I hope I understand them correctly.)

0   0                      0, 0
1   1  2                   1, 0    0, 1
2   3  4  5               -1, 2   -1, 1  -1, 0

3   6  7  8  9            -1,-1    0,-1   1,-1   2,-1
4  10 11 12 13 14          3,-1    2, 0   1, 1   0, 2  -1, 3 
5  15 16 17 18 19 20      -2, 4   -2, 3  -2, 2  -2, 1  -2, 0  -2,-1

6  21 22 23 24 25 26 27   -2,-2    ...
...

I have also added a row number r in front: three rows form a complete "turn" in the spiral.

You can see the coordinate pattern within the rows, it depends of course on how it can be divided by 3:

rows divisible by 3 start at -r/3, -r/3 and increment x
rows with remainder 1 start at 2*(r-1)/3+1, -(r-1)/3, decrement x and increment y
rows with remainder 2 start at -(r+1)/3, 2*(r+1)/3 and decrement y

Figure out in which row we actually are

The last number n in row r is "n = {sum i for i from 0 to r+1} = (r+1)(r+2)/2". We solve this for r and arrive at:

r = -3/2 + sqrt(9/4 + 2n)

Only the positive solution is relevant.

If we insert a number n like 12, we get r = 3.6 which means we are somewhere in row 4 as expected, please check the row numbers.

Put things together

Calculate the current row number.
Calculate the position within the row by subtracting the last number of the previous row. This is n_prev = r*(r+1)/2 in general and n_prev = 4*5/2 = 10 in the example with n=12. The position within the row for the example is pos = 12-10 = 2
Calculate the remainder of the current row number on division by 3. For the example we have 4 = 3*1 + 1
Now calculate the coordinates by selecting the appropriate formula. For the example we have row 4, remainder 1 and position 2, so we need

[2*(r-1)/3+1, -(r-1)/3] + pos*[-1, 1] = [2*3/3+1, -3/3] + [-2,2] = [1,1]

Again, please check with your initial spiral-triangle.

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

how do I find a coordinates given a number in Spiral pattern?

python

algorithm

spiral