Spiral neighbourhoods

Question

If we take the natural numbers and roll them up counter clock-wise into a spiral we end up with the following infinite spiral:

                  ....--57--56
                             |
36--35--34--33--32--31--30  55
 |                       |   |
37  16--15--14--13--12  29  54
 |   |               |   |   |
38  17   4---3---2  11  28  53
 |   |   |       |   |   |   |
39  18   5   0---1  10  27  52
 |   |   |           |   |   |
40  19   6---7---8---9  26  51
 |   |                   |   |
41  20--21--22--23--24--25  50
 |                           |
42--43--44--45--46--47--48--49

Given some number in that spiral your task is to determine its neighbours - meaning the element above, left, right and below it.

Example

If we have a look at 27 we can see that it has the following neighbours:

• above: 28
• left: 10
• right: 52
• below: 26

So the output would be: [28,10,52,26]

Rules

• Input will be a number \$n \geq 0\$ in any default I/O format
• Output will be a list/matrix/.. of that numbers' 4 neighbours in any (consistent!) order
• You may work with a spiral that starts with 1 instead of 0, however you should specify that in your answer

Examples

The output is in the format [above,left,right,below] and uses a 0-based spiral:

0  ->  [3,5,1,7]
1  ->  [2,0,10,8]
2  ->  [13,3,11,1]
3  ->  [14,4,2,0]
6  ->  [5,19,7,21]
16  ->  [35,37,15,17]
25  ->  [26,24,50,48]
27  ->  [28,10,52,26]
73  ->  [42,72,74,112]
101  ->  [100,146,64,102]
2000  ->  [1825,1999,2001,2183]
1000000  ->  [1004003,1004005,999999,1000001]

Answer 1

R, 156 bytes

function(n){g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))
x=g(sinpi)
y=g(cospi)
a=x[n]
b=y[n]
which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))}

Try it online!

• posted another R answer since it's a slightly different approach than @ngn
• 1-indexed
• neighbours are always sorted by ascending value
• saved 6 bytes removing round and using cospi(x)/sinpi(x) which are more precise than cos(x*pi)/sin(x*pi) in case of half numbers (0.5, 1.5 etc...)
• saved another byte removing the minus on y coordinates since the result is the same (just up/down neighbours are reversed)

---

Explanation :

If we look at the matrix coordinates of the values, considering the first value 0 placed at x=0, y=0, they are :

x = [0,  1,  1,  0, -1, -1, -1,  0,  1,  2,  2,  2,  2,  1,  0, ...] 
y = [0,  0,  1,  1,  1,  0, -1, -1, -1, -1,  0,  1,  2,  2,  2, ...]

The x coordinates follow the A174344 OEIS sequence with the recursive formula :

a(1) = 0, a(n) = a(n-1) + sin(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

The same formula holds for y matrix coordinates, but with cos instead of sin and negated :

a(1) = 0, a(n) = a(n-1) - cos(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

So, in R we can translate the formula to this function, taking sinpi/cospi as parameter :

g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))

and we generate the two coordinates vectors (we don't negate the y coords since we'll get the same result, just with up/down neighbours reversed) :

x=g(sinpi)
y=g(cospi)

Note that we have generated (n+2)^2 coordinates, which are more than the minimum necessary coordinates containing both n and their neighbours (a tighter bound would be (floor(sqrt(n))+2)^2 but unfortunately is less "golfy").

Therefore, now that we have all the coordinates, we first search the coordinates a,b corresponding to our n :

a=x[n]
b=y[n]

finally we select the positions of their neighbours, i.e. :

• the up/down neighbours where x == a and y == b+1 or b-1
• the right/left neighbours where y == b and x == a+1 or a-1

using :

which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))

Answer 2

Brain-Flak, 238 bytes

