Encuentra los vecinos de la celda

20

... o vecindarios de Toroidal Moore

Enteros positivos Dadas h, wy un número entero no negativo i, devolver todos los índices de los alrededores i.

Debe asumir una matriz que consiste en hfilas de welementos, numerados desde el más bajo, en la esquina superior izquierda, hasta el más alto, en la esquina inferior derecha, y devolver, en cualquier formato razonable, una lista de los índices que rodear el índice, i. Esta matriz es un toro (un mapa infinito que se envuelve alrededor de cada borde).

Por ejemplo, las entradas h=4y w=4, darían como resultado la matriz:

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

pero más específicamente:

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

así que si ifuera así 0, necesitaría regresar 15, 12, 13, 3, 1, 7, 4, 5(basado en 0).

Ejemplos

Basado en 0:

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

Basado en 1:

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

Reglas

  • Su respuesta puede ser 0 o 1 indexada, su elección, por favor especifique.
  • Puede suponer eso i < h * w(o i <= h * wpara respuestas indexadas 1).
  • Puede suponer eso i >= 0(o i > 0para respuestas indexadas 1).
  • El orden de los valores devueltos no es importante siempre que se incluyan solo los ocho valores deseados.
  • Las lagunas estándar están prohibidas .
  • Este es el por lo que la respuesta más corta, en cada idioma, ¡gana!

¡Gracias a @Conor O'Brien por el título más técnico y a @ngm por más casos de prueba!

Dom Hastings
fuente
3
¿Podemos devolver una matriz de vecinos de 3 por 3?
Adám
@ Adám Preferiría que la lista no incluyera la celda central si es posible. Pero apreciamos que ya hay respuestas. ¿Es bastante fácil filtrar esto?
Dom Hastings
¿Importa el orden?
Robert Fraser
El pedido de @RobertFraser no es importante. Agregaré eso a las reglas.
Dom Hastings
@DomHastings Interpreto ese comentario como: ¿no está permitido devolver una matriz de 3 por 3 o incluir la celda central?
JungHwan Min

Respuestas:

8

JavaScript (ES6), 75 bytes

Guardado 2 bytes gracias a @KevinCruijssen

Espera un índice basado en 0.

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

Pruébalo en línea!

Los índices circundantes se devuelven en el siguiente orden:

54362701

¿Cómo?

Los índices de cada celda circundante en ( x + d x , y + d y ) están dados por:Idx,dy(X+reX,y+rey)

yoreX,rey=((X+reX)modificaciónw)+w((y+rey)modificaciónh)=((norte+reX)modificaciónw)+w((nortew+rey)modificaciónh)

donde es el índice de la celda objetivo.norte=wy+X

Recorremos la lista y restamos 1 para obtener el valor de d x , que da:[1,2,2,2,1,0 0,0 0,0 0]1reX

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

Para los valores correspondientes de , usamos la misma lista desplazada por 2 posiciones, que da:rey

[1,1,0 0,-1,-1,-1,0 0,1]
Arnauld
fuente
w*(~~(i/w+h+~-a[j+2&7])%h)que ~~(a[j+2&7]-1+i/w+h)%h*wahorra 2 bytes por deshacerse de un par de paréntesis.
Kevin Cruijssen
@KevinCruijssen Buena captura. ¡Gracias!
Arnauld
6

APL (Dyalog Classic) , 27 bytes

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

Pruébalo en línea!

{ }es una función con argumentos (las dimensiones h w) y (el índice i)

⍳3 3es una matriz de todos los números ternarios de 2 dígitos: 0 0, 0 1, ...,2 2

, alista la matriz como un vector

1↓4⌽elimina el elemento central 1 1girando 4 hacia la izquierda ( 4⌽) y soltando uno ( 1↓)

1- resta de 1, dando las 8 compensaciones vecinas

