# “Snail” number sequence lookup

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!

• Very closely related. – Martin Ender Nov 17 '14 at 12:45
• As well as this. – Martin Ender Nov 17 '14 at 12:55
• You might want to clarify if M is the width or the height. – Martin Ender Nov 17 '14 at 12:57
• @MartinBüttner: I think N corresponds to i and M to j. Then you need only specify, that the snail starts at i=j=0 and continues in j=0 direction. – M.Herzkamp Nov 17 '14 at 13:00
• Does our code need to complete in a reasonable amount of time with a reasonable amount of memory for the given limits? I can definitely write valid code for those parameters, which just generates the spiral and looks up the value, but I don't actually have 4 TB of memory lying around. – Martin Ender Nov 17 '14 at 13:14

# 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:

• kn+1 = kn + mn
• Mn+1 = Nn - 1
• Nn+1 = Mn
• in+1 = jn - 1
• jn+1 = nm - in - 1

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

• 51 bytes: If[#5<1,#+#4,#0[#+#2,#3-1,#2,#5-1,#2-1-#4]]&[1,##]& – LegionMammal978 Apr 22 '16 at 23:02

# 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.

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