Find the Cell's Neighbours

Question

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

• Your answer may be 0 or 1-indexed, your choice, please specify.
• 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 code-golf 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!}

• Adám: May we return a 3-by-3 matrix of neighbours?
• Dom Hastings: @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?
• Robert Fraser: Does order matter?
• Dom Hastings: @RobertFraser Order is not important. I'll add that to the rules.
• JungHwan Min: @DomHastings I interpret that comment as: it is not allowed to return a 3 by 3 matrix or include the center cell?

Answer 1

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]$$

• Kevin Cruijssen: 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.
• Arnauld: @KevinCruijssen Nice catch. Thanks!

Answer 2

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 ⍺

Answer 3

APL (Dyalog Unicode), 40 bytes ^SBCS

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

{1↓4⌽,3 3↑,⍨⍣2⍪⍨⍣2⊃⊖∘⍉/( ̄1+⍺⊤⍵)×ばつ/⍺}

Try it online!

{...} "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

• ngn: @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⌽...}
• Adám: @ngn Uh, that's quite original. You post that!
• ngn: @Adám ok­­­­­­­
• JungHwan Min: I don't think the output is expected to have the center element in it.
• JungHwan Min: 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]

Answer 4

Python 2, (削除) 79 (削除ここまで) (削除) 69 (削除ここまで) 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.

• Neil: %h*w saves 3 bytes over *w%(h*w).

Answer 5

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.

• JayCe: You can save 14 bytes. I did not know that which had an arr.ind argument, learned something today !
• Mark: You can save 8 bytes by replacing seq() with 1:

Answer 6

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

Or Try it online!

Answer 7

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

• Conor O'Brien: Out of curiosity, does your variant of K have a "reverse arguments" adverb, like J's ~?
• ngn: @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: 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.
• Conor O'Brien: 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?
• ngn: @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.

Answer 8

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.

Try it online! Or verify all test cases.

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]
3Y6 % Push Moore mask
 % 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] 
+ % Add, element-wise with broadcast
 % 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]

Answer 9

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!

Answer 10

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.

Answer 11

MATL, 24 bytes

X[h3Y6&fh2-+1GX1円Gw!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.

Answer 12

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'.

Answer 13

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]
 ¤ - nilad followed by link(s) as a nilad:
 Ø- - 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)

Answer 14

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]}

Answer 15

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!

Answer 16

Vyxal 3, 11 bytes

Πʀ0hẆÞȮ1)1i

Try it Online!

Output is sorted in footer but is not necessary to the program bytecount

input is of the form [w,h], n

Πʀ0hẆÞȮ1)1i­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌­
Πʀ # ‎⁡range [0, w*h)
 0hẆ # ‎⁢split into chunks of given width
 ÞȮ1) # ‎⁣grid neighbors with wraparound flattened by one
 1i # ‎⁤at given index
💎

Created with the help of Luminespire.