“Snail” number sequence lookup

Question

You are given integers N and M, 1 <= N,M <= 10^6 and indexes i and j. Your job is to find the integer at position [i][j]. The sequence looks like this (for N=M=5, i=1, j=3 the result is 23):

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

Shortest code wins. Good luck!

Answer 1

Mathematica, 63 55 bytes

f=If[#5<1,#+#4,f[#+#2,#3-1,#2,#5-1,#2-1-#4]]&;g=1~f~##&

This defines a function g which can be called like

g[5, 5, 1, 3]

I'm using a recursive approach. It uses up to 2(N+M) iterations, depending on how far down the spiral the result is found. It does handle all inputs (up to g[10^6,10^6,5^5-1,5^5], which requires the most iterations) within a few seconds, but for larger inputs, you'll need to increase the default iteration limit like

$IterationLimit = 10000000;

Basically, if k is the starting number of the spiral, I'm checking if the j index is 0 in which case I can just return k + i. Otherwise, I throw away the top row, rotate the spiral by 90 degrees (anti-clockwise), increment k accordingly, and look at the remaining spiral instead. We can move to the next spiral with the following mapping of parameters:

• k_n+1 = k_n + m_n
• M_n+1 = N_n - 1
• N_n+1 = M_n
• i_n+1 = j_n - 1
• j_n+1 = n_m - i_n - 1

This assumes that M is the width and N is the height.

Answer 2

Pyth, 25 bytes

D(GHYZ)R?+G(tHGtZt-GY)ZhY

This defines a function, (. Example usage:

D(GHYZ)R?+G(tHGtZt-GY)ZhY(5 5 1 3

prints 23.

This is algorithmically identical to the Mathematica answer by Martin Büttner, though it was developed independently. As far as I can tell, that's the only good way to do it.

Note that Pyth cannot handle the full input range on my machine, it will overflow the stack and die with a segfault on large inputs.

Answer 3

Haskell, 44

z j i m n|j==0=i+1|0<1=z(n-i-1)(j-1)n(m-1)+n

this uses the regular recursive approach