( aplica el tren de funciones entre paréntesis a cada desplazamiento

⍺⊤⍵es la codificación base de - las coordenadas de en la matriz

(⍺⊤⍵)-⊢ resta el desplazamiento actual, dando las coordenadas de un vecino

⍺|es mod apara envolver coordenadas y permanecer dentro de la matriz

⍺⊥ decodifica desde la base

ngn
fuente
5

APL (Dyalog Unicode) , SBCS de 40 bytes

Función de infijo anónimo. Toma h wcomo argumento izquierdo y icomo argumento derecho.

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

Pruébalo en línea!

{... } "dfn"; es argumento izquierdo (dimensiones) y argumento derecho (índice).

×/⍺ producto (multiplicación-reducción) de las dimensiones

 el primero que muchos índices

⍺⍴ utilizar las dimensiones a r eshape que

 encerrarlo (para tratarlo como un elemento único)

(... ), anteponer lo siguiente:

  ⍺⊤⍵ codificar el índice en mezcla mixta h w(esto nos da las coordenadas del índice)

  ¯1+ agregue uno negativo a esas coordenadas

⊖∘⍉/ reduzca rotando-la-transposición
  esto es equivalente a y⊖⍉x⊖⍉... que es equivalente a y⊖x⌽... que gira a la izquierda tantos pasos como ise desplaza a la derecha (menos uno), y gira hacia arriba tantos pasos como ise compensa hacia abajo (menos uno), causando la matriz de 3 por 3 buscamos estar en la esquina superior izquierda

 revelar (porque la reducción redujo el vector a escalar al encerrar)

⍪⍨⍣2 apilar dos veces sobre sí mismo (solo necesitamos tres veces para matrices de una sola fila)

,⍨⍣2 agregarse a sí mismo dos veces (solo necesitamos tres veces para matrices de una sola columna)

3 3↑ tomar las primeras tres filas de las primeras tres columnas

Los siguientes dos pasos se pueden omitir si es aceptable devolver una matriz de 3 por 3:

, ravel (aplanar)

4⌽ gire cuatro pasos hacia la izquierda (lleva el elemento central al frente)

1↓ soltar el primer elemento

Adán
fuente
@ Adám arregla lo anterior y lo acorta: {,(⍺⊥⍺|(⍺⊤⍵)-⊢)¨1-⍳3 3}no estoy seguro de si también debes eliminar el elemento del medio: {4⌽1↓4⌽...}
ngn
@ngn Uh, eso es bastante original. ¡Publicas eso!
Adám
@ Adám ok
ngn
No creo que se espere que la salida tenga el elemento central.
JungHwan Min
1
El último caso de prueba todavía tiene 8 elementos. Creo que el resultado previsto es imprimir a los vecinos en posiciones relativas[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]
JungHwan Min
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]

Pruébalo en línea!

3 bytes dotados por Neil señalando eso (x*w)%(h*w)==((x)%h)*w==(x)%h*w.

Solución indexada 0.

Chas Brown
fuente
%h*w ahorra 3 bytes más *w%(h*w).
Neil
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]

Pruébalo en línea!

14 y 8 bytes jugados por @JayCe y @Mark.

La entrada se [w, h], idebe a que R llena primero la columna de matrices.

Hace la matriz y luego la "triplica" en forma de fila y columna. Luego, ubíquese ien la matriz original y encuentre su vecindario. Salida sin i.

ngm
fuente
1
Puede guardar 14 bytes . No sabía lo que tenía un argumento arr.ind, ¡aprendí algo hoy!
JayCe
Puede guardar 8 bytes reemplazando seq()con1:
Mark
3

PHP , 165 bytes

Esto es "basado en 0". Debe haber una mejor solución en PHP, ¡pero este es un punto de partida!

<?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;

Para ejecutarlo:

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

Ejemplo:

php -n cell_neighbours.php 4 5 1

O Pruébelo en línea!

Noche2
fuente
3

K (ngn / k) , 27 24 bytes

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

Pruébalo en línea!

{ }es una función con argumentos x(las dimensiones h w) y y(el índice i)

(!9)^4es 0 1 2 3 4 5 6 7 8sin el4

3\ codifica en ternario: (0 0;0 1;0 2;1 0;1 2;2 0;2 1;2 2)

