¿De quién son los vecinos hostiles?

10

Introducción

Para los propósitos de este desafío, definiremos los vecinos de un elemento en una matriz cuadrada A (tal que E = A i , j ) como todas las entradas de A que están inmediatamente adyacentes en diagonal, horizontal o vertical a E (es decir ellos "rodean" E , sin envolver).miUNAmi=UNAyo,jUNAmi mi

Para los pedantes, una definición formal de los vecinos de para unn×nmatixAes (0-indexado): N i ,UNAyo,jnorte×norteUNA donde E i ,

norteyo,j={UNAuna,si(una,si)miyo,j([0 0,norte)Z)2}
miyo,j={yo-1,yo,yo+1}×{j-1,j,j+1} \ {yo,j}

Digamos que el elemento en el índice yo,jmcd(UNAyo,j,norte)=1nortenorteyo,j

Tarea

Suficientes historias: dada una matriz cuadrada de enteros positivos, arroje uno de los siguientes:METRO

  • Una lista plana de elementos (deduplicados o no) que indica todas las entradas que ocupan algunos índices en modo que los vecinos sean hostiles.M N i ,yo,jMETROnorteyo,j
  • Una matriz booleana con s en las posiciones donde los vecinos son hostiles y caso contrario (puede elegir cualquier otro valor consistente en lugar de y ).0 0 110 00 01
  • La lista de pares de índices que representan vecindarios hostiles.yo,j

Implementación de referencia en Physica : también admite la sintaxis de Python para E / S. Puede tomar entradas y proporcionar salidas a través de cualquier método estándar y en cualquier formato razonable, mientras toma nota de que estas lagunas están prohibidas de forma predeterminada. Este es el código de golf, por lo que gana el código más corto en bytes (en todos los idiomas).

Además, también puede tomar el tamaño de la matriz como entrada y, además, puede tomar la matriz como una lista plana, ya que siempre será cuadrada.

Ejemplo

Considere la siguiente matriz:

(641014272232535836)

Los vecinos correspondientes de cada elemento son:

i j – E  -> Neighbours                          | All coprime to E?
                                                |
0 0 – 64 -> {10; 27; 22}                        | False
0 1 – 10 -> {64; 14; 27; 22; 32}                | False
0 2 – 14 -> {10; 22; 32}                        | False
1 0 – 27 -> {64; 10; 22; 53; 58}                | True
1 1 – 22 -> {64; 10; 14; 27; 32; 53; 58; 36}    | False
1 2 – 32 -> {10; 14; 22; 58; 36}                | False
2 0 – 53 -> {27; 22; 58}                        | True
2 1 – 58 -> {27; 22; 32; 53; 36}                | False
2 2 – 36 -> {22; 32; 58}                        | False

Y, por lo tanto, el resultado debe ser uno de los siguientes:

  • {27; 53}
  • {{0; 0; 0}; {1; 0; 0}; {1; 0; 0}}
  • {(1; 0); (2; 0)}

Casos de prueba

Input –> Version 1 | Version 2 | Version 3

[[36, 94], [24, 69]] ->
    []
    [[0, 0], [0, 0]]
    []
