Array saya harus sama dengan ini, tetapi tidak!

21

Diberikan array bilangan bulat ayang berisi n bilangan bulat, dan bilangan bulat tunggal x; menghapus jumlah elemen paling sedikit dari auntuk membuat jumlah asama dengan x. Jika tidak ada kombinasi akaleng x, kembalikan nilai palsu.

Seperti yang ditunjukkan dalam komentar, ini adalah set maksimum dengan jumlah x , maaf otak matematika saya yang lebih rendah. Saya lupa banyak istilah sejak kuliah.

Contoh (Kebenaran):

f([1,2,3,4,5,6,7,8,9,10], 10) = [1,2,3,4]

f([2,2,2,2,2,2,2,2,2], 10) = [2,2,2,2,2]

f([2,2,2,2,-2,-2,-2,-4,-2], -8) = [2,2,-2,-2,-2,-4,-2]

f([-2,-4,-2], -6) = [-4,-2] OR [-2,-4]

f([2,2,2,4,2,-2,-2,-2,-4,-2], 0) = [2,2,2,4,2,-2,-2,-2,-4,-2] (Tidak berubah)

f([], 0) = [] (Kasus Jumlah-Nol yang Tidak Berubah)

Contoh (Falsy, nilai non-array yang konsisten):

Tidak Mungkin Membuat Kasus: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Zero Sum Case: f([], non-zero number) = falsy (E.G. -1)

  • Catatan: nilai apa pun seperti [-1]tidak dapat valid untuk falsy, karena ini merupakan output potensial yang sebenarnya.

Aturan:

  • Input dapat diambil dalam bentuk array, atau sebagai daftar argumen, yang terakhir atau yang pertama x.
  • Output dapat berupa daftar bilangan bulat yang dibatasi. EG 1\n2\n3\natau [1,2,3].
  • Nilai apa pun dapat digunakan sebagai indikator palsu, selain array bilangan bulat.
  • Kode Anda harus memaksimalkan ukuran array akhir, pesanan tidak masalah.
    • EG Untuk f([3,2,3],5)keduanya [2,3]dan [3,2]sama-sama valid.
    • EG Untuk f([1,1,2],2)Anda hanya dapat kembali [1,1]karena [2]lebih pendek.
  • Baik jumlah adan nilai xakan lebih kecil dari 2^32-1dan lebih besar dari -2^32-1.
  • Ini adalah kode-golf , kemenangan byte-count terendah.
  • Jika ada beberapa subarrays dengan ukuran yang sama yang valid, itu tidak dapat diterima untuk menghasilkan semuanya. Anda harus memilih satu dan mengeluarkan yang itu.

Beri tahu saya jika ini telah diposting, saya tidak dapat menemukannya.

Posting yang saya temukan seperti ini : Terkait tetapi ditutup , ...

code-golf array-manipulation Guci Gurita Ajaib
sumber
1
Saya kira "Falsy, ada nilai non-array yang konsisten" termasuk meningkatkan kesalahan?
Jonathan Allan
" Nilai apa pun dapat digunakan sebagai indikator palsu, selain array bilangan bulat. " Apakah itu termasuk array kosong?
Shaggy
@shaggy [] adalah indikasi nilai kebenaran potensial, bukan? Apakah membiarkan aturan meta itu lebih penting daripada kebenaran dan kepalsuan yang berbeda?
Magic Octopus Mm
@ Johnathan Allan jika kesalahan itu tidak dapat dinaikkan dalam skenario Truthy - saya kira. Tapi saya merasa ini sengaja mencoba untuk meregangkan spec. Jika saya mengubah kata-kata dari indikator untuk mengembalikan nilai tidak apa-apa?
Magic Octopus Mm
Saya percaya nilai keluar yang konsisten dihitung sebagai nilai balik meskipun per meta?
Magic Gurita Guci

Jawaban:

7

Brachylog , 8 byte

h⊇.+~t?∧

Cobalah online!

