# Find the Cell's Neighbours

## ...or Toroidal Moore Neighbourhoods

Given positive integers h, w and a non-negative integer i, return all of the indices surrounding i.

You are to assume a matrix consisting of h rows of w elements, numbered from lowest, in the top left-hand corner, to highest, in the bottom right-hand corner, and return, in any reasonable format, a list of the indices that would surround the index, i. This matrix is a torus (an infinite map that wraps around each edge).

For example, inputs h=4 and w=4, would result in the matrix:

 0  1  2  3
4  5  6  7
8  9 10 11
12 13 14 15


but more specifically:

15 12 13 14 15 12
3  0  1  2  3  0
7  4  5  6  7  4
11  8  9 10 11  8
15 12 13 14 15 12
3  0  1  2  3  0

so that if i was 0, you'd need to return 15, 12, 13, 3, 1, 7, 4, 5 (0-based).

## Examples

0-based:

h   w   i       Expected result

4   4   5       0, 1, 2, 4, 6, 8, 9, 10
4   4   0       15, 12, 13, 3, 1, 7, 4, 5
4   5   1       15, 16, 17, 0, 2, 5, 6, 7
1   3   2       1, 2, 0, 1, 0, 1, 2, 0
1   1   0       0, 0, 0, 0, 0, 0, 0, 0


1-based:

h   w   i       Expected result

4   4   6       1, 2, 3, 5, 7, 9, 10, 11
4   4   1       16, 13, 14, 4, 2, 8, 5, 6
4   5   2       16, 17, 18, 1, 3, 6, 7, 8
1   3   3       2, 3, 1, 2, 1, 2, 3, 1
1   1   1       1, 1, 1, 1, 1, 1, 1, 1


## Rules

• You can assume that i < h * w (or i <= h * w for 1-indexed answers).
• You can assume that i >= 0 (or i > 0 for 1-indexed answers).
• The order of the returned values is not important as long as just the eight desired values are included.
• Standard loopholes are forbidden.
• This is so the shortest answer, in each language, wins!

Thanks to @Conor O'Brien for the more technical sounding title and @ngm for more test cases!

• May we return a 3-by-3 matrix of neighbours?
Jul 18, 2018 at 13:25
• @Adám I would prefer the list to not include the center cell if possible. But appreciate there are already answers. Is it easy enough to filter this out? Jul 18, 2018 at 15:35
• Does order matter? Jul 18, 2018 at 15:47
• @RobertFraser Order is not important. I'll add that to the rules. Jul 18, 2018 at 15:48
• @DomHastings I interpret that comment as: it is not allowed to return a 3 by 3 matrix or include the center cell? Jul 18, 2018 at 15:55

# JavaScript (ES6), 75 bytes

Saved 2 bytes thanks to @KevinCruijssen

Expects a 0-based index.

(h,w,i)=>[...'12221000'].map((k,j,a)=>(i+w+~-k)%w+~~(i/w+h+~-a[j+2&7])%h*w)


Try it online!

The surrounding indices are returned in the following order:

$$\begin{matrix}5&4&3\\6&\cdot&2\\7&0&1\end{matrix}$$

### How?

The indices $$\I_{dx,dy}\$$ of each surrounding cell at $$\(x+dx,y+dy)\$$ are given by:

\begin{align}I_{dx,dy}&=((x+dx) \bmod w)+w((y+dy) \bmod h)\\&=((N+dx) \bmod w)+w((\left\lfloor\frac{N}{w}\right\rfloor+dy) \bmod h)\end{align}

where $$\N=wy+x\$$ is the index of the target cell.

We walk through the list $$\[1,2,2,2,1,0,0,0]\$$ and subtract $$\1\$$ to get the value of $$\dx\$$, which gives:

$$[0,1,1,1,0,-1,-1,-1]$$

For the corresponding values of $$\dy\$$, we use the same list shifted by 2 positions, which gives:

$$[1,1,0,-1,-1,-1,0,1]$$

• w*(~~(i/w+h+~-a[j+2&7])%h) to ~~(a[j+2&7]-1+i/w+h)%h*w saves 2 bytes by getting rid of a pair of parenthesis. Jul 19, 2018 at 12:44
• @KevinCruijssen Nice catch. Thanks! Jul 19, 2018 at 12:57

# APL (Dyalog Classic), 27 bytes