[[38, 77, 11], [17, 51, 32], [66, 78, 19]] –>
    [38, 19]
    [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
    [(0, 0), (2, 2)]
[[64, 10, 14], [27, 22, 32], [53, 58, 36]] ->
    [27, 53]
    [[0, 0, 0], [1, 0, 0], [1, 0, 0]]
    [(1, 0), (2, 0)]
[[9, 9, 9], [9, 3, 9], [9, 9, 9]] ->
    []
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    []
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] ->
    [1, 1, 1, 1, 1, 1, 1, 1, 1] or [1]
    [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
    [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
[[35, 85, 30, 71], [10, 54, 55, 73], [80, 78, 47, 2], [33, 68, 62, 29]] ->
    [71, 73, 47, 29]
    [[0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1]]
    [(0, 3), (1, 3), (2, 2), (3, 3)]
Sr. Xcoder
fuente
¿Pedir prestado cosas de vecinos hostiles? Por alguna razón, esto me recuerda al juego de Jeff Minter Hover Bovver ...
Arnauld
¿Podemos tomar el tamaño de la matriz como entrada?
Delfad0r
@ Delfad0r Siempre me olvido de mencionar eso. Sí, puede tomar el tamaño de la matriz como entrada.
Sr. Xcoder

Respuestas:

3

APL (Dyalog) , 17 bytes

1=⊢∨(×/∘,↓)⌺3 3÷⊢

Pruébalo en línea! (créditos a ngn por traducir los casos de prueba a APL)

Breve explicacion

(×/∘,↓)⌺3 3 obtiene el producto de cada elemento con sus vecinos.

Luego divido por el argumento ÷⊢, de modo que cada entrada en la matriz ha sido asignada al producto de sus vecinos.

Finalmente, tomo el mcd del argumento con esta matriz ⊢∨y compruebo la igualdad con 1,1=

Tenga en cuenta que, al igual que con la respuesta de ngn , esto falla para algunas entradas debido a un error en el intérprete.

H.PWiz
fuente
2

JavaScript (ES6), 121 bytes

Devuelve una matriz de valores booleanos, donde falso significa hostil.

m=>m.map((r,y)=>r.map((v,x)=>[...'12221000'].some((k,j,a)=>(g=(a,b)=>b?g(b,a%b):a>1)(v,(m[y+~-k]||0)[x+~-a[j+2&7]]||1))))

Pruébalo en línea!

¿Cómo?

El método utilizado para aislar a los 8 vecinos de cada celda es similar al que describí aquí .

Comentado

m =>                            // m[] = input matrix
  m.map((r, y) =>               // for each row r[] at position y in m[]:
    r.map((v, x) =>             //   for each value v at position x in r[]:
      [...'12221000']           //     we consider all 8 neighbors
      .some((k, j, a) =>        //     for each k at position j in this array a[]:
        ( g = (a, b) =>         //       g is a function which takes 2 integers a and b
            b ?                 //       and recursively determines whether they are
              g(b, a % b)       //       coprime to each other
            :                   //       (returns false if they are, true if they're not)
              a > 1             //
        )(                      //       initial call to g() with:
          v,                    //         the value of the current cell
          (m[y + ~-k] || 0)     //         and the value of the current neighbor
          [x + ~-a[j + 2 & 7]]  //
          || 1                  //         or 1 if this neighbor is undefined
  ))))                          //         (to make sure it's coprime with v)
Arnauld
fuente
2

MATL , 22 bytes

tTT1&Ya3thYC5&Y)Zd1=A)

La entrada es una matriz. La salida es todos los números con vecinos hostiles.

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

Explicación con ejemplo trabajado

Considere la entrada [38, 77, 11; 17, 51, 32; 66, 78, 19]como un ejemplo. El contenido de la pila se muestra de abajo hacia arriba.

t         % Implicit input. Duplicate
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
TT1&Ya    % Pad in the two dimensions with value 1 and width 1
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [1,  1,  1,  1,  1;
                    1,  38, 77, 11, 1;
                    1,  17, 51, 32, 1;
                    1,  66, 78, 19, 1
                    1,  1,  1,  1,  1]
3thYC     % Convert each sliding 3×3 block into a column (in column-major order)
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [ 1,  1,  1,  1, 38, 17,  1, 77, 51;
                     1,  1,  1, 38, 17, 66, 77, 51, 78;
                     1,  1,  1, 17, 66,  1, 51, 78,  1;
                     1, 38, 17,  1, 77, 51,  1, 11, 32;
                    38, 17, 66, 77, 51, 78, 11, 32, 19;
                    17, 66,  1, 51, 78,  1, 32, 19,  1;
                     1, 77, 51,  1, 11, 32,  1,  1,  1;
                    77, 51, 78, 11, 32, 19,  1,  1,  1;
                    51, 78,  1, 32, 19,  1,  1,  1,  1]
5&Y)      % Push 5th row (centers of the 3×3 blocks) and then the rest of the matrix
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [38, 17, 66, 77, 51, 78, 11, 32, 19]
                   [ 1,  1,  1,  1, 38, 17,  1, 77, 51;
                     1,  1,  1, 38, 17, 66, 77, 51, 78;
                     1,  1,  1, 17, 66,  1, 51, 78,  1;
                     1, 38, 17,  1, 77, 51,  1, 11, 32;
                    17, 66,  1, 51, 78,  1, 32, 19,  1;
                     1, 77, 51,  1, 11, 32,  1,  1,  1;
                    77, 51, 78, 11, 32, 19,  1,  1,  1;
                    51, 78,  1, 32, 19,  1,  1,  1,  1]
