20
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ May we return a 3-by-3 matrix of neighbours? \$\endgroup\$ – Adám Jul 18 '18 at 13:25
  • \$\begingroup\$ @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? \$\endgroup\$ – Dom Hastings Jul 18 '18 at 15:35
  • \$\begingroup\$ Does order matter? \$\endgroup\$ – Robert Fraser Jul 18 '18 at 15:47
  • \$\begingroup\$ @RobertFraser Order is not important. I'll add that to the rules. \$\endgroup\$ – Dom Hastings Jul 18 '18 at 15:48
  • \$\begingroup\$ @DomHastings I interpret that comment as: it is not allowed to return a 3 by 3 matrix or include the center cell? \$\endgroup\$ – JungHwan Min Jul 18 '18 at 15:55

15 Answers 15

8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Jul 19 '18 at 12:44
  • \$\begingroup\$ @KevinCruijssen Nice catch. Thanks! \$\endgroup\$ – Arnauld Jul 19 '18 at 12:57
6
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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+⍺⊤⍵),⊂⍺⍴⍳×/⍺}

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

\$\endgroup\$
  • \$\begingroup\$ @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⌽...} \$\endgroup\$ – ngn Jul 18 '18 at 15:19
  • \$\begingroup\$ @ngn Uh, that's quite original. You post that! \$\endgroup\$ – Adám Jul 18 '18 at 15:23
  • \$\begingroup\$ @Adám ok­­­­­­­ \$\endgroup\$ – ngn Jul 18 '18 at 15:25
  • \$\begingroup\$ I don't think the output is expected to have the center element in it. \$\endgroup\$ – JungHwan Min Jul 18 '18 at 16:02
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – JungHwan Min Jul 18 '18 at 16:15
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ %h*w saves 3 bytes over *w%(h*w). \$\endgroup\$ – Neil Jul 18 '18 at 23:40
4
\$\begingroup\$

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.

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

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!

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

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

\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, does your variant of K have a "reverse arguments" adverb, like J's ~? \$\endgroup\$ – Conor O'Brien Jul 19 '18 at 15:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – ngn Jul 19 '18 at 16:13
  • \$\begingroup\$ 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. \$\endgroup\$ – ngn Jul 19 '18 at 16:22
  • \$\begingroup\$ 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? \$\endgroup\$ – Conor O'Brien Jul 19 '18 at 17:26
  • \$\begingroup\$ @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. \$\endgroup\$ – ngn Jul 20 '18 at 8:48
2
\$\begingroup\$

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

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!

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

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.

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

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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

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!

\$\endgroup\$

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.