Einführung

Für die Zwecke dieser Herausforderung definieren wir die Nachbarn eines Elements $E$ in einer quadratischen Matrix $A$ (so dass $E=A_{i,j}$ ) als alle Einträge von $A$ , die unmittelbar diagonal, horizontal oder vertikal an angrenzen $E$(dh sie "umgeben" $E$ , ohne sich zu wickeln).

Für Pedanten eine formale Definition der Nachbarn von $A_{i,\:j}$ für eine$n\times n$Matix$A$ist (0-indiziert):

$$N_{i,\:j}=\{A_{a,\:b}\mid(a,b)\in E_{i,\:j}\:\cap\:([0,\:n)\:\cap\:\Bbb{Z})^2\}$$ wobei $$E_{i,\:j}=\{i-1,\:i,\:i+1\}\times \{j-1,\:j,\:j+1\} \text{ \\ } \{i,\:j\}$$

Nehmen wir an, das Element am Index lebt in Feindseligkeit, wenn es allen seinen Nachbarn gemeinsam ist ). Leider kann dieser arme Eingang nicht einmal eine Tasse Zucker von seinen unhöflichen Anwohnern in der Nähe ausleihen ...$i,\:j$$\gcd(A_{i,\:j},\:n)=1\:\forall\:n\in N_{i,\:j}$

Aufgabe

Genug Geschichten: Geben Sie bei einer quadratischen Matrix positiver Ganzzahlen eine der folgenden Optionen aus:$M$

• Eine flache Liste von Elementen (dedupliziert oder nicht), die alle Einträge angeben, die einige Indizes in belegen so dass die Nachbarn feindlich sind.M N i $i,j$$M$$N_{i,\:j}$
• Eine boolesche Matrix mit s an Positionen, an denen die Nachbarn feindlich eingestellt sind, und ansonsten (Sie können anstelle von und andere konsistente Werte wählen ).0 0 $1$$0$$0$$1$
• Die Liste der Indexpaare , die feindliche Nachbarschaften darstellen.$i,\:j$

Referenzimplementierung in Physica - unterstützt die Python- Syntax auch für E / A. Sie können Eingaben und Ausgaben über jede Standardmethode und in jedem vernünftigen Format vornehmen, wobei zu beachten ist, dass diese Lücken standardmäßig verboten sind. Dies ist Code-Golf, also gewinnt der kürzeste Code in Bytes (in jeder Sprache)!

Darüber hinaus können Sie auch die Matrixgröße als Eingabe und zusätzlich die Matrix als flache Liste verwenden, da sie immer quadratisch ist.

Beispiel

Betrachten Sie die folgende Matrix:

$$\left(\begin{matrix} 64 & 10 & 14 \\ 27 & 22 & 32 \\ 53 & 58 & 36 \\ \end{matrix}\right)$$

Die entsprechenden Nachbarn jedes Elements sind:

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

Und daher muss die Ausgabe eine der folgenden sein:

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

Testfälle

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

APL (Dyalog) , 17 Bytes

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

Probieren Sie es online aus! (Dank an ngn für die Übersetzung der Testfälle in APL)

Kurze Erklärung

(×/∘,↓)⌺3 3 erhält das Produkt jedes Elements mit seinen Nachbarn.

Dann dividiere ich durch das Argument ÷⊢, so dass jeder Eintrag in der Matrix dem Produkt seiner Nachbarn zugeordnet wurde.

Schließlich nehme ich die gcd des Arguments mit dieser Matrix ⊢∨und überprüfe die Gleichheit mit 1,1=

Beachten Sie, dass dies wie bei der Antwort von ngn bei einigen Eingaben aufgrund eines Fehlers im Interpreter fehlschlägt.

JavaScript (ES6), 121 Byte

Gibt eine Matrix von Booleschen Werten zurück, wobei false feindlich bedeutet.

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

Probieren Sie es online aus!

Wie?

Die Methode zur Isolierung der 8 Nachbarn jeder Zelle ähnelt der hier beschriebenen .

Kommentiert

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)

MATL , 22 Bytes

tTT1&Ya3thYC5&Y)Zd1=A)

Eingabe ist eine Matrix. Ausgabe sind alle Zahlen mit feindlichen Nachbarn.

Probieren Sie es online aus! Oder überprüfen Sie alle Testfälle .

Erklärung mit Beispiel

Betrachten Sie die Eingabe [38, 77, 11; 17, 51, 32; 66, 78, 19]als Beispiel. Der Stapelinhalt wird von unten nach oben angezeigt.

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]

APL (Dyalog Classic) , 23 22 Bytes

-1 Byte dank @ H.PWiz

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

Probieren Sie es online aus!

unterstützt keine Matrizen kleiner als 3x3 aufgrund eines Fehlers im Interpreter

Gelee , 24 Bytes

^{Hmm, scheint lang.}

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

Ein monadischer Link, der eine Liste von Listen positiver Ganzzahlen akzeptiert, die eine Liste aller Werte zurückgibt, die sich in feindlichen Nachbarschaften befinden (Version 1 ohne Deduplizierung).

Probieren Sie es online aus! Oder sehen Sie sich eine Testsuite an .

Wie?

ỊẠ€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

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

Probieren Sie es online aus!

Gibt eine Liste von Listen mit True / False-Einträgen aus.

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

Probieren Sie es online aus!

Die Funktion verwendet ?die Matrix mals Liste von Listen und die Matrixgröße n. es gibt die Liste der Einträge in Feindseligkeit zurück .