Determine the position of a non-negative number in the infinite spiral

Question

Definition

The infinite spiral used in this question has 0 on the position (0,0), and continues like this:

16-15-14-13-12
 |           |
17  4--3--2 11
 |  |     |  |
18  5  0--1 10
 |  |        |
19  6--7--8--9
 |
20--21...

It is to be interpreted as a Cartesian plane.

For example, 1 is on the position (1,0), and 2 is on the position (1,1).

Task

Given a non-negative integer, output its position in the spiral.

Specs

• Your spiral can start with 1 instead of 0. If it starts with 1, please indicate so in your answer.
• Output the two numbers in any sensible format.

Testcases

The testcases are 0-indexed but you can use 1-indexed as well.

input output
0     (0,0)
1     (1,0)
2     (1,1)
3     (0,1)
4     (-1,1)
5     (-1,0)
6     (-1,-1)
7     (0,-1)
8     (1,-1)
9     (2,-1)
100   (-5,5)

Answer 1

Python, 46 bytes

f=lambda n:n and 1j**int((4*n-3)**.5-1)+f(n-1)

Dennis's answer suggested the idea of summing a list of complex numbers representing the unit steps. The question is how to find the number of quarter turns taken by step i.

[0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7]

These are generated by int((4*k-n)**.5-1), and then converted to a direction unit vector via the complex exponent 1j**_.

Answer 2

Python, 53 bytes

lambda n:sum(1j**int((4*i+1)**.5-1)for i in range(n))

Answer 3

Jelly, 22 16 10 bytes

Ḷ×4‘ƽ’ı*S

This uses the quarter-turn approach from @xnor's/@orlp's answer.

Indexing is 0-based, output is a complex number. Try it online! or verify all test cases.

How it works

Ḷ×4‘ƽ’ı*S  Main link. Argument: n (integer)

Ḷ           Unlength; create the range [0, ..., n - 1].
 ×4         Multiply all integers in the range by 4.
   ‘        Increment the results.
    ƽ      Take the integer square root of each resulting integer.
      ’     Decrement the roots.
       ı*   Elevate the imaginary unit to the resulting powers.
         S  Add the results.

Answer 4

Python 2, 72 62 bytes

n=2;x=[]
exec'x+=n/2*[1j**n];n+=1;'*input()
print-sum(x[:n-2])

Thanks to @xnor for suggesting and implementing the quarter-turn idea, which saved 10 bytes.

Indexing is 0-based, output is a complex number. Test it on Ideone.

Answer 5

Ruby, 57 55 bytes

This is a simple implementation based on Dennis's Python answer. Thanks to Doorknob for his help in debugging this answer. Golfing suggestions welcome.

->t{(1...t).flat_map{|n|[1i**n]*(n/2)}[0,t].reduce(:+)}

Ungolfed:

def spiral(t)
  x = []
  (1...t).each do |n|
    x+=[1i**n]*(n/2)
  end
  return x[0,t].reduce(:t)
end

Answer 6

JavaScript (ES7), 75 bytes

n=>[0,0].map(_=>((a+2>>2)-a%2*n)*(a--&2?1:-1),a=(n*4+1)**.5|0,n-=a*a>>2)

Who needs complex arithmetic? Note: returns -0 instead of 0 in some cases.

Answer 7

Batch, 135 bytes

@set/an=%1,x=y=f=l=d=0,e=-1
:l
@set/ac=-e,e=d,d=c,n-=l+=f^^=1,x+=d*l,y+=e*l
@if %n% gtr 0 goto l
@set/ax+=d*n,y+=e*n
@echo %x%,%y%

Explanation: Follows the spiral out from the centre. Each pass through the loop rotates the current direction d,e by 90° anticlockwise, then the length of the arm l is incremented on alternate passes via the flag f and the next corner is calculated in x,y, until we overshoot the total length n, at which point we backtrack and print the resulting co-ordinates.