Zd        % Greatest common divisor, element-wise with broadcast
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [1,  1,  1,  1,  1,  1,  1,  1,  1;
                    1,  1,  1,  1, 17,  6, 11,  1,  1;
                    1,  1,  1,  1,  3,  1,  1,  2,  1;
                    1,  1,  1,  1,  1,  3,  1,  1,  1;
                    1,  1,  1,  1,  3,  1,  1,  1,  1;
                    1,  1,  3,  1,  1,  2,  1,  1,  1;
                    1, 17,  6, 11,  1,  1,  1,  1,  1;
                    1,  1,  1,  1,  1,  1,  1,  1,  1]
1=        % Compare with 1, element-wise. Gives true (1) or false (0)
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [1, 1, 1, 1, 1, 1, 1, 1, 1;
                    1, 1, 1, 1, 0, 0, 0, 1, 1;
                    1, 1, 1, 1, 0, 1, 1, 0, 1;
                    1, 1, 1, 1, 1, 0, 1, 1, 1;
                    1, 1, 1, 1, 0, 1, 1, 1, 1;
                    1, 1, 0, 1, 1, 0, 1, 1, 1;
                    1, 0, 0, 0, 1, 1, 1, 1, 1;
                    1, 1, 1, 1, 1, 1, 1, 1, 1]
A         % All: true (1) for columns that do not contain 0
          % STACK: [38, 77, 11;
                    17, 51, 32;
                    66, 78, 19]
                   [1, 0, 0, 0, 0, 0, 0, 0, 1]
)         % Index (the matrix is read in column-major order). Implicit display
          % [38, 19]
Luis Mendo
fuente
¿Funcionará esto si la matriz es mayor que 3x3?
Robert Fraser
@RobertFraser Sí, el procedimiento no depende del tamaño de la matriz. Vea el último caso de prueba, por ejemplo
Luis Mendo
1

APL (Dyalog Classic) , 23 22 bytes

-1 byte gracias a @ H.PWiz

{∧/1=1↓∨∘⊃⍨14⌽,⍵}⌺3 3

Pruébalo en línea!

no admite matrices menores de 3x3 debido a un error en el intérprete

ngn
fuente
@ H.PWiz eso es muy inteligente, ¿quieres publicarlo como tuyo?
ngn
Claro, también puedes usar (⊃∨⊢)-> ∨∘⊂⍨Creo
H.PWiz
1

Jalea , 24 bytes

Hmm, parece largo.

ỊẠ€T
ŒJ_€`Ç€ḟ"J$ịFg"FÇịF

Un enlace monádico que acepta una lista de listas de enteros positivos que devuelve una lista de cada uno de los valores que se encuentran en vecindades hostiles (versión 1 sin deduplicación).

Pruébalo en línea! O ver un conjunto de pruebas .

¿Cómo?

ỊẠ€T - Link 1: indices of items which only contain "insignificant" values: list of lists
Ị    - insignificant (vectorises) -- 1 if (-1<=value<=1) else 0 
  €  - for €ach:
 Ạ   -   all?
   T - truthy indices

ŒJ_€`Ç€ḟ"J$ịFg"FÇịF - Main Link: list of lists of positive integers, M
ŒJ                  - multi-dimensional indices
    `               - use as right argument as well as left...
   €                -   for €ach:
  _                 -     subtract (vectorises)
      €             - for €ach:
     Ç              -   call last Link (1) as a monad
          $         - last two links as a monad:
         J          -   range of length -> [1,2,3,...,n(elements)]
        "           -   zip with:
       ḟ            -     filter discard (remove the index of the item itself)
            F       - flatten M
           ị        - index into (vectorises) -- getting a list of lists of neighbours
               F    - flatten M
              "     - zip with:
             g      -   greatest common divisor
                Ç   - call last Link (1) as a monad
                  F - flatten M
                 ị  - index into
Jonathan Allan
fuente
1

Python 2 , 182 177 166 bytes

lambda a:[[all(gcd(t,a[i+v][j+h])<2for h in[-1,0,1]for v in[-1,0,1]if(h|v)*(i+v>-1<j+h<len(a)>i+v))for j,t in E(s)]for i,s in E(a)]
from fractions import*
E=enumerate

Pruébalo en línea!

Emite una lista de listas con entradas verdaderas / falsas.

Chas Brown
fuente
1

Haskell , 95 bytes

m?n|l<-[0..n-1]=[a|i<-l,j<-l,a<-[m!!i!!j],2>sum[1|u<-l,v<-l,(i-u)^2+(j-v)^2<4,gcd(m!!u!!v)a>1]]

Pruébalo en línea!

La función ?toma la matriz mcomo una lista de listas y el tamaño de la matriz n; devuelve la lista de entradas en hostilidad .

Delfad0r
fuente