Tetangga siapa yang bermusuhan?

10

pengantar

Untuk keperluan tantangan ini, kita akan mendefinisikan tetangga dari elemen E dalam matriks persegi SEBUAH (sedemikian sehingga E=SEBUAHsaya,j ) sebagai semua entri SEBUAH yang berbatasan langsung secara diagonal, horizontal atau vertikal ke E (yaitu mereka "mengelilingi" E , tanpa membungkus).

Untuk para pendaki, definisi formal dari tetangga SEBUAHsaya,j untuk sebuahn×nmatixSEBUAHadalah (0-diindeks):

Nsaya,j={SEBUAHSebuah,b(Sebuah,b)Esaya,j([0,n)Z)2}
mana
Esaya,j={saya-1,saya,saya+1}×{j-1,j,j+1} \ {saya,j}

Katakanlah elemen pada indeks saya,jgcd(SEBUAHsaya,j,n)=1nNsaya,j

Tugas

Cukup cerita: Diberikan matriks persegi dari bilangan bulat positif, hasilkan salah satu dari yang berikut:M.

  • Daftar elemen yang datar (diduplikasi atau tidak) yang menunjukkan semua entri yang menempati beberapa indeks di M sedemikian rupa sehingga tetangga N_ {i, \: j} bermusuhan.saya,jM.Nsaya,j
  • Matriks boolean dengan s pada posisi di mana tetangga tidak bersahabat dan sebaliknya (Anda dapat memilih nilai konsisten lainnya sebagai pengganti dan ).1001
  • Daftar pasangan indeks yang mewakili lingkungan yang tidak bersahabat.saya,j

Implementasi Referensi di Physica - mendukung sintaksis Python juga untuk I / O. Anda dapat mengambil input dan memberikan output melalui metode standar apa pun dan dalam format apa pun yang masuk akal, sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah kode-golf, jadi kode terpendek dalam byte (dalam setiap bahasa) menang!

Selain itu, Anda dapat mengambil ukuran matriks sebagai input juga dan juga dapat mengambil matriks sebagai daftar datar karena akan selalu persegi.

Contoh

Pertimbangkan matriks berikut:

(641014272232535836)

Tetangga yang sesuai dari setiap elemen adalah:

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

Dan dengan demikian hasilnya harus salah satu dari yang berikut:

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

Uji kasus

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)]
Tuan Xcoder
sumber
Meminjam barang dari tetangga yang bermusuhan? Untuk beberapa alasan, ini mengingatkan saya pada permainan Jeff Minter Hover Bovver ...
Arnauld
Bisakah kita mengambil ukuran matriks sebagai input?
Delfad0r
@ Delfad0r Saya selalu lupa menyebutkan itu. Ya, Anda dapat menggunakan ukuran matriks sebagai input.
Tn. Xcoder

Jawaban:

3

APL (Dyalog) , 17 byte

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

Cobalah online! (kredit untuk ngn karena menerjemahkan kasus uji ke APL)

Penjelasan singkat

(×/∘,↓)⌺3 3 mendapat produk dari setiap elemen dengan tetangganya.

Kemudian saya bagi dengan argumen ÷⊢, sehingga setiap entri dalam matriks telah dipetakan ke produk tetangganya.

Akhirnya saya mengambil gcd dari argumen dengan matriks ini ⊢∨, dan memeriksa kesetaraan dengan 1,1=

Catatan, seperti dengan jawaban ngn , ini gagal untuk beberapa input karena bug pada juru bahasa.

H.Piz
sumber
2

JavaScript (ES6), 121 byte

Mengembalikan matriks nilai Boolean, di mana false berarti bermusuhan.

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

Cobalah online!

Bagaimana?

Metode yang digunakan untuk mengisolasi 8 tetangga masing-masing sel mirip dengan yang saya jelaskan di sini .

Berkomentar

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
sumber
2

MATL , 22 byte

tTT1&Ya3thYC5&Y)Zd1=A)

Input adalah sebuah matriks. Keluaran adalah semua angka dengan tetangga yang bermusuhan.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan dengan contoh yang berhasil

Pertimbangkan input [38, 77, 11; 17, 51, 32; 66, 78, 19]sebagai contoh. Isi tumpukan ditampilkan dari bawah ke atas.

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
sumber
Apakah ini akan berhasil jika matriks lebih besar dari 3x3?
Robert Fraser
@ RobertTraser Ya, prosedur tidak tergantung pada ukuran matriks. Lihat contoh tes terakhir misalnya
Luis Mendo
1

APL (Dyalog Classic) , 23 22 byte

-1 byte terima kasih kepada @ H.PWiz

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

Cobalah online!

tidak mendukung matriks yang lebih kecil dari 3x3 karena ada bug pada juru bahasa

ngn
sumber
@ H.Piz yang sangat cerdas, apakah Anda ingin mempostingnya sebagai milik Anda?
ngn
Tentu, Anda juga dapat menggunakan (⊃∨⊢)-> ∨∘⊂⍨Saya pikir
H.PWiz
1

Jelly , 24 byte

Hmm, sepertinya panjang.

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

Tautan monadik yang menerima daftar daftar bilangan bulat positif yang mengembalikan daftar setiap nilai yang ada di lingkungan yang bermusuhan (versi 1 tanpa de-duplikasi).

Cobalah online! Atau lihat test-suite .

Bagaimana?

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

Python 2 , 182 177 166 byte

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

Cobalah online!

Output daftar daftar dengan entri Benar / Salah.

Chas Brown
sumber
1

Haskell , 95 byte

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

Cobalah online!

Fungsi ?mengambil matriks msebagai daftar daftar dan ukuran matriks n; ia mengembalikan daftar entri dalam permusuhan .

Delfad0r
sumber