1-resta de 1, dando compensaciones vecinas:(1 1;1 0;1 -1;0 1;0 -1;-1 1;-1 0;-1 -1)

x\yes la xcodificación base de y- las coordenadas de yen la matriz

- resta cada desplazamiento, dándonos 8 pares de coordenadas vecinas

x!''es mod xpara cada uno: ajusta las coordenadas para permanecer dentro de la matriz

x/decodifica desde la base x: convierte pares de coordenadas en enteros únicos

ngn
fuente
Por curiosidad, ¿su variante de K tiene un adverbio de "argumentos inversos", como el de J ~?
Conor O'Brien
1
@ ConorO'Brien Ninguna de las k que conozco (Kx's K, Kona, oK y la mía) la tiene, lo cual es lamentable para el golf. Solo hay 6 adverbios integrados: / \ '/: \:': y ningún mecanismo para los definidos por el usuario.
ngn
Por supuesto, podría agregar un adverbio selfie, pero el golf no es un fin en sí mismo para ngn / k, solo un medio para acumular casos de prueba y experiencia.
ngn
Eso es justo. Por supuesto, podría verlo como una posible deficiencia del idioma. Utilicé PPCG para ayudar a desarrollar Attache, y me di cuenta de que Attache carecía de algunas funciones muy útiles que de otro modo no habría incluido. No uso K, pero ¿quizás hay otros casos de uso que pueden justificar ese tipo de adverbio?
Conor O'Brien
@ ConorO'Brien con el que estoy familiarizado en APL, que es como ~en J, y estoy convencido de su utilidad, pero, como puede ver, k está limitado a ASCII imprimible y (casi) sin dígrafos, por lo que un nuevo adverbio significaría el sacrificio de alguna otra primitiva útil, así como más incompatibilidad entre implementaciones. No veo todo lo que pueda para poner esto.
ngn
2

MATL , 24 bytes

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

Las entradas son h, w, i. La salida es un vector de fila o de columna con los números.

La entrada iy la salida están basadas en 1.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

*     % 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]
Luis Mendo
fuente
2

Lote, 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 indexado. Ahorró 23 bytes al robar el truco del módulo 3 de @ ChasBrown.

Neil
fuente
2

MATL, 24 bytes

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

Pruébalo en MATL Online

Toma entradas [w h]y i. 8 bytes de esto fueron robados descaradamente de la inspiración de la respuesta de Luis Mendos, aunque el enfoque general es diferente.

sundar - Restablecer a Monica
fuente
1

Limpio , 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]]

Pruébalo en línea!

Se trata icomo una coordenada (0 <= p < h, 0 <= q < w)y genera los valores de los elementos adyacentes donde está el valor p'w + q'.

Οurous
fuente
1

Jalea , 20 bytes

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

Un enlace diádico que acepta una lista de las dimensiones a la izquierda [h,w], y la celda como un entero a la derecha,i , que produce una lista del vecindario.

Nota: el orden es diferente al de los ejemplos que está permitido en el OP

Pruébalo en línea!

¿Cómo?

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)
Jonathan Allan
fuente
1

Adjunto , 66 bytes

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

Pruébalo en línea!

Todavía necesito implementar Mooresy NMoore, pero todavía tengo el Mooreque sirve como una función de iteración. Esencialmente, Integers@@__2crea una matriz de forma entera __2(los dos últimos argumentos) de los primeros Prod[__2]enteros. Esto nos da la matriz de destino. Luego, Mooreitera la función {Push[a,_]}sobre cada vecindario de tamaño de Moore 1(argumento implícito), con la opción de alternar cada elemento ( cycle->1). Esto agrega cada vecindario a la matriz a. Luego, Flat[a@_]aplana el _miembro th dea , es decir, el vecindario de Moore centrado alrededor _(el primer argumento).[0:3'5:8]obtiene todos los miembros excepto el centro de esta matriz aplanada.

Esta solución, con una actualización del idioma, se vería así (49 bytes):

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

Kotlin , 88 bytes

Utiliza índices basados ​​en cero y genera una lista de 8 elementos.

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

Pruébalo en línea!

JohnWells
fuente