Matikan matriks untuk mendapatkan jumlah yang diinginkan

21

Definisi

Diberi matriks dari integer non-negatif dan integer non-negatif , kami mendefinisikan sebagai fungsi "memotong" yang menghapus semua baris dan semua kolom dalam yang berisi .k F k M kMkFkMk

Contoh:

M=(615128985604)F5(M)=(1260)

Tugas Anda

Mengingat M dan target jumlah S , tugas Anda adalah untuk menemukan semua nilai yang mungkin dari k sedemikian rupa sehingga jumlah dari unsur-unsur yang tersisa di Fk(M) adalah sama dengan S .

Contoh:

Mengingat matriks di atas M dan S=9 :

  • k=5 adalah solusi, karena F5(M)=(1260) dan 1+2+6+0=9
  • k=1 adalah satu-satunya solusi yang mungkin: F1(M)=(54) dan 5+4=9

Jadi output yang diharapkan adalah {1,5} .

Klarifikasi dan aturan

  • Input dijamin untuk mengakui setidaknya satu solusi.
  • Jumlah elemen dalam matriks asli dijamin akan lebih besar dari S .
  • Anda dapat mengasumsikan S>0 . Ini berarti bahwa matriks kosong tidak akan pernah mengarah ke solusi.
  • Nilai-nilai k dapat dicetak atau dikembalikan dalam urutan apa pun dan dalam format apa pun yang wajar dan tidak ambigu.
  • Anda diizinkan untuk tidak output (mis. atau dianggap sebagai jawaban yang valid untuk contoh di atas).[ 1 , 5 , 1 , 5 ][1,1,5,5][1,5,1,5]
  • Ini adalah .

Uji kasus

M = [[6,1,5],[1,2,8],[9,8,5],[6,0,4]]
S = 9
Solution = {1,5}

M = [[7,2],[1,4]]
S = 7
Solution = {4}

M = [[12,5,2,3],[17,11,18,8]]
S = 43
Solution = {5}

M = [[7,12],[10,5],[0,13]]
S = 17
Solution = {0,13}

M = [[1,1,0,1],[2,0,0,2],[2,0,1,0]]
S = 1
Solution = {2}

M = [[57,8,33,84],[84,78,19,14],[43,14,81,30]]
S = 236
Solution = {19,43,57}

M = [[2,5,8],[3,5,8],[10,8,5],[10,6,7],[10,6,4]]
S = 49
Solution = {2,3,4,7}

M = [[5,4,0],[3,0,4],[8,2,2]]
S = 8
Solution = {0,2,3,4,5,8}
Arnauld
sumber
Apakah mempertahankan struktur asli array input (misalnya, [[1,5],[1],[5],[]]untuk kasus uji pertama) menjadi sarana output yang valid?
Shaggy
@ Shaggy Ya. Itu terlihat masuk akal.
Arnauld

Jawaban:

10

K (ngn / k) , 39 byte