((){[()]<((({}[((()))]<>)<<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>)<<>({}<(((({}{})()){}<>({}))()())<>>)<>>()())<>{{}((()()()[({})]){}<>({}<{}>))(<>)}>}{}){<>((((())()())()())()())(<>)}{}{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

Try it online!

Output is in the order left, up, right, down.

Explanation

# If n is nonzero:
((){[()]<

  ((

    # Push 1 twice, and push n-1 onto other stack.
    ({}[((()))]<>)

    # Determine how many times spiral turns up to n, and whether we are on a corner.
    # This is like the standard modulus algorithm, but the "modulus" used
    # increases as 1, 1, 2, 2, 3, 3, ...
    <<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>

  # Push n-1: this is the number behind n in the spiral.
  )<

    # While maintaining the "modulus" part of the result:
    <>({}<

      # Push n+2k+1 and n+2k+3 on top of n-1, where k is 3 more than the number of turns.
      # n+2k+1 is always the number to the right in the direction travelled.
      # If we are on a corner, n+2k+3 is the number straight ahead.
      (((({}{})()){}<>({}))()())<>

    >)<>

  # Push n+1.  If we are on a corner, we now have left, front, right, and back
  # on the stack (from top to bottom)
  >()())

  # If not on a corner:
  <>{{}

    # Remove n+2k+3 from the stack entirely, and push 6-2k+(n+1) on top of the stack.
    ((()()()[({})]){}<>({}<{}>))

  (<>)}

>}{})

# If n was zero instead:
{

  # Push 1, 3, 5, 7 on right stack, and implicitly use 1 (from if/else code) as k.
  <>((((())()())()())()())

(<>)}{}

# Roll stack k times to move to an absolute reference frame
# (switching which stack we're on each time for convenience)
{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

Answer 3

Perl 6Raku, 94 83 78 bytes

{my \s=0,|[+] flat((1,i...)Zxx flat(1..Inf Z 1..Inf));map {first :k,s[$_]+$^d,s},i,-1,1,-i}

{my \s=0,|[+] flat((1,i...)Zxx(1,1.5...*));map {first :k,s[$_]+$^d,s},i,-1,1,-i}

{my \s=0,|[\+] flat (1,*i...*)Zxx(1,3/2...*);(grep :k,1==(s[$_]-*).abs,s)[^4]}

Try it online!

s is a lazy, infinite list of spiral coordinates, represented as complex numbers. It's constructed from two other infinite lists: 1, *i ... * makes the list 1, i, -1, -i .... 1, 1.5 ... * makes the list 1, 1.5, 2, 2.5, 3, 3.5 .... Zipping these two lists together with list replication produces the list of steps from each spiral coordinate to the next: 1, i, -1, -1, -i, -i, 1, 1, 1, i, i, i .... (The fractional parts of the right-hand arguments to the list replication operator are discarded.) Doing a triangular addition reduction ([\+]) on this list (and pasting 0 onto the front) produces the list of spiral coordinates.

Finally, starting from the complex number s[$_] ($_ being the sole argument to the function), we look up the indexes (first :k) in the spiral of the complex numbers which are offset from that number by i, -1, 1, and -i.

I shaved a few bytes off by searching for the matching elements in index order, and by testing that the absolute value of the complex difference between the coordinates is 1, rather than testing for 1, -1, i, and -1 explicitly.

Answer 4

MATL, 15 bytes

2+1YLtG=1Y6Z+g)

Input and output are 1-based.

The output gives the left, down, up and right neighbours in that order.

Try it online! Or verify all test cases except the last two, which time out on TIO.

2+      % Implicit input: n. Add 2. This is needed so that
        % the spiral is big enough
1YL     % Spiral with side n+2. Gives a square matrix
t       % Duplicate
G=      % Compare with n, element-wise. Gives 1 for entry containing n
1Y6     % Push 3×3 mask with 4-neighbourhood
Z+      % 2D convolution, keeping size. Gives 1 for neighbours of the
        % entry that contained n
g       % Convert to logical, to be used as an index
)       % Index into copy of the spiral. Implicit display

Answer 5

R, 172 bytes

function(x,n=2*x+3,i=cumsum(rep(rep(c(1,n,-1,-n),l=2*n-1),n-seq(2*n-1)%/%2))){F[i]=n^2-1:n^2
m=matrix(F,n,n,T)
j=which(m==x,T)
c(m[j[1],j[2]+c(-1,1)],m[j[1]+c(-1,1),j[2]])}

Try it online!

This is R, so obviously the answer is 0-indexed.

Most of the work is creating the matrix. Code inspired by: https://rosettacode.org/wiki/Spiral_matrix#R

Answer 6

Python 2, 177 164 146 144 bytes

def f(n):N=int(n**.5);S=N*N;K=S+N;F=4*N;return[n+[F+3,[-1,1-F][n>K]][n>S],n+[F+5,-1][n>K],n+[[1,3-F][n<K],-1][0<n==S],n+[F+7,1][n<K]][::1-N%2*2]

Try it online!

Calculates u,l,r,d directly from n.

Answer 7

