pengantar
Pertimbangkan daftar L kosong bilangan bulat. Sebuah zero-sum slice dari L adalah subsequence bersebelahan L yang jumlahnya sama dengan 0. Misalnya, [1, -3, 2] adalah zero-sum sepotong [-2, 4, 1, -3, 2, 2 , -1, -1] , tetapi [2, 2] tidak (karena itu tidak berjumlah 0), dan juga tidak [4, -3, -1] (karena tidak berdekatan).
Koleksi irisan zero-sum dari L adalah penutup zero-sum dari L jika setiap elemen milik setidaknya satu dari irisan. Sebagai contoh:
L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B = [1, -3, 2]
C = [2, -1, -1]
Tiga zero-sum irisan A , B dan C membentuk zero-sum sampul L . Beberapa salinan dari irisan yang sama dapat muncul dalam sampul zero-sum, seperti ini:
L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B = [-1, -1, 2]
C = [2, -1, -1]
Tentu saja, tidak semua daftar memiliki sampul zero-sum; beberapa contoh adalah [2, -1] (setiap irisan memiliki jumlah bukan nol) dan [2, 2, -1, -1, 0, 1] ( 2 paling kiri bukan bagian dari irisan zero-sum).
Tugas
Input Anda adalah daftar bilangan bulat nonempty L , diambil dalam format apa pun yang masuk akal. Output Anda akan menjadi nilai kebenaran jika L memiliki penutup zero-sum, dan nilai palsu jika tidak.
Anda dapat menulis program atau fungsi lengkap, dan jumlah byte terendah menang.
Uji kasus
[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True
[2,2,-1,-1,0,1] -> False
seharusnya contoh palsu ketiga menjadi benar karena kedua irisan[2,-1,-1]
dan[-1,0,1]
tambahkan ke nol dan semua elemen mereka ada di daftar asli?Jawaban:
Jelly ,
1312 byteCobalah online!
Bagaimana itu bekerja
sumber
Mathematica,
6665 byteDisimpan 1 byte, dan semoga belajar trik baru untuk masa depan, terima kasih kepada ngenisis!
Dua alternatif yang sama panjangnya, keduanya adalah fungsi yang tidak disebutkan namanya mengambil daftar bilangan bulat sebagai input dan mengembalikan
True
atauFalse
:Dalam kedua kasus,
Tr@#[[i;;j]]
hitung jumlah irisan input dari posisii
ke posisij
(diindeks 1).Product[...,{i,k},{j,k,l}]
mengalikan semua irisan-jumlah ini, sebagaii
rentang di atas indeks yang paling banyakk
danj
rentang di atas indeks yang setidaknyak
. (Perhatikan bahwal=Tr[1^#]
mendefinisikanl
sebagai jumlah dari1
semua kekuatan dalam daftar input, yang hanya panjang dari daftar.) Dengan kata lain, produk ini sama dengan 0 jika dan hanya jikak
elemen th milik kepingan zero-sum .Dalam versi pertama, masing-masing produk tersebut dibandingkan dengan
0
, danAnd@@
kembaliTrue
tepat ketika setiap produk tunggal sama0
. Dalam versi kedua, daftar produk ditindaklanjuti oleh fungsiNorm
(panjangl
vektor -dimensi), yang sama dengan0
jika dan hanya jika setiap entri sama0
.sumber
Tr[1^#]
menyimpan1
byte dariLength@#
.0^
berhasil0==
? Tidak yakin bagaimana Mathematica mengatasinya. (Anda akan kembali1
/0
bukannyatrue
/false
)Indeterminate
untuk0^0
. Juga,1
/0
tidak benar-benar truthy / falsy di Mathematica-itu terlalu kuat diketik untuk pegolf make happy :)Mathematica,
6564 byteTerima kasih kepada ngenisis karena telah menghemat 1 byte.
Saya lebih suka menemukan solusi pencocokan pola murni, tetapi terbukti rumit (dan hal-hal seperti
{___,a__,___}
selalu super panjang).sumber
Haskell, 94 byte
Contoh penggunaan:
g [-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3]
->True
.Cara kerjanya (mari gunakan
[-1,1,5,-5]
untuk input):sumber
powerslice
adalah nama fungsi yang hebat.Ruby, 81 byte
Cobalah online
Solusi brute force sederhana; untuk setiap elemen array, cobalah mencari irisan zero-sum yang berisi itu.
sumber
J,
3635 byteUntuk setiap subsum, saya menambahkan indeks elemen dan saya menyimpan indeks iff subsum
0
dan kemudian memeriksa apakah setiap indeks ada.Trik: indeks berbasis 1 daftar dapat dihasilkan dengan
#\
panjang mis. Setiap.Pemakaian:
Cobalah online di sini.
sumber
#\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\
JavaScript (ES6), 109 byte
Cuplikan tes
Tampilkan cuplikan kode
sumber
Python,
123120 byte-3 byte terima kasih kepada @Zgarb
Mempopulasikan daftar dengan ukuran yang sama dengan input dengan irisan zero-sum dan overwrites menurut indeks, mengembalikan kesetaraannya ke aslinya di akhir.
sumber
0
sebagai penggantiNone
. Tidak akan ada false positive, karena setiap0
input selalu merupakan bagian atau irisan zero-sum.Scala, 49 byte
Cobalah di ideone
Pemakaian:
Tidak Disatukan:
Penjelasan:
sumber
%
sebagai nama parameter? Keren!.,;:()[]{}\"'
. Cukup berguna untuk bermain golf, karena mereka terpisah dari huruf oleh parse, sehingga Anda dapat menghemat spasi.true
untuk case falsy kedua.Python, 86 Bytes
Truthy = 1 Falsy = Tidak ada
sumber
1
untuk kasus uji ketiga.1
untuk semua kasus uji kecuali dua yang salah pertama.Clojure, 109 byte
Menghasilkan semua partisi yang berjumlah nol, memeriksa bahwa ia memiliki indeks yang berbeda "panjang input vektor".
sumber
PHP, 104 byte
Brute force dan masih lebih dari 99 byte. :-(
mengambil input dari argumen baris perintah,
1
untuk kebenaran, kosong untuk kepalsuan. Jalankan dengan-r
.kerusakan
$argv[0]
berisi nama file; jika dijalankan dengan-r
, itu akan-
dan dievaluasi untuk0
untuk operasi numerik.sumber
JavaScript (ES6), 102 byte
Menghitung jumlah parsial untuk semua elemen
i..j
inklusif, dan me-reset unsur-unsur yang relevan darib
dari1
ke0
ketika menemukan sejumlah nol, akhirnya memeriksa bahwa tidak ada1
s kiri.sumber