Algorithm find number position in snail 2D array

I have a 2D array square size.

such as :

(3x3)         (4x4)
1 2 3    or   1   2   3   4
8 9 4         12  13  14  5
7 6 5         11  16  15  6
              10  9   8   7

I am trying to find a solution to get by giving a value and the array size the Y, X position of the 2D array.

Exemple:

>> find_y_x_in_snail(3, 4)
1, 2
# in a 3x3 array, search value 4
return y=1 x=2

the only idea i have to create the snail in a 2D array and return the position.. not that great.

I found the opposite algorithm here (first exemple)

Any idea ?

Solution

You could use this function:

def find_y_x_in_snail(n, v):
    r = 0
    span = n
    while v > span:
        v -= span
        r += 1
        span -= r%2
    d, m = divmod(r,4);
    c = n-1-d
    return [d, d+v, c, c-v][m], [d+v-1, c, c-v, d][m] # y, x

Explanation

r is the number of corners the "snake" needs to take to get to the targetted value.

span is the number of values in the current, straight segment of the snake, i.e. it starts with n, and decreases after the next corner, and again every second next corner.

d is the distance the snake has from the nearest side of the matrix, i.e. the "winding" level.

m indicates which of the 4 sides the segment -- containing the targetted value -- is at:

0: up
1: right
2: down
3: left

Depending on m a value is taken from a list with 4 expressions, each one tailored for the corresponding side: it defines the y coordinate. A similar method is applied (but with different expressions) for x.