{a@&y=x{+//x*(&/'b)&\:&/b:~x=y}/:a:,/x}

Cobalah online!

terima kasih @ Adám untuk penjelasan ini :

{... }fungsi, xadalah M dan yadalah S

,/x ratakan M (ini adalah kandidat k )

a: ditugaskan kepada a

x{... }/: terapkan fungsi berikut untuk masing-masing saat menggunakan M sebagai argumen tetap kiri ( x):

  x=y Matriks Boolean menunjukkan di mana elemen M sama dengan kandidat k saat ini

  ~ meniadakan itu

  b: tetapkan itu untuk b

  &/ DAN reduksi (menemukan kolom tanpa itu k )

  ()&\: DAN itu dengan masing-masing hal berikut:

   &/'b DAN pengurangan masing-masing (menemukan baris tanpa itu k )

  x* kalikan M dengan itu

  +// jumlah besar

y= daftar Boolean yang menunjukkan di mana S sama dengan jumlah itu

& indeks Trues

a@ menggunakannya untuk mengindeks ke elemen ( kandidat k )

ngn
sumber
Jangan ragu untuk mengoreksi penjelasannya.
Adám
Bahaya penjelasan salin-tempel ...
Adám
6

APL (Dyalog Unicode) , 35 33 28 byte SBCS

-7 Terima kasih kepada ngn.

Lambda infix Anonim. Membawa S sebagai argumen kiri dan M sebagai argumen kanan.

{⍵[⍸⍺=(+/∘,⍵×∧/∘.∧∧⌿)¨⍵≠⊂⍵]}

Cobalah online!

{} "Dfn", dan merupakan argumen kiri dan kanan ( S dan M ) masing-masing:

⍵[] Indeks M dengan koordinat berikut:

  ⊂⍵ lampirkan M untuk memperlakukannya sebagai elemen tunggal

  ⍵= bandingkan setiap elemen (yaitu k kandidat) M dengan keseluruhan M

  (...  terapkan fungsi tersembunyi berikut untuk masing-masing:

   ∧⌿ vertikal DAN reduksi (menemukan kolom tanpa kandidat k itu )

… Produk ∘.∧ Cartesian Boolean dengan:

    ∧/ horizontal DAN reduksi (menemukan baris tanpa kandidat k )

   ⍵× kalikan M dengan topeng itu

   +/∘, jumlah matriks yang diratakan

  ⍺= Boolean menunjukkan di mana S sama dengan jumlah itu

   indeks mana itu benar

Adm
sumber
1
{M[⍸⍺={+/,(∧⌿d)/M⌿⍨∧/d←M≠⍵}¨M←⍵]}
ngn
@ ngn Terima kasih. Saya tidak akan menggunakan global, karena itu membuat urutan evaluasi membingungkan: - Bagaimana Anda bisa mengindeks Mketika belum dibuat?
Adám
lewat seperti di dfn dalam sama membingungkan bagi saya
ngn
{⍵[⍸⍺=+/¨(,⍵×∧/∘.∧∧⌿)¨⍵≠⊂⍵]}
ngn
@ Ngn Ya, saya ingin melakukan sesuatu seperti itu. Terima kasih!
Adám
6

R , 78 73 byte

function(m,s)m[Map(function(y)sum(m[(w=-which(m==y,T))[,1],w[,2]]),m)==s]

Cobalah online!

Tidak mengurutkan atau menduplikasi output.

Kredit untuk J.Doe & Giuseppe untuk -5 byte.

Kirill L.
sumber
4
76 bytes
J.Doe
4
@ J.Doe 73 byte
Giuseppe
5

Jelly , 20 19 17 15 14 byte

pZnⱮFȦ€€ḋFẹƓịF

Ini adalah tautan monadik yang menggunakan M sebagai argumen dan membaca S dari STDIN.

Cobalah online!

Bagaimana itu bekerja

pZnⱮFȦ€€ḋFẹƓịF  Main link. Argument: M

 Z              Zip; transpose the rows and columns of M.
p               Take the Cartesian product of M and its transpose, yielding all pairs
                (r, c) of rows and columns of M.
    F           Flatten; yield the elements of M.
  nⱮ            Not equal map; for each element e of M, compare the elements of the
                pairs (r, c) with e.
     Ȧ€€        All each each; for each array of Booleans corresponding to an (r, c)
                pair, test if all of them are true.
         F      Flatten; yield the elements of M.
        ḋ       Take the dot product of each list of resulting Booleans and the
                elements of M.
           Ɠ    Read an integer S from STDIN.
          ẹ     Find all indices of S in the dot products.
             F  Flatten; yield the elements of M.
            ị   Retrieve the elements of the right at the indices from the left.
Dennis
sumber
Tandai kata-kata saya lol :) Jawaban yang bagus, +1
Mr. Xcoder
5

Haskell , 88 86 84 77 byte

  • -2 byte terima kasih kepada BWO
  • -7 byte terima kasih kepada Tesseract
m!s=[k|k<-m>>=id,s==sum[x|r<-m,all(/=k)r,(i,x)<-zip[0..]r,all((/=k).(!!i))m]]

Verifikasi semua testcases .

Penjelasan

m ! s =                                         -- function !, taking m and s as input
    [k |                                        -- the list of all k's such that
        k <- m >>= id,                          -- * k is an entry of m
        s == sum                                -- * s equals the sum of
            [x |                                --     the list of x's such that
                r <- m,                         --     * r is a row of m
                all (/= k) r,                   --     * r does not contain k
                (i, x) <- zip [0 ..] r,         --     * i is a valid column index; also let x = r[i]
                all ((/= k) . (!! i)) m         --     * none of the rows contain k at index i
            ]
    ]
Delfad0r
sumber
Haruskah itu mengatakan "fungsi f"?
Quintec
1
@ Quintec Memang seharusnya begitu, tetapi saya mengubahnya menjadi "berfungsi!" untuk menyimpan 2 byte berkat BWO
Delfad0r
5

Pyth ,  27 23 22 21  20 byte

fqvzss.DRsxLTQ-I#TQs

Suite uji!

Tidak diduplikasi.

Bagaimana itu bekerja?

fqvzss.DRsxLTQ-I#TQs     Full program.
f                  s     Flatten M and keep only those elements T which satisfy:
 qvzss.DRsxLTQ-I#TQ      The filtering function. Breakdown:
              -I#TQ      Discard the rows that contain T. More elaborate explanation:
                # Q         |-> In M, keep only those elements that are...
               I            |-> Invariant under (equal to themselves after...)
              -  T          |-> Removing T.
                         Let's call the result of this expression CR (chopped rows).
          xLTQ           Map over the rows M and retrieve all indices of T.
         s               Collect indices in 1D list (flatten). Call this I.
      .DR                For each row left in CR, remove the elements at indices in I.
    ss                   Sum all the elements of this matrix flattened.
 qvz                     And then finally check whether they equal S.
Tuan Xcoder
sumber
4

Python 2 , 114 108 byte

lambda m,s:{a for a in sum(m,[])if s==sum(v for l in m for i,v in enumerate(l)if{a}-set(l)-set(zip(*m)[i]))}

Cobalah online!

TFeld
sumber
4

Perl 6 , 80 74 byte

->\m,\s{grep {s==sum m[m.$_;[[Z](m).$_]]}o{*.grep(:k,!*.grep($_))},m[*;*]}

Cobalah online!

Penjelasan

->\m,\s{...}  # Anonymous block taking arguments m and s
  grep {...}o{...},m[*;*]   # Filter matrix elements
                            # with combination of two functions
    *.grep(:k,!*.grep($_))  # (1) Whatever code returning matching rows
    s==sum m[               # (2) s equals sum of elements
      m.$_;                 #     in matched rows
      [                     #     (array supporting multiple iterations)
       [Z](m).$_            #     and matched columns (matched rows
                            #     of m transposed with [Z])
      ]
    ]
nwellnhof
sumber
3

05AB1E , 21 byte

²˜ʒQεZ+}øεZ<~}ø_*OO¹Q