Jawaban Brachylog bulanan. Kembali false.jika tidak memungkinkan.

Penjelasan

h⊇.           The output is a subset of the head of the input
  .+~t?       The sum of the elements of the output must equal the tail of the input
       ∧      (Avoid implicit unification between the output and the input)
Fatalisasi
sumber
6

Python 2 , 108 104 byte

lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]
from itertools import*

Cobalah online!

-4 byte, terima kasih kepada Jonathan Allan

Python 2 , 108 106 byte

def f(a,n):
 q=[a]
 while q:
  x=q.pop(0);q+=[x[:i]+x[i+1:]for i in range(len(x))]
  if sum(x)==n:return x

Cobalah online!

-2 byte, terima kasih kepada Janathan Frech

TFeld
sumber
1
Anda bisa menggunakan range(-len(a),1)dan -lmenyimpan 2, tetapi lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]menghemat 4.
Jonathan Allan
@JonathanAllan Terima kasih :)
TFeld
1
Kemungkinan 106 byte .
Jonathan Frech
@ JonathanFrech Terima kasih, saya pasti lelah kemarin;)
TFeld
4

Pyth , 8 byte

  • 8-byter ( Coba! ) - Hanya mengeluarkan satu solusi yang mungkin. Untuk input yang tidak dapat dipecahkan, ia tidak mencetak apa pun ke STDOUT, yang merupakan string kosong, yang secara teknis berbicara falsey dalam Pyth, tetapi menulis ke STDERR. Terima kasih kepada FryAmTheEggman untuk menyarankan ini (mengabaikan STDERR dan berfokus pada output STDOUT saja), sehingga menghemat 1 byte.

    efqz`sTy

  • 9-byter ( Coba! ) - Hanya mengeluarkan satu solusi yang mungkin, yang dibungkus dengan daftar tunggal sebagaimana diizinkan secara default (mis ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]].). Untuk input yang tidak dapat dipecahkan, ia mengembalikan [], yang merupakan kesalahan dalam Pyth.

    >1fqz`sTy

  • 10-byter ( Coba! ) - Untuk hasil yang lebih jelas, tanpa menggunakan aturan daftar tunggal dan menggunakan 0bukan []sebagai nilai falsy.

    e+0fqz`sTy

Penjelasan

Pertama, kode tersebut menghitung set daftar input (semua kemungkinan sub-koleksi yang dipesan). Kemudian, itu hanya menyimpan koleksi yang jumlahnya sama dengan nomor input. Perlu dicatat bahwa koleksi dihasilkan dari yang terpendek ke yang terpanjang, jadi kami fokus pada yang terakhir. Untuk mendapatkannya:

  • The 8-byter hanya menggunakan akhir built-in, yang melempar kesalahan, tapi STDERR dapat diabaikan sesuai aturan situs kami, output ke STDOUT menjadi string kosong, yang falsy.
  • The 9-byter mengambil elemen terakhir, tetapi menggunakan kode Python setara lst[-1:]di tempat lst[-1]untuk kesalahan menghindari dari yang dilemparkan untuk input terpecahkan.
  • The 10-byter menambahkan sebuah 0 ke daftar disaring sub-koleksi, kemudian mengambil akhir koleksi yang (elemen terakhir). Jika input tidak dapat dipecahkan, maka 0 digunakan secara alami.
Tuan Xcoder
sumber
[]apakah palsu? Rapi. Mengapa Pyth melakukan itu []?
Guci Gurita Ajaib
@MagicOctopusUrn Pyth mewarisi itu dari Python sebenarnya: Cobalah online .
Tn. Xcoder
@FryAmTheEggman tidak akan daftar kosong menjadi output yang benar dalam kasus uji f([], 0) = []?
Sok
@FryAmTheEggman Terima kasih atas saran Anda! Saya telah membuat perubahan yang diperlukan :)
Tn. Xcoder
3

Jelly , 7 byte

ŒPS⁼¥ƇṪ

Cobalah online!

Output diklarifikasi atas TIO.

Erik the Outgolfer
sumber
3

Perl 6 , 38 37 byte

{*.combinations.grep(*.sum==$_).tail}

Cobalah online!

Fungsi kari.

nwellnhof
sumber
Tunggu, apakah itu ;perlu?
Jo King
@ JoKing Itu perlu dalam iterasi sebelumnya untuk menghindari kesalahan "salah penutupan ganda". Tetapi untuk beberapa alasan itu bisa dihilangkan sekarang. (Saya pikir setelah saya diganti $^xdengan $_.)
nwellnhof
3

Brachylog , 4 byte

⟨⊇+⟩

Cobalah online!

Hampir setara dengan Fatalize h⊇.+~t?∧, kecuali jauh lebih pendek, berkat fitur komposisi predikat yang menurut riwayat edit referensi adalah pekerjaan yang sedang berlangsung hingga 8 Januari, setelah lebih dari dua bulan. ⟨⊇+⟩adalah sandwich , yang meluas ke {[I,J]∧I⊇.+J∧}, di mana kawat gigi dalam hal ini tidak relevan karena sandwich itu sendiri.

                The input
[I,J]           is a list of two elements I and J.
        .       The output,
         +J     which sums to J
           ∧    (which we don't unify with the output),
      I⊇        is a sublist of I
     ∧          (which we don't unify with [I,J]).

Transformasi yang jauh lebih dramatis dari jawaban Fatalize, yang menggunakan predikat yang sama dengan variabel yang sama tetapi keluar satu byte lebih pendek dari yang diatur secara berbeda:

Brachylog , 7 byte

h⊇.&t~+

Cobalah online!

           The input
h          's first element
 ⊇         is a superlist of
  .        the output,
   &       and the input
    t      's last item
     ~+    is the sum of the elements of
           the output.

(Juga, jika ada yang ingin melihat sesuatu yang aneh, ubah salah satu garis bawah dalam kasus uji menjadi tanda hubung.)

String yang tidak terkait
sumber
1
Sandwich diimplementasikan oleh @ ais523 pada November 2018 tetapi hanya ditarik di Brachylog pada awal Januari 2019.
Fatalize
1
Tentu saja, tidak satu pun dari penggalian sejarah ini yang penting, karena bahasa yang mengundurkan diri dari tantangan telah diizinkan selama bertahun-tahun.
pppery
2

Bersihkan , 89 byte

import StdEnv,Data.List,Data.Func
$n=find((==)n o sum)o sortBy(on(>)length)o subsequences

Cobalah online!

Menentukan fungsi yang $ :: Int -> [Int] -> (Maybe [Int])kembali Nothingjika tidak ada kombinasi elemen yang tepat, dan (Just [elements...])sebaliknya.

Suram
sumber
2

JavaScript (ES6), 108 byte

Mengambil input sebagai (array)(n). Mengembalikan array atau false.

a=>n=>a.reduce((a,x)=>[...a,...a.map(y=>1/r[(y=[...y]).push(x)]||eval(y.join`+`)-n?y:r=y)],[[]],r=!n&&[])&&r

Cobalah online!

Arnauld
sumber
2

Ini dimulai dari keren dan kecil, tetapi ujung kasus membuat saya. Apa pun yang terjadi, saya bangga dengan pekerjaan yang saya lakukan ini.

Python 3 , 169 161 154 byte

from itertools import*
def f(a,x):
	if sum(a)==x:return a
	try:return[c for i in range(len(a))for c in combinations(a,i)if sum(c)==x][-1]
	except:return 0

Cobalah online!

Gigaflop
sumber
Ingat bahwa ini adalah [kode-golf] jadi Anda harus mencoba membuat byte Anda sekecil mungkin! Anda memiliki baris baru terkemuka dan beberapa golf spasi putih sepele lainnya , dan saya bertaruh orang lain yang tahu python dapat menurunkan ini lebih jauh.
Giuseppe
@ Giuseppe Terima kasih telah mengingatkan saya pada spasi putih terkemuka. Saya menghabiskan beberapa waktu mencoba untuk mengkonsolidasikan beberapa bagian dari ini, tetapi memutuskan untuk mempostingnya sementara itu jika ada yang lain dapat menyarankan suntingan.
Gigaflop
Bukan masalah! Sudah seperti 5 tahun sejak saya melakukan Python, tetapi tidak range(x)menghasilkan (0...x-1)? Jadi Anda range(len(a))tidak memberi Anda kemungkinan membiarkan array tidak berubah?
Giuseppe
@Giuseppe Eureka, itu berhasil. Saya mungkin terlalu fokus pada materi baru yang sedang saya kerjakan.
Gigaflop
Alih-alih if a==[] and x==0digunakan if sum(a)==x. Kemudian Anda juga dapat menghapus +1dari range.
Vedant Kandoi
2

R , 100 80 byte

function(a,x){i[sum(a|1):0,j[combn(a,i,,F),if(sum(j)==x)return(j)]]
F}
`[`=`for`

Cobalah online!

20 byte disimpan berkat digEmAll

Pengembalian FALSEuntuk kriteria yang tidak mungkin.

Giuseppe
sumber
Dan 80 operator '[' yang menyalahgunakan : D
digEmAll
@digEmAll Saya tentu senang saya tidak mendapatkan kesempatan untuk mengedit jawaban 98 byte Anda :-)
Giuseppe
eheh lupa menghapusnya: D
digEmAll
1

Attache , 28 byte

${(y&`=@Sum\Radiations@x)@0}