{(⍺⊥⍺|(⍺⊤⍵)-⊢)¨1-1↓4⌽,⍳3 3}


Try it online!

{ } is a function with arguments ⍺ (the dimensions h w) and ⍵ (the index i)

⍳3 3 is a matrix of all 2-digit ternary numbers: 0 0, 0 1, ..., 2 2

, enlists the matrix as a vector

1↓4⌽ removes the centre element 1 1 by rotating 4 to the left (4⌽) and dropping one (1↓)

1- subtracts from 1, giving all 8 neighbour offsets

( )¨ applies the function train in parentheses to each offset

⍺⊤⍵ is the base-⍺ encoding of ⍵ - the coordinates of ⍵ in the matrix

(⍺⊤⍵)-⊢ subtracts the current offset, giving the coordinates of a neighbour

⍺| is mod a to wrap around coordinates and stay within the matrix

⍺⊥ decodes from base ⍺

# APL (Dyalog Unicode), 40 bytesSBCS

Anonymous infix function. Takes h w as left argument and i as right argument.

{1↓4⌽,3 3↑,⍨⍣2⍪⍨⍣2⊃⊖∘⍉/(¯1+⍺⊤⍵),⊂⍺⍴⍳×/⍺}


{} "dfn"; ⍺ is left argument (dimensions) and ⍵ is right argument (index).

×/⍺ product (multiplication-reduction) of the dimensions

⍳ the first that many indices

⍺⍴ use the dimensions to reshape that

⊂ enclose it (to treat it as a single element)

(), prepend the following:

⍺⊤⍵ encode the index in mixed-radix h w (this gives us the coordinates of the index)

¯1+ add negative one to those coordinates

⊖∘⍉/ reduce by rotate-the-transpose
this is equivalent to y⊖⍉x⊖⍉… which is equivalent to y⊖x⌽… which rotates left as many steps as i is offset to the right (less one), and rotates up as many steps as i is offset down (less one), causing the the 3-by-3 matrix we seek to be in the top left corner

⊃ disclose (because the reduction reduced the vector to scalar by enclosing)

⍪⍨⍣2 stack on top of itself twice (we only really need thrice for single-row matrices)

,⍨⍣2 append to itself twice (we only really need thrice for single-column matrices)

3 3↑ take the first three rows of the first three columns

The next two steps can be omitted if returning a 3-by-3 matrix is acceptable:

, ravel (flatten)

4⌽ rotate four steps left (brings the centre element to the front)

1↓ drop the first element

• @Adám fix the above and shorten it: {,(⍺⊥⍺|(⍺⊤⍵)-⊢)¨1-⍳3 3}, I'm not sure if you should also remove the middle element: {4⌽1↓4⌽...}
– ngn
Jul 18, 2018 at 15:19
• @ngn Uh, that's quite original. You post that!
Jul 18, 2018 at 15:23
– ngn
Jul 18, 2018 at 15:25
• I don't think the output is expected to have the center element in it. Jul 18, 2018 at 16:02
• The last test case still has 8 elements. I think the intended output is to print the neighbors at relative positions [-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1] Jul 18, 2018 at 16:15

# Python 2, 7969 66 bytes

lambda h,w,i:[(i+q%3-1)%w+(i/w+q/3-1)%h*w for q in range(9)if q-4]


Try it online!

3 bytes gifted by Neil noting that (x*w)%(h*w)==((x)%h)*w==(x)%h*w.

0-indexed solution.

• %h*w  saves 3 bytes over *w%(h*w).
– Neil
Jul 18, 2018 at 23:40

# R, 125 111 108 bytes

function(x,i,m=array(1:prod(x),x),n=rbind(m,m,m),o=cbind(n,n,n),p=which(m==i,T)+x-1)o[p+0:2,p+0:2][-5]


Try it online!

14 and 8 bytes golfed by @JayCe and @Mark.

Input is [w, h], i because R populates arrays column first.

Makes the array and then "triples" it row- and column-wise. Then locate i in the original array and find it's neighborhood. Output without i.

• You can save 14 bytes. I did not know that which had an arr.ind argument, learned something today ! Jul 19, 2018 at 0:35
• You can save 8 bytes by replacing seq() with 1:
– Mark
Jul 19, 2018 at 12:01

# PHP, 165 bytes

This is "0-based". There must be a better solution in PHP, but this is a starting point!

