Czyich sąsiedzi są wrogo nastawieni?

10

Wprowadzenie

Na potrzeby tego wyzwania zdefiniujemy sąsiadów elementu w macierzy kwadratowej (takiej, że ) jako wszystkie wpisy które sąsiadują bezpośrednio z po przekątnej, w poziomie lub w pionie (tzn. „otaczają” , bez owijania się).A E = A i , j A EEAE=Ai,jAE E

W przypadku pedantów formalną definicją sąsiadów dla macierzy jest (indeksowany 0): gdzie n×nA N i ,Ai,jn×nAE i ,

Ni,j={Aa,b(a,b)Ei,j([0,n)Z)2}
mija,jot={ja-1,ja,ja+1}×{jot-1,jot,jot+1} \ {ja,jot}

Powiedzmy, że element o indeksie żyje we wrogości, jeśli jest chroniony prawem autorskim do wszystkich swoich sąsiadów (to znaczy ). Niestety, ten biedny wpis nie może pożyczyć nawet kubka cukru od swoich niegrzecznych pobliskich mieszkańców ...ja,jotgcd(ZAja,jot,n)=1nN.ja,jot

Zadanie

Dość historii: Biorąc pod uwagę macierz kwadratową M. dodatnich liczb całkowitych, wypisz jedną z następujących opcji:

  • Płaska lista elementów (deduplikowana lub nie) wskazująca wszystkie wpisy, które zajmują niektóre indeksy ja,jot w M. tak że sąsiedzi N.ja,jot są wrogo nastawieni.
  • Macierz boolowska z 1 s na pozycjach, w których sąsiedzi są wrogo nastawieni, a 0 przeciwnym razie (możesz wybrać dowolne inne spójne wartości zamiast 0 i 1 ).
  • Lista par indeksów ja,jot które reprezentują wrogie dzielnice.

Implementacja referencji w Physica - obsługuje również składnię Pythona dla I / O. Możesz pobierać dane wejściowe i generować dane wyjściowe dowolną standardową metodą w dowolnym rozsądnym formacie, zwracając uwagę, że te luki są domyślnie zabronione. To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach (w każdym języku)!

Co więcej, możesz również wziąć rozmiar matrycy jako dane wejściowe i dodatkowo możesz wziąć matrycę jako płaską listę, ponieważ zawsze będzie kwadratowa.

Przykład

Rozważ następującą macierz:

(641014272232535836)

Odpowiednimi sąsiadami każdego elementu są:

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

Dlatego wynik musi być jednym z następujących:

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

Przypadki testowe

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)]
Pan Xcoder
źródło
Pożyczasz rzeczy od wrogich sąsiadów? Z jakiegoś powodu przypomina mi to grę Jeffa Mintera Hover Bovver ...
Arnauld
Czy możemy przyjąć rozmiar matrycy jako dane wejściowe?
Delfad0r,
@ Delfad0r Zawsze zapomniałem o tym wspomnieć. Tak, możesz wziąć rozmiar matrycy jako dane wejściowe.
Pan Xcoder,

Odpowiedzi:

3

APL (Dyalog) , 17 bajtów

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

Wypróbuj online! (podziękowania dla ngn za tłumaczenie przypadków testowych na APL)

Krótkie wyjaśnienie

(×/∘,↓)⌺3 3 otrzymuje iloczyn każdego elementu z jego sąsiadami.

Następnie dzielę przez argument ÷⊢, aby każdy wpis w macierzy został odwzorowany na iloczyn jego sąsiadów.

Na koniec biorę gcd argumentu za pomocą tej macierzy ⊢∨i sprawdzam równość z 1,1=

Uwaga, podobnie jak w przypadku odpowiedzi ngn , nie udaje się to w przypadku niektórych danych wejściowych z powodu błędu interpretera.

H.PWiz
źródło
2

JavaScript (ES6), 121 bajtów

Zwraca macierz wartości boolowskich, gdzie false oznacza wrogi.

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

Wypróbuj online!

W jaki sposób?

Metoda zastosowana do izolacji 8 sąsiadów każdej komórki jest podobna do tej, którą tu opisałem .

Skomentował

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
źródło
2

MATL , 22 bajty

tTT1&Ya3thYC5&Y)Zd1=A)

Dane wejściowe to macierz. Dane wyjściowe to wszystkie liczby z wrogimi sąsiadami.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie z działającym przykładem

Rozważ dane wejściowe [38, 77, 11; 17, 51, 32; 66, 78, 19]jako przykład. Zawartość stosu pokazana jest od dołu do góry.

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
źródło
Czy to zadziała, jeśli matryca jest większa niż 3x3?
Robert Fraser,
@RobertFraser Tak, procedura nie zależy od rozmiaru matrycy. Zobacz na przykład ostatni przypadek testowy
Luis Mendo
1

APL (Dyalog Classic) , 23 22 bajtów

-1 bajt dzięki @ H.PWiz

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

Wypróbuj online!

nie obsługuje matryc mniejszych niż 3x3 z powodu błędu interpretera

ngn
źródło
@ H.PWiz, który jest bardzo inteligentny, czy chcesz opublikować go jako swój własny?
ngn
Jasne, możesz także użyć (⊃∨⊢)-> ∨∘⊂⍨tak myślę
H.PWiz
1

Galaretka , 24 bajty

Hmm, wydaje się długi.

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

Monadyczny link akceptujący listę list dodatnich liczb całkowitych, która zwraca listę każdej z wartości znajdujących się w wrogich dzielnicach (wersja 1 bez usuwania duplikatów).

Wypróbuj online! Lub zobacz zestaw testowy .

W jaki sposób?

ỊẠ€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
źródło
1

Python 2 , 182 177 166 bajtów

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

Wypróbuj online!

Wyświetla listę list z wpisami True / False.

Chas Brown
źródło
1

Haskell , 95 bajtów

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

Wypróbuj online!

Funkcja ?przyjmuje macierz mjako listę list i rozmiar macierzy n; zwraca listę wpisów z wrogości .

Delfad0r
źródło