8
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Very closely related. \$\endgroup\$ – Martin Ender Nov 17 '14 at 12:45
  • \$\begingroup\$ As well as this. \$\endgroup\$ – Martin Ender Nov 17 '14 at 12:55
  • 1
    \$\begingroup\$ You might want to clarify if M is the width or the height. \$\endgroup\$ – Martin Ender Nov 17 '14 at 12:57
  • \$\begingroup\$ @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. \$\endgroup\$ – M.Herzkamp Nov 17 '14 at 13:00
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Nov 17 '14 at 13:14
6
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.