<?list(,$h,$w,$i)=$argv;for($r=-2;$r++<1;)for($c=-2;$c++<1;)$r||$c?print(($k=(int)($i/$w)+$r)<0?$h-1:($k>=$h?0:$k))*$w+(($l=$i%$w+$c)<0?$w-1:($l>=$w?0:$l))%$w.' ':0;


To run it:

php -n <filename> <h> <w> <i>


Example:

php -n cell_neighbours.php 4 5 1


# K (ngn/k), 27 24 bytes

{x/x!''(x\y)-1-3\(!9)^4}


Try it online!

{ } is a function with arguments x (the dimensions h w) and y (the index i)

(!9)^4 is 0 1 2 3 4 5 6 7 8 without the 4

3\ encodes in ternary: (0 0;0 1;0 2;1 0;1 2;2 0;2 1;2 2)

1- subtracts from 1, giving neighbour offsets: (1 1;1 0;1 -1;0 1;0 -1;-1 1;-1 0;-1 -1)

x\y is the base-x encoding of y - the coordinates of y in the matrix

- subtracts each offset, giving us 8 pairs of neighbour coordinates

x!'' is mod x for each - wrap coordinates around to stay within the matrix

x/ decodes from base x - turns pairs of coordinates into single integers

• Out of curiosity, does your variant of K have a "reverse arguments" adverb, like J's ~? Jul 19, 2018 at 15:31
• @ConorO'Brien None of the ks I know of (Kx's K, Kona, oK, and mine) has it, which is unfortunate for golfing. There are only 6 built-in adverbs: / \ ' /: \: ': and no mechanism for user-defined such.
– ngn
Jul 19, 2018 at 16:13
• Of course I could add a selfie adverb, but golfing is not an end in itself for ngn/k, only a means to accumulate test cases and experience.
– ngn
Jul 19, 2018 at 16:22
• That's fair. Of course, you could view it as a potential shortcoming of the language. I've used PPCG to help develop Attache, and have realized Attache lacked some very useful functions that I would have otherwise not included. I don't use K, but perhaps there are other usecases which may warrant that type of adverb? Jul 19, 2018 at 17:26
• @ConorO'Brien I'm familiar with ⍨ in APL which is like ~ in J and I'm convinced of its utility, but, you see, k is limited to printable ASCII and (almost) no digraphs, so, a new adverb would mean the sacrifice of some other useful primitive as well as more incompatibility among implementations. I don't see what I can through out to put this in.
– ngn
Jul 20, 2018 at 8:48

# MATL, 24 bytes

*:2Geti=&fh3Y6&fh2-+!Z{)


Inputs are h, w, i. The output is a row vector or column vector with the numbers.

Input i and output are 1-based.

### Explanation

*     % Take two inputs implicitly. Multiply
% STACK: 16
:     % Range
% STACK: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
2G    % Push second input again
% STACK: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16], 4
e     % Reshape with that number of rows, in column-major order
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16]
t     % Duplicate
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16],
%        [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16]
i=    % Take third input and compare, element-wise
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16],
%        [0 0 0 0; 0 1 0 0; 0 0 0 0; 0 0 0 0]
&f    % Row and column indices of nonzeros (1-based)
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], 2, 2,
h     % Concatenate horizontally
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], [2 2]
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], [2 2],
%        [1 1 1; 1 0 1; 1 1 1]
&f    % Row and column indices of nonzeros (1-based)
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], [2 2],
%        [1; 2; 3; 1; 3; 1; 2; 3], [1; 1; 1; 2; 2; 3; 3; 3]
h     % Concatenate horizontally
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], [2 2],
%        [1 1; 2 1; 3 1; 1 2; 3 2; 1 3; 2 3; 3 3]
2-    % Subtract 2, element-wise
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16], [2 2],
%        [-1 -1; 0 -1; 1 -1; -1 0; -1 0; -1 1; 0 1; 1 1]
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16],
%        [1 1; 2 1; 3 1; 1 2; 3 2; 1 3; 2 3; 3 3]
!     % Transpose
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16],
%        [1 2 3 1 3 1 2 3; 1 1 1 2 2 3 3 3]
Z{    % Convert into a cell array of rows
% STACK: [1 5 9 13; 2 6 10 14; 3 7 11 15; 4 8 12 16],
%        {[1 2 3 1 3 1 2 3], [1 1 1 2 2 3 3 3]}
)     % Index. A cell array acts as an element-wise (linear-like) index
% STACK: [1 2 3 5 7 9 10 11]


