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

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

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

Answer 4

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.

Answer 5

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.

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

Answer 8

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 9

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

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!