1

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 ?

albttx
  • 3,444
  • 4
  • 23
  • 42
  • For the example, how is `y=2, x=1` giving `7`as the answer. I think you want the value of 3rd column and 2nd row, right?? – User_Targaryen Nov 08 '16 at 18:43
  • at `y=2, x=1` for `3x3` isn't the value `14` for the above example ? – SomeDude Nov 08 '16 at 18:43
  • Sorry guys for deleting, i made a mistake. all my apologies. @svasa for me `3x3` is the first exemple and `4x4` the second – albttx Nov 08 '16 at 19:11
  • http://stackoverflow.com/questions/18785462/mapping-elements-of-a-matrix-to-its-position-in-its-spiral-order-traversal ? – גלעד ברקן Nov 08 '16 at 19:42
  • גלעד ברקן The opposite, from the value get coordinates – albttx Nov 08 '16 at 19:48
  • Can you clarify. It would seem relatively easy to fill the array and then search for the position of the number you want. However are you asking for a function definition that could generalize to arbitrary size arrays and not solve it by brute force search? – Bradley Thomas Nov 08 '16 at 20:17
  • @BradThomas I know, but my first idea was to find this miracle function, and i wasn't able to find it myself. I rather learn the proper way. – albttx Nov 08 '16 at 20:39

1 Answers1

1

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.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • In fact I just notice I returned the tuple in the order x, y, while the function name has y_x, so ***I have switched*** the tuple returned in the `return` statement just now. – trincot Nov 08 '16 at 20:19