JavaScript (V8),  165 162  151 bytes

Prints the indices.

f=(n,x=w=y=n+2)=>y+w&&[-1,0,1,2].map(d=>(g=(x,y)=>(k=2*Math.max(x,-x,y,-y))*k+(k+x+y)*(y>=x||-1))(x+d%2,y+~-d%2)-n||print(g(x,y)))|f(n,x+w?x-1:(y--,w))

Try it online!

How?

For \$x, y \in \mathbb{Z}\$, we compute the 0-based index \$I_{x,y}\$ of the spiral with:

$$A_{x,y}=2\cdot\max(|x|,|y|)$$ $$S_{x,y}=\begin{cases}1,&\text{if }y\ge x\\-1,&\text{if }y<x\end{cases}$$ $$I_{x,y}=A_{x,y}^2+(A_{x,y}+x+y)\times S_{x,y}$$

Adapted from this answer from math.stackexchange.
Also used in Can you make your way through the Ulam spiral?
Saved 1 byte thanks to @att.

Answer 8

APL (Dyalog Unicode), ⁶⁶ 60 bytes

{(⊃⍸⍵=s)⌷{⊢/4 2⍴⍵}⌺3 3⊢s←{⌽⍉⍵⍪⍨⌽(⍳(⌈/⍴⍵)+⌈/,⍵)~,⍵}⍣(⍵+4)⊢⍪1}

Try it online!

1-indexed.

I'd been wanting to solve spiral challenges in APL for a while, so I figured I'd make a spiral creating function for this. I've used simple array magic to make it(and ngn will probably find an insane math relation to calculate it, most likely).

-6 bytes from Adám.

Explanation

{(⊃⍸⍵=s)⌷{⊢/4 2⍴⍵}⌺3 3⊢s←{⌽⍉⍵⍪⍨⌽(⍳(⌈/⍴⍵)+⌈/,⍵)~,⍵}⍣(⍵+4)⊢⍪1} input → n
                                                         ⍪1  to [[1]],
                                                  ⍣(⍵+4)⊢    apply the following n+4 times:
                                (⍳(⌈/⍴⍵)+⌈/,⍵)               range 1..max(i)+max(shape(i))
                                              ~,⍵            without i
                            ⍵⍪⍨                              add that as a row

                          ⌽⍉                                 rotate 90 degrees clockwise

                       s←                                    assign the spiral to s
         {       }⌺3 3⊢                                      to the 3x3 paritions of the spiral:
          ⊢/4 2⍴⍵                                            get every 2nd element   

 ⊃⍸⍵=s                                                       find indices of n in the spiral                
(     )⌷                                                     and index into the matrix of neighbours 

Answer 9

PHP (>=5.4), 208 bytes

<?$n=$argv[1];for(;$i++<($c=ceil(sqrt($n))+($c%2?2:3))**2;$i!=$n?:$x=-$v,$i!=$n?:$y=+$h,${hv[$m&1]}+=$m&2?-1:1,$k++<$p?:$p+=$m++%2+$k=0)$r[-$v][+$h]=$i;foreach([0,1,0,-1]as$k=>$i)echo$r[$x+$i][$y+~-$k%2].' ';

To run it:

php -n -d error_reporting=0 <filename> <n>

Example:

php -n -d error_reporting=0 spiral_neighbourhoods.php 2001

Or Try it online!

Notes:

• The -d error_reporting=0 option is used to not output notices/warnings.
• This spiral starts with 1.

---

How?

I'm generating the spiral with a modified version of this answer in a 2 dimensional array.

I decide on the size of the spiral based on the input n with a formula to always get an extra round of numbers in the spiral (guarantee for existence of above/below/left/right). An extra round of numbers means +2 in height and +2 in width of the 2 dimensional array.

So if n will be located in a spiral with maximum size of 3*3, then generated spiral will be 5*5.

Spiral size is c*c where c = ceil(sqrt(n)) + k, if ceil(sqrt(n)) is odd, then k is 2 and if ceil(sqrt(n)) is even, then k is 3.

For example, the above formula will result in this:

• If n = 1 then c = 3 and spiral size will be 3*3
• If n <= 9 then c = 5 and spiral size will be 5*5
• If n <= 25 then c = 7 and spiral size will be 7*7
• If n <= 49 then c = 9 and spiral size will be 9*9
• And so on ...

While generating the spiral, I store the x and y of n and after generation, I output the elements above/below/left/right of it.