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)
  • 1
    Some bigger testcases would be nice. – orlp Aug 1 '16 at 3:38
  • @orlp Done. – – – Leaky Nun Aug 1 '16 at 3:39
  • Can we print coordinates as a complex number? – orlp Aug 1 '16 at 3:54
  • @orlp As long as it matches the regex. – Leaky Nun Aug 1 '16 at 3:57
  • 2
    I'm not sure how to interpret the regex requirement for return values. In some languages, the output of, e.g., a complex number, will depend on what function is called to print it. – Dennis Aug 1 '16 at 4:02

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**_.

  • Just keep this answer since you two came up with it independently... – Leaky Nun Aug 1 '16 at 5:25
  • Doubly awkward... I independently discovered it. But I guess your chat message was first, so no way to prove it. – orlp Aug 1 '16 at 5:25

Python, 53 bytes

lambda n:sum(1j**int((4*i+1)**.5-1)for i in range(n))
  • Just keep this answer since you two came up with it independently... – Leaky Nun Aug 1 '16 at 5:25

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.

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.
  • 3
    At which point will you rename Jelly to 'random noise'? – orlp Aug 1 '16 at 3:46
  • 2
    Right after all other esolangs do the same. It's only noise if you don't understand it. – Dennis Aug 1 '16 at 3:53
  • 2
    @orlp But Jelly is the one that looks the most like semi-random (emphasis on AltGr and punctuation modifier keys) hammering of a US International keyboard... – Adám Aug 1 '16 at 7:28

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
  • Do you need the second pair of parentheses? – Leaky Nun Aug 1 '16 at 5:53
  • @LeakyNun Over n/2. I think so. Otherwise it tries to divide the array by 2 instead of multiplying by n/2. I'll see what I can do about it. – Sherlock9 Aug 1 '16 at 5:59
  • I don't think you need flat_map when regular map works just as well on ranges. Also, [0,t] gets you the same entries from an array as [0...t] – Value Ink Aug 1 '16 at 8:15
  • See here for the discussion about flat_map chat.stackexchange.com/transcript/message/31403761#31403761. Thanks for the [0,t] tip. – Sherlock9 Aug 1 '16 at 8:17

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.

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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