Find the last position in a matrix walking like a spiral

4

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.

removed

Posted 2016-04-10T16:35:57.220

Reputation: 2 785

Question was closed 2016-04-10T18:57:28.183

1About 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 – edc65 – 2016-04-10T17:21:24.840

@edc65. You can use javascript, I will update – removed – 2016-04-10T17:28:38.967

1A=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 – Level River St – 2016-04-10T17:30:34.097

1I'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 – Level River St – 2016-04-10T17:42:29.203

I just stated the size of the number, not about the memory, but I edited with a formula – removed – 2016-04-10T17:55:13.140

1@WashingtonGuedes But you haven't stated if explicit methods that are limited by memory are allowed or not – Luis Mendo – 2016-04-10T17:56:54.133

1@WashingtonGuedes also, we are discussing a hardware restriction, not a language restriction. – Level River St – 2016-04-10T18:02:37.897

Sorry, for all troubles, I tried deleting this question, but I can not because it has answers.. I will try to make it a community question then – removed – 2016-04-10T18:05:38.360

1No need for making it CW? Just clarify about the memory – Luis Mendo – 2016-04-10T18:47:19.793

Perhaps we can discuss this in chat: https://chat.stackexchange.com/rooms/240/the-nineteenth-byte

– Sherlock9 – 2016-04-10T19:12:19.700

1Really there's no need to delete. It's a good question and I upvoted it. No "trouble" caused. The fairest thing to do (as you already have an answer) would be to reduce the max value of A which would let naive solutions work (such as 2^12) or say that the solution should work in theory notwithstanding memory and time constraints. However if you decide to rule that A=2^30 is required, @LuisMendo said he would delete or revise his answer. The purpose of putting on hold is to ensure more answers like Luis's don't come piling in till your intention is clarified. – Level River St – 2016-04-10T21:10:03.270

Another thing you can do is have a main codegolf competition admitting naive solutions, but offer a bounty on the side for the most efficient/elegant algorithm, if that's what you were hoping to see.. An advantage of this is that bounties can be awarded under subjective criteria, whereas the main competition must be objective. – Level River St – 2016-04-10T21:10:58.790

Answers

2

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

Luis Mendo

Posted 2016-04-10T16:35:57.220

Reputation: 87 464

1Can 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 – Level River St – 2016-04-10T17:34:27.277

@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) – Luis Mendo – 2016-04-10T17:38:25.413

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? – poi830 – 2016-04-11T12:15:48.577

@poi830 Oops yes, sorry about the confusion. Corrected – Luis Mendo – 2016-04-11T13:24:22.970

Asked: 2016-04-10T16:35:57.220

Viewed: 172 times

Active: 2016-04-11T13:24:37.907