Cobalah online!

Hanya setelah saya menulis jawaban ini saya melihat Kevin . Saya percaya ini sangat berbeda, jadi saya mempostingnya secara terpisah. Intuisi saya mengatakan bahwa jumlah byte optimal adalah sekitar 18, jadi saya harus meninjau kembali ini dan melihat apa lagi yang bisa saya lakukan. Dengan kode saat ini, tidak mungkin untuk menulis test suite tetapi saya telah memverifikasi sendiri semua test case dan hasilnya benar.

Algoritma Pemotongan

k=5

M.=(615128985604)

k

(001000001000)

M.Rmaks(R)R

(112000112000)

Kemudian, ia berjalan melalui transpos dan untuk setiap kolom , ia melakukan operasi (di mana adalah bitwise ATAU 05AB1E - penambahan harus bekerja juga, jadi ganti dengan jika Anda ingin mengujinya juga), yang menghasilkan:M.C(maks(C)-1) || c  cC||~+

(113001113001)

Akhirnya, ia memetakan ke dan semua bilangan bulat lainnya ke dan melakukan perkalian elemen-bijaksana dengan :010M.

(000110000110)(000120000600)

Setelah itu jumlah dari matriks yang dihasilkan dihitung.

Tuan Xcoder
sumber
1
Jawaban bagus! Aku tahu pasti milikku akan golf. Saya sudah cukup senang untuk membuatnya bekerja, termasuk kasus yang menjengkelkan [[1,1,0,1],[2,0,0,2],[2,0,1,0]]yang mengacaukan saya untuk nomor 1(yang menghilangkan setiap kolom ..) Saya memang punya sedikit di bawah 20 di kepala saya serta kemungkinan. Sayang sekali hampir tidak ada builtin untuk matriks, meskipun produk yang ditambahkan baru-baru ini. Sedangkan untuk 1|2( 1 2~di synthax 05AB1E) menghasilkan 3, ini karena logical ORbertindak seperti binary ORketika angka selain 0/ 1terlibat (saya pikir / berasumsi).
Kevin Cruijssen
@KevinCruijssen Oh Anda benar! Kemudian, dokumen harus menulis bitwise ATAU , tidak logis ATAU . Saya harus segera memperbaikinya. Bagaimanapun, bitwise ATAU harus bekerja juga saya pikir. +Saya kira itu bisa diganti , jadi saya harap tidak akan ada masalah dengannya :)
Tn. Xcoder
2

