19
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>
\$\endgroup\$
  • \$\begingroup\$ Very impressive! I guess you're not generating the whole spiral as others do, are you? \$\endgroup\$ – ბიმო Jul 21 '18 at 16:30
6
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ "slightly different" :) \$\endgroup\$ – ngm Jul 23 '18 at 13:25
  • \$\begingroup\$ @ngm: eheh... since the rosetta code you used is pretty "obscure" to me, I assumed is somehow generating the position indexes of the matrix in a different but similar fashion than my OEIS sequences :D \$\endgroup\$ – digEmAll Jul 23 '18 at 14:42
1
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Perl 6, 94 83 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}

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 165 bytes

Prints the indices with alert().

f=(n,x=w=y=n+2)=>y+w&&[0,-1,0,1].map((d,i)=>(g=(x,y,A=Math.abs)=>(k=A(A(x)-A(y))+A(x)+A(y))*k+(k+x+y)*(y>=x||-1))(x+d,y+~-i%2)-n||alert(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}=||x|-|y||+|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)

\$\endgroup\$
  • \$\begingroup\$ This seems to work fine with smaller numbers, but I get an error when testing this with a large number like 2000. Error on tio.run: RangeError: Maximum call stack size exceeded and error in browser console: InternalError: too much recursion. Am I doing something wrong? \$\endgroup\$ – Night2 Jul 22 '18 at 12:26
  • 1
    \$\begingroup\$ @Night2 The number of iterations grows in \$4n^2\$, so the call stack quickly overflows. The same kind of restriction applies to most JS recursive answers, although the exact limit depends on the platform it's running on. \$\endgroup\$ – Arnauld Jul 22 '18 at 12:35
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 1YL- MATLAB has aspiral function? When did MATLAB turn into Mathematica?! \$\endgroup\$ – sundar Jul 20 '18 at 17:44
  • \$\begingroup\$ Yeah, I duckduckgo-ed it after seeing what 1YL meant, and this Rosetta code entry was the only place I could find to confirm that it's a MATLAB thing and not just a MATL convenience function. I was starting to think it might be something you added to MATL for golfing, until I saw that entry. \$\endgroup\$ – sundar Jul 20 '18 at 18:55
  • \$\begingroup\$ @sundar Weird that it's not documented anymore \$\endgroup\$ – Luis Mendo Jul 20 '18 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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