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 k
Contoh:
Tugas Anda
Mengingat dan target jumlah , tugas Anda adalah untuk menemukan semua nilai yang mungkin dari sedemikian rupa sehingga jumlah dari unsur-unsur yang tersisa di adalah sama dengan .
Contoh:
Mengingat matriks di atas dan :
- adalah solusi, karena dan
- adalah satu-satunya solusi yang mungkin: dan
Jadi output yang diharapkan adalah .
Klarifikasi dan aturan
- Input dijamin untuk mengakui setidaknya satu solusi.
- Jumlah elemen dalam matriks asli dijamin akan lebih besar dari .
- Anda dapat mengasumsikan . Ini berarti bahwa matriks kosong tidak akan pernah mengarah ke solusi.
- Nilai-nilai 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 ]
- Ini adalah kode-golf .
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}
code-golf
array-manipulation
matrix
Arnauld
sumber
sumber
[[1,5],[1],[5],[]]
untuk kasus uji pertama) menjadi sarana output yang valid?Jawaban:
K (ngn / k) , 39 byte
Cobalah online!
terima kasih @ Adám untuk penjelasan ini :
{
...}
fungsi,x
adalah M dany
adalah S,/x
ratakan M (ini adalah kandidat k )a:
ditugaskan kepadaa
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 itub:
tetapkan itu untukb
&/
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 besary=
daftar Boolean yang menunjukkan di mana S sama dengan jumlah itu&
indeks Truesa@
menggunakannya untuk mengindeks ke elemen ( kandidat k )sumber
APL (Dyalog Unicode) ,
353328 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 benarsumber
{M[⍸⍺={+/,(∧⌿d)/M⌿⍨∧/d←M≠⍵}¨M←⍵]}
M
ketika belum dibuat?⍵
seperti⍺
di dfn dalam sama membingungkan bagi saya{⍵[⍸⍺=+/¨(,⍵×∧/∘.∧∧⌿)¨⍵≠⊂⍵]}
R ,
7873 byteCobalah online!
Tidak mengurutkan atau menduplikasi output.
Kredit untuk J.Doe & Giuseppe untuk -5 byte.
sumber
Jelly ,
2019171514 byteIni adalah tautan monadik yang menggunakan M sebagai argumen dan membaca S dari STDIN.
Cobalah online!
Bagaimana itu bekerja
sumber
Haskell ,
88868477 byteVerifikasi semua testcases .
Penjelasan
sumber
Pyth ,
27 23 22 2120 byteSuite uji!
Tidak diduplikasi.
Bagaimana itu bekerja?
sumber
Python 2 ,
114108 byteCobalah online!
sumber
Perl 6 ,
8074 byteCobalah online!
Penjelasan
sumber
05AB1E , 21 byte
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
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∀c∈C | |
~
+
Akhirnya, ia memetakan ke dan semua bilangan bulat lainnya ke dan melakukan perkalian elemen-bijaksana dengan :0 1 0 M.
Setelah itu jumlah dari matriks yang dihasilkan dihitung.
sumber
[[1,1,0,1],[2,0,0,2],[2,0,1,0]]
yang mengacaukan saya untuk nomor1
(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 untuk1|2
(1 2~
di synthax 05AB1E) menghasilkan 3, ini karenalogical OR
bertindak sepertibinary OR
ketika angka selain0
/1
terlibat (saya pikir / berasumsi).+
Saya kira itu bisa diganti , jadi saya harap tidak akan ada masalah dengannya :)05AB1E (warisan) ,
2726 byteTidak 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:
sumber
Jelly , 22 byte
Cobalah online!
-6 byte menggunakan pendekatan umum dari jawaban 05AB1E Mr. Xcoder.
sumber
Arang , 33 byte
Cobalah online! Tautan adalah untuk mengungkapkan versi kode dan memasukkan deduplikasi. Penjelasan:
Ratakan larik input pertama
q
ke dalam daftar yang telah ditentukanu
.Untuk setiap elemen dari daftar, jumlah array, tetapi jika baris berisi elemen kemudian gunakan
0
bukan jumlahnya, dan ketika menjumlahkan baris yang tidak mengandung elemen, jika kolom berisi elemen kemudian gunakan0
bukan nilai kolom . Ini sedikit lebih golf daripada menyaring elemen karena Charcoal tidak dapat menjumlahkan daftar kosong.sumber
Bersihkan , 92 byte
Cobalah online!
Dijelaskan:
sumber
MATLAB - 80 byte
( Dikoreksi dan ) Dipadatkan:
Dan dalam versi yang dikembangkan sepenuhnya:
Berkat komentar untuk menyoroti kesalahan awal saya. Perhatikan bahwa versi ini tidak menduplikat output.
Dimungkinkan untuk menduplikat output dengan 5 byte lebih:
sumber