1

I have a matrix of variable sizes, and want to find the coordinates of the n amount of squares traveled. In this example the size of the matrix is: 8. Meaning the amount of rows and columns.

enter image description here

Starting at point x, y: (1, 1) and;

  • Going as far right as possible
  • Going as far down as possible
  • Going as far left as possible
  • Going as far up as possible

Given that i = 53

Starting at n = 0and adding up 1to nfor each square traveled, by reaching n == i calculate the coordinates.

What I have tried:

(Disclaimer: This is mathematically unrelated, I'm only posting this so you can see how naive I am)

In my original programming problem I have achieved it via creating a variable mwith the size of the matrix so in this case m = 8, and deducing it after each rightand leftmovements.

y = 0 //y will move first, starts offboard at imaginary column `0`
x = 1 //start from row 1
m = 8
right: { y+= i; m -= 1;} //x = 1, y = 8 / m = 7
down: {  x+= m; }//x = 8, y = 8
left: { y-= m; m -= 1; } //x = 8, y = 1 / m = 6
up: { x-=m; } // x = 2, y = 1

And iterating, until another created variable sumofsteps, to sum up the amount of m squares traveled reach i which is in this case 53.''

This is, of course very naive, since in some cases the matrix can be as big as 1073741824 and the number of steps 1152921504603393520, which in my program takes too long to solve.

Back to reality:

What is a mathematical formula to find the coordinates after n amount of squares traveled?

Vinícius
  • 115
  • 1
    This won't answer your question, but there is a simple algorithm to build this matrix, that does not involve a loop on $x$ and $y$. See this on Rosetta Code (the Octave version implementes this method, and if you know a bit of Matlab or Matlab-like language it should be readable). See also the discussion page. Of course it's only usable if the matrix is small enough to fit in memory. – Jean-Claude Arbaut Nov 08 '19 at 05:11

1 Answers1

1

I don't give a closed form, but a way to find out the $x,y$ coordinates more quickly than looping through the whole square.

Think of the matrix as many nested squares, the outside one being layer $1$. You can easily find the coordinate of the upper left corner of each layer, since it's the first square being traveled after all the preceding layers have been traveled. That is, for the layer $1$, it's $1$, for the layer $2$ it's $4(n-1)+1$, for the layer $3$ it's $4(n-1)+4(n-3)+1$ and so on.

For the layer $k$, the position of the upper left corner in the sequence of traveled squares is:

$$1+4\sum_{i=1}^{k-1} (n-2i+1)=1+4n(k-1)-8\frac{k(k-1)}{2}+4(k-1)\\ =1+4(k-1)(n+1-k)$$

So, if $N$ squares have been traveled, the cell is in the maximum layer $k$ such that $1+4(k-1)(n+1-k)\le N$.

You can find this $k$ by solving the quadratic equation $1+4(k-1)(n+1-k)=N$:

$$k=\lfloor1+\frac n2-\sqrt{n^2+1-N}\rfloor$$

The coordinates of the upper left corner of this layer are $(k,k)$. Then with the difference $N-(1+4(k-1)(n+1-k))$ you will find on which side you are on this layer, and the exact position on the side.

Jean-Claude Arbaut
  • 23,277