05AB1E (warisan) , 27 26 byte

˜ʒ©¹ε®å_}¹ζʒ®å_}ζ‚ζ€€OPOIQ

Tidak memilah atau menyamakan hasil.
Hanya berfungsi di warisan (untuk saat ini), karena jumlah-masing-masing tampaknya melakukan beberapa hal aneh ketika bagian dari daftar batin adalah bilangan bulat dan lainnya adalah daftar ..

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

˜              # Flatten the (implicit) matrix-input
               #  i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [6,1,5,1,2,8,9,8,5,6,0,4]
 ʒ             # Filter this list by:
  ©            #  Store the current value in a register-variable
   ¹           #  Take the matrix-input
    ε   }      #  Map it to:
     ®å_       #   0 if the current number is in this row, 1 if not
               #    i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] and 6 → [0,1,1,0]
   ¹           #  Take the matrix-input again
    ζ          #  Swap its rows and columns
               #   i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [[6,1,9,6],[1,2,8,0],[5,8,5,4]]
     ʒ   }     #  Filter it by:
      ®å_      #   Only keep the inner lists that does not contain the current number
               #    i.e. [[6,1,9,6],[1,2,8,0],[5,8,5,4]] and 6 → [[1,2,8,0],[5,8,5,4]]
               #    i.e. [[1,2,2],[1,0,0],[0,0,1],[1,2,0]] and 1 → []
          ζ    #  After filtering, swap it's rows and columns back again
               #   i.e. [[1,2,8,0],[5,8,5,4]] → [[1,5],[2,8],[8,5],[0,4]]
   ‚ζ          #  Pair both lists together and zip them
               #   i.e. [0,1,1,0] and [[1,5],[2,8],[8,5],[0,4]]
               #    → [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #   i.e. [0,1,0] and [] → [[0,' '],[1,' '],[0,' ']]
              #  Map each inner list / value to:
      O       #   Sum each
               #    i.e. [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #     → [[0,6],[1,10],[1,13],[0,4]]
               #    i.e. [[0,' '],[1,' '],[0,' ']]
               #     → [[0,0],[1,0],[0,0]]
               #  (NOTE: For most test cases just `O` instead of `€€O` would be enough,
               #   but not if we removed ALL zipped inner lists for a number, like the 
               #   second example above with input [[1,1,0,1],[2,0,0,2],[2,0,1,0]] and 1)
        P      #  Now take the product of each inner list
               #   i.e. [[0,6],[1,10],[1,13],[0,4]] → [0,10,13,0]
         O     #  Then take the sum of those
               #   i.e. [0,10,13,0] → 23
          IQ   #  And only keep those that are equal to the number-input
               #   i.e. 23 and 9 → 0 (falsey), so it's removed from the flattened input
