4
\$\begingroup\$

This question will be deleted soon, do not read/answer it

Introduction

Given one matrix A x A and a number of movements N.

You will need to walk like a spiral starting in (1; 1):

  1. right while possible, then
  2. down while possible, then
  3. left while possible, then
  4. up while possible, repeat until got N.

Challenge

You can only take as input the numbers A and N.

You must output the final (row; column) after walking N steps in the conditions explained above. You can not invert the output order.

You can use indexes starting with zero as well. Just state it in your answer.

Program or function allowed.

This is , shortest answer in bytes wins.

Sample

For input (A = 8; N = 54).

enter image description here

The output should be (5; 6).

Another samples

input: A=8, N=64
output: [5, 4]

input: A=15, N=14
output: [1, 14]

input: A=26, N=400
output: [22, 9]

input: A=1073741824, N=1152921504603393520
output: [536871276, 536869983]

Restrictions

1 <= A <= 230

1 <= N <= (A2 OR the below higher number supported in your language).


And, if you want a generic formula.

\$\endgroup\$
  • 1
    \$\begingroup\$ About restrictions: there are common languages that cannot handle 60 bits integers. Javascript for instance is limited to 53 bits for numbers stored as IEEE 754 64 bits floating point, or 32 bits for signed integers \$\endgroup\$ – edc65 Apr 10 '16 at 17:21
  • 1
    \$\begingroup\$ A=2^15 (2^30 cells) will run in reasonable time (seconds or minutes) and memory (gigabytes) if we trace through every cell. A=2^30 (2^60cells) will not. If your intention is to disallow naive algorithms you should state it in the question. Otherwise you should reduce the max size of the matrix \$\endgroup\$ – Level River St Apr 10 '16 at 17:30
  • 1
    \$\begingroup\$ I've voted to close as it is not clear without further clarification whether the existing answer is valid or not: as stated by the poster, it is limited by memory to considerably less than A=2^30. Please clarify \$\endgroup\$ – Level River St Apr 10 '16 at 17:42
  • 1
    \$\begingroup\$ @WashingtonGuedes But you haven't stated if explicit methods that are limited by memory are allowed or not \$\endgroup\$ – Luis Mendo Apr 10 '16 at 17:56
  • 1
    \$\begingroup\$ @WashingtonGuedes also, we are discussing a hardware restriction, not a language restriction. \$\endgroup\$ – Level River St Apr 10 '16 at 18:02
2
\$\begingroup\$

MATL, 24 bytes

This works in release 16.0.0 of the language, which predates the challenge.

2^Q6Y3GYLG2\?!P!}P]-=2#f

Output is 1-based, as in the examples.

A^2 and N are limited to 2^53 as per the language's default data type (double). In addition, since the whole matrix is being generated, memory will limit A to significantly lower values.

Try it online! (In the online version I have changed the order of G and 6Y3 so it works in the new 16.1.0 release)

Explanation

This uses MATL's builtin for generating an outward spiral. To make it inward, a subtraction and a reversal are needed. The direction of reversal depends on whether A is odd or even.

2^Q     % take input A implicitly. Compute A^2+1
6Y3GYL  % outward spiral of side length A
G2\     % is A odd?
?       % if so
  !P!   %   flip matrix horizontally
}       % else
  P     %   flip matrix vertically
]       % end if
-       % compute A^2+1 minus the matrix element-wise, so (1,1) contains 1
=       % take input N implicitly. Set matrix entry that contains that value to true
2#f     % row and column index of that true value
\$\endgroup\$
  • 1
    \$\begingroup\$ Can this run the last test case? If you're genrating the whole spiral, I doubt you have time or memory for it. See my comment on the last question \$\endgroup\$ – Level River St Apr 10 '16 at 17:34
  • \$\begingroup\$ @LevelRiverSt Yes, it genererates the whole spiral. Size is limited by memory. I'll state that in the answer. Thanks for the indication. I totally agree with your comment to the challenge BTW. I'm waiting for OP's response, and depending on that I may have to delete my answer (or use a different approach) \$\endgroup\$ – Luis Mendo Apr 10 '16 at 17:38
  • \$\begingroup\$ When you say "compute A^2-1 minus the matrix element-wise, so (1,1) contains 1", do you mean A^2+1, which was calculated earlier at the beginning of the code? \$\endgroup\$ – poi830 Apr 11 '16 at 12:15
  • \$\begingroup\$ @poi830 Oops yes, sorry about the confusion. Corrected \$\endgroup\$ – Luis Mendo Apr 11 '16 at 13:24

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