# Wolfram Language (Mathematica), 74 bytes

Mod[i=#;w=#2;Mod[i+#2,w]+i~Floor~w+w#&@@@{-1,0,1}~Tuples~2~Delete~5,1##2]&


Try it online!

Takes input in reverse (i, w, h), 0-based.

### 3x3 matrix with the center cell in it, (60 bytes)

(Join@@(p=Partition)[Range[#2#]~p~#,a={1,1};3a,a,2a])[[#3]]&


Takes (w, h, i), 1-based.

Try it online!

## Batch, 105 bytes

@for /l %%c in (0,1,8)do @if %%c neq 4 cmd/cset/a(%3/%2+%1+%%c/3-1)%%%1*%2+(%3%%%2+%2+%%c%%3-1)%%%2&echo.


0-indexed. Saved 23 bytes by stealing @ChasBrown's modulo 3 trick.

# MATL, 24 bytes

X[h3Y6&fh2-+1GX\1Gw!Z}X]


Try it on MATL Online

Takes inputs [w h] and i. 8 bytes of this was shamelessly stolen from inspired by Luis Mendos' answer, though the overall approach is different.

# Clean, 85 83 bytes

import StdEnv
r=(rem)
\$h w i=tl[r(n+i/w)h*w+r(r(m+i)w)w\\n<-[0,1,h-1],m<-[0,1,w-1]]


Try it online!

Treats i as a coordinate (0 <= p < h, 0 <= q < w), and generates the values of the adjacent elements where the value is p'w + q'.

# Jelly, 20 bytes

PRs©Ṫ{œi+€Ø-Ż¤ŒpḊœị®


A dyadic link accepting a list of the dimensions on the left, [h,w], and the cell as an integer on the right, i, which yields a list of the neighbourhood.

Note: the order is different to that in the examples which is allowed in the OP

Try it online!

### How?

PRs©Ṫ{œi+€Ø-Ż¤ŒpḊœị® - Link: [h,w], i
P                    - product -> h*w
R                   - range -> [1,2,3,...,h*w]
Ṫ{               - tail of left -> w
s                  - split into chunks -> [[1,2,3,...w],[w+1,...,2*w],[(h-1)*w+1,...,h*w]]
©                 - ...and copy that result to the register
œi             - multi-dimensional index of (i) in that list of lists, say [r,c]
Ø-         -   literal list -> [-1,1]
Ż        -   prepend a zero -> [0,-1,1]
+€           - addition (vectorises) for €ach -> [[r,r-1,r+1],[c,c-1,c+1]]
Œp     - Cartesian product -> [[r,c],[r,c-1],[r,c+1],[r-1,c],[r-1,c-1],[r-1,c+1],[r+1,c],[r+1,c-1],[r+1,c+1]]
Ḋ    - dequeue -> [[r,c-1],[r,c+1],[r-1,c],[r-1,c-1],[r-1,c+1],[r+1,c],[r+1,c-1],[r+1,c+1]]
® - recall (the table) from the register
œị  - multi-dimensional index into (1-indexed & modular)


# Attache, 66 bytes

{a.=[]Moore[Integers@@__2,{Push[a,_]},cycle->1]Flat[a@_][0:3'5:8]}


Try it online!

I still need to implement Moores and NMoore, but I still have Moore which serves as an iteration function. Essentially, Integers@@__2 creates an integer array of shape __2 (the last two arguments) of the first Prod[__2] integers. This gives us the target array. Then, Moore iterates the function {Push[a,_]} over each Moore neighborhood of size 1 (implied argument), with the option to cycle each element (cycle->1). This adds each neighborhood to the array a. Then, Flat[a@_] flattens the _th member of a, that is, the Moore neighborhood centered around _ (the first argument). [0:3'5:8] obtains all members except the center from this flattened array.

This solution, with an update to the language, would look something like this (49 bytes):

{Flat[NMoore[Integers@@__2,_,cycle->1]][0:3'5:8]}


# Kotlin, 88 bytes

Uses zero based indexes and outputs an 8 element list.

{h:Int,w:Int,i:Int->List(9){(w+i+it%3-1)%w+(h+i/w+it/3-1)%h*w}.filterIndexed{i,v->i!=4}}


Try it online!