Kevin Cruijssen
sumber
1

Jelly , 22 byte

=+Ṁ$€Z$⁺’¬×⁸FS
F³ç=⁹ƲƇ

Cobalah online!

-6 byte menggunakan pendekatan umum dari jawaban 05AB1E Mr. Xcoder.

HyperNeutrino
sumber
1

Arang , 33 byte

FθFι⊞υκIΦυ⁼ηΣEθ∧¬№λιΣEλ∧¬№Eθ§πξιν

Cobalah online! Tautan adalah untuk mengungkapkan versi kode dan memasukkan deduplikasi. Penjelasan:

FθFι⊞υκ

Ratakan larik input pertama qke dalam daftar yang telah ditentukan u.

  υ                          Flattened array
 Φ                           Filter elements
       θ                     Input array
      E                      Map over rows
            ι                Current element
           λ                 Current row
          №                  Count matching elements
         ¬                   Logical Not
        ∧                    Logical And
               λ             Current row
              E              Map over columns
                    θ        Input array
                   E         Map over rows
                      π      Inner row
                       ξ     Column index
                     §       Inner element
                        ι    Current element
                  №          Count matching elements
                 ¬           Logical Not
                ∧            Logical And
                         ν   Current element
             Σ               Sum
     Σ                       Sum
    η                        Second input
   ⁼                         Equals
I                            Cast to string
                             Implicitly print each result on its own line

Untuk setiap elemen dari daftar, jumlah array, tetapi jika baris berisi elemen kemudian gunakan 0bukan jumlahnya, dan ketika menjumlahkan baris yang tidak mengandung elemen, jika kolom berisi elemen kemudian gunakan 0bukan nilai kolom . Ini sedikit lebih golf daripada menyaring elemen karena Charcoal tidak dapat menjumlahkan daftar kosong.

Neil
sumber
1

Bersihkan , 92 byte

import StdEnv
$m s=[c\\r<-m,c<-r|sum[b\\a<-m|all((<>)c)a,b<-a&x<-[0..]|all(\u=u!!x<>c)m]==s]

Cobalah online!

Dijelaskan:

$ m s                       // the function $ of `m` and `s`
 = [                        // is equal to
  c                         // the value `c`
  \\ r <- m                 // for every row `r` in `m`
  , c <- r                  // for every value `c` in `r`
  | sum [                   // where the sum of
   b                        // the value `b`
   \\ a <- m                // for every row `a` in `m`
   | all ((<>)c) a          // where `c` isn't in `a`
   , b <- a                 // for every value `b` in `a`
   & x <- [0..]             // with every column index `x` from zero
   | all (\u = u!!x <> c) m // where `c` isn't in column `x`
  ] == s                    // equals `s`
 ]
Suram
sumber
1

MATLAB - 80 byte

( Dikoreksi dan ) Dipadatkan:

function f(M,s);for k=M(:)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end

Dan dalam versi yang dikembangkan sepenuhnya:

function getthesum(M,s)

for k=M(:)'                         % For each element of M
    x = M==k ;                      % Index elements equal to "k"
    N = M( ~sum(x,2) , ~sum(x) ) ;  % New matrix with only the appropriate rows/columns
    if sum(sum(N))==s               % sum rows and columns and compare to "s"
        k                           % display "k" in console if "k" is valid
    end
end

Berkat komentar untuk menyoroti kesalahan awal saya. Perhatikan bahwa versi ini tidak menduplikat output.

Dimungkinkan untuk menduplikat output dengan 5 byte lebih:

% This will only cycle through the unique elements of 'M' (85 bytes):

function f(M,s);for k=unique(M)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end
Hoki
sumber
1
k dapat berupa elemen matriks apa pun.
Dennis
@ Dennis, oops itu benar ... Buruk saya, saya akan memperbaikinya hari ini. Terima kasih telah menunjukkannya.
Hoki
1
@Arnauld. Maaf saya sedang liburan, sudah diperbaiki sekarang.
Hoki