Cobalah online!

Alternatif

34 byte :f[x,y]:=({y=Sum@_}\Radiations@x)@0

30 byte :First@${y&`=@Sum\Radiations@x}

29 byte :{(_&`=@Sum\_2)@0}#/Radiations

29 byte :${({y=Sum@_}\Radiations@x)@0}

29 byte :`@&0@${y&`=@Sum\Radiations@x}

29 byte :{_}@@${y&`=@Sum\Radiations@x}

Penjelasan

${(y&`=@Sum\Radiations@x)@0}
${                         }    function receiving two arguments, x and y
            Radiations@x        calculate the radiations of x
                                (simulates removing all possible subslices of x)
           \                    keep those radiations
        Sum                     ...whose sum...
     `=@                        ...equals...
   y&                           ...y
  (                     )@0     select the first one (always the longest)
Conor O'Brien
sumber
0

APL (NARS), 65 karakter, 130 byte

{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

↓ digunakan karena elemen pertama dari set set akan menjadi satu set kosong (di sini ⍬ Zilde), yang ingin dihilangkan karena tampaknya + / ⍬ adalah nol ...

Karena tidak menemukan, atau kesalahan itu akan mengembalikan ⍬ atau dalam teks cetak:

  o←⎕fmt
  o ⍬
┌0─┐
│ 0│
└~─┘

uji:

  z←{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

  o 1 z ,1
┌1─┐
│ 1│
└~─┘
  o 2 z ,1
┌0─┐
│ 0│
└~─┘
  o 10 z 1 2 3 4 5 6 7 8 9 10
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 2,2,2,2,2,2,2,2,2
┌5─────────┐
│ 2 2 2 2 2│
└~─────────┘
  o ¯8 z 2,2,2,2,¯2,¯2,¯2,¯4,¯2
┌7──────────────────┐
│ 2 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~──────────────────┘
  o ¯6 z ¯2,¯4,¯2
┌2─────┐
│ ¯4 ¯2│
└~─────┘
  o 0 z 2,2,2,4,2,¯2,¯2,¯2,¯4,¯2
┌10───────────────────────┐
│ 2 2 2 4 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~────────────────────────┘
  o 10 z 1 2 3 4
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 1 2 3
┌0─┐
│ 0│
└~─┘
  o 0 z ⍬
┌0─┐
│ 0│
└~─┘
  o +/⍬  
0
~
RosLuP
sumber