# 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? – Adám Jul 18 '18 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? – Dom Hastings Jul 18 '18 at 15:35
• Does order matter? – Robert Fraser Jul 18 '18 at 15:47
• @RobertFraser Order is not important. I'll add that to the rules. – Dom Hastings Jul 18 '18 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? – JungHwan Min Jul 18 '18 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. – Kevin Cruijssen Jul 19 '18 at 12:44
• @KevinCruijssen Nice catch. Thanks! – Arnauld Jul 19 '18 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 '18 at 15:19
• @ngn Uh, that's quite original. You post that! – Adám Jul 18 '18 at 15:23
• @Adám ok­­­­­­­ – ngn Jul 18 '18 at 15:25
• I don't think the output is expected to have the center element in it. – JungHwan Min Jul 18 '18 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] – JungHwan Min Jul 18 '18 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 '18 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[1]+0:2,p[2]+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 ! – JayCe Jul 19 '18 at 0:35
• You can save 8 bytes by replacing seq() with 1: – Mark Jul 19 '18 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 ~? – Conor O'Brien Jul 19 '18 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 '18 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 '18 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? – Conor O'Brien Jul 19 '18 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 '18 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!