Jumlah minimum jumlah untuk dijumlahkan dengan tepat n

15

Pertanyaan pertama di sini, jangan meneriaki saya apakah ini duplikat atau tantangan yang buruk.

pengantar

Saya memikirkan tantangan ini sendiri, dan itu tampaknya menjadi teka-teki dasar yang bagus untuk pegolf kode pemula. Ini juga dapat membantu saya memutuskan bahasa golf kode mana yang akan saya pelajari.

Tantangan

Diberikan array bilangan bulat yang kurang dari atau sama dengan n, menghasilkan atau mengembalikan jumlah angka minimum dari array yang dijumlahkan dengan tepat n.

Anda dapat memilih untuk menulis fungsi atau program lengkap.

Memasukkan

Anda bisa berasumsi dengan aman 0 <= n < 2^31.

Ambil array atau daftar apa pun ( vectoruntuk C ++ atau Java LinkedListdiizinkan), beserta nparameter opsional length, yang menentukan panjang array.

Anda juga dapat mengambil input sebagai string yang dipisahkan spasi, dipisahkan noleh koma atau spasi:

1 5 7 3 7 3 6 3 2 6 3,10

1 5 7 3 7 3 6 3 2 6 3 10

jika lebih mudah.

Keluaran

Keluaran, atau kembalikan jumlah angka minimum dari array yang jumlahnya tepat n. Menggunakan contoh di atas:

1 5 7 3 7 3 6 3 2 6 3,10

Program Anda harus mencetak:

2

karena jumlah minimum angka yang dijumlahkan 10adalah 2( 7dan 3).

Dalam hal tidak ada solusi, cetak atau kembalikan negatif,, 0"Tidak ada solusi" (meskipun itu tidak akan pintar), (seperti yang disarankan), atau nilai palsu lainnya, dengan pengecualian string kosong.

Contoh Input dan Output

Memasukkan:

1 5 7 3 7 3 6 3 2 6 3,10
143 1623 1646 16336 1624 983 122,18102
5 6 9,12

Keluaran:

2
3
-1

Mencetak gol

Ini adalah kode-golf, jadi kode terpendek dalam byte menang.

Jawaban teratas akan diterima pada Natal.

Cangkir Kopi
sumber
Saya telah mengedit spesifikasi Anda, karena kami biasanya mengizinkan metode I / O yang sama untuk fungsi dan program; lihat konsensus di sini . Jangan ragu untuk mundur jika Anda tidak setuju.
lirtosiast
Bolehkah kami membuat kasing falseuntuk kasus tanpa solusi?
ETHproduk
@ ETHproductions Tentu, akan menambahkan itu.
TheCoffeeCup
Apakah Anda mempertimbangkan output falsey kosong, karena string kosong adalah falsey di Pyth?
lirtosiast
@ThomasKwa Saya tidak suka output string kosong, tetapi Anda dapat memasukkan itu sebagai "jika x diizinkan ..." dalam jawaban Anda ...
TheCoffeeCup

Jawaban:

7

Pyth, 12 11 byte

lhafqsTQyEY

Ini diambil nsebagai baris input pertama dan daftar pada baris kedua.

lhafqsTQyEY     (Implicit: Q = 1st line of input; E = 2nd line)
         E      The list
        yE      Powerset (sorted by increasing length; empty set first)
   f            Filter by lambda T:
     sT         sum(T)
    q                  ==
       Q                  Q
   fqSTQyE      Sublists that sum to Q, sorted by increasing length
  a       Y     append an empty array (in case none match)
lh              take the length of the first element (0 for empty array)

Coba di sini .

lirtosiast
sumber
1
Kode dan penjelasan Anda tidak cocok.
isaacg
@isaacg Sekarang diperbaiki.
lirtosiast
5

Japt , 30 21 18 byte

Ternyata ada metode yang jauh lebih efisien. ;)

Uà f_x ¥V} ml n- g

Uji secara online! (Catatan: n-telah diubah menjadi n@X-Y}karena alasan kompatibilitas)

Ini mengambil input sebagai array yang dipisahkan oleh spasi atau koma, diikuti oleh angka. Output undefineduntuk kasus uji tanpa solusi.

Uà f_  x ¥ V} ®   l} n- g
UàfmZ{Zx ==V} mZ{Zl} n- g

            // Implicit: U = input array, V = input integer
Uà fZ{   }  // Generate all possible combinations of U, then filter to only items Z where
Zx ==V      //   the sum of Z is equal to V.
mZ{Zl}      // Map each remaining combination to its length.
n-          // Sort by subtraction; smaller items end up in the front.
g           // Take the first item.
            // Implicit: output last expression

Saya tidak percaya saya tidak memikirkan versi ini ketika saya awalnya menulis ini ...

Beberapa optimasi telah dilakukan sejak saat itu yang berguna di sini:

  • A Upada awal program biasanya dapat ditinggalkan.
  • Ãadalah jalan pintas untuk .
  • n sekarang mengurutkan angka dengan benar secara default.

Masing-masing membutuhkan satu byte, dengan total 15:

à f_x ¥VÃml n g

Uji secara online!

Produksi ETH
sumber
Itu 25 byte, bukan 21.
Albert Renshaw
1
@AlbertRenshaw Japt mendukung pengkodean IEC_8859-1 , di mana masing-masing karakter ini adalah 1 byte. Anda dapat menyimpan program ini sebagai file teks yang disandikan IEC_8859-1, lalu mengunggahnya ke penerjemah online .
ETHproduksi
Ah bagus! Terima kasih telah memberi tahu saya
Albert Renshaw
1

Mathematica, 73 65 byte

Min[Length/@Select[IntegerPartitions[#2,#2,#],Sort@#==Union@#&]]&

Fungsi murni, kembali jika tidak ada solusi.

LegionMammal978
sumber
1

Python 3, 128 byte

Ini tidak golf seperti yang saya inginkan, tapi saya akan mengerjakannya nanti.

from itertools import*
def s(a,n):
 for i in range(len(a)):
  for j in permutations(a,i+1):
   if sum(j)==n:return i+1
 return 0
Sherlock9
sumber
1

Mathematica, 45 byte

Min@Cases[Subsets@#,i_/;Tr@i==12:>Length@#2]&
alephalpha
sumber
1

CJam, 34 byte

0q~_,2,m*\f.*{:+1$=},\;0f-{,}$0=,+

Cobalah online . Format input adalah jumlah yang diikuti oleh daftar nilai, misalnya:

18102 [143 1623 1646 16336 1624 983 122]

Perhatikan bahwa ini akan menimbulkan pengecualian jika tidak ada solusi yang ditemukan. Pengecualian pergi ke stderr ketika CJam dijalankan dari baris perintah, dan hasil yang benar ( 0) masih dicetak ke stdout. Jadi ini memenuhi konsensus yang ditetapkan di Haruskah pengajuan diizinkan untuk keluar dengan kesalahan?

Kode mungkin terlihat lebih panjang dari yang Anda harapkan. Alasan utama adalah bahwa CJam tidak memiliki built-in untuk menghasilkan kombinasi. Atau setidaknya itu alasan saya, dan saya berpegang teguh pada itu.

Penjelasan:

0       Push 0 result for exception case.
q~      Get and interpret input.
_,      Copy and get length of input value list.
2,      Push [0 1].
m*      Cartesian power. This generates all possible lists of 0/1 values with the
        same length as the input value list.
\       Swap input value list to top.
f.*     Apply element-wise product of input value list with all 0/1 lists.
        We now have all combinations of values, with 0 in place of unused values.
{       Start filter block.
  :+      Sum values.
  1$      Copy target sum to top.
  =       Compare.
},      Filter.
\;      Swap target sum to top and discard.
0f-     Remove 0 values. We now have all solution lists.
{,}$    Sort by length.
0=      Get first solution, which after sorting is the shortest.
        This will raise an exception if the list of solutions is empty, bailing
        out with the initial 0 on the stack.
,       Get length of solution.
+       Add the 0 we initially pushed for the exception case.
Reto Koradi
sumber
1

JavaScript (ES6), 84 byte

f=(a,n,m=1e999,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0)&&m

Penjelasan

Mengambil Arraydari Numbers dan Numbersebagai argumen. Mengembalikan sejumlah Infinityjika tidak ada hasil. Ini adalah fungsi rekursif yang mengurangi ndan menghapus setiap elemen dari array satu per satu hingga n == 0.

f=(a,n,m=1e999,x)=> // m and x are not passed, they are here to declare them in the local
                    //     scope instead of globally, initialise m to Infinity
  n&&               // if n == 0, return 0
  a.map((v,i)=>     // iterate over each number in a
    (x=[...a],      // x = copy of a
    x.splice(i,1),  // remove the added number from the array
    x=f(x,n-v)+1)   // x = result for the numbers in this array
      <m?m=x:0      // set m to minimum result
  )
  &&m               // return m

Uji

Tes ini set muntuk Infinitykemudian bukan sebagai argumen default untuk membuatnya bekerja di Chrome (bukan hanya Firefox).

pengguna81655
sumber
1

Haskell, 72 byte

import Data.List
n#l=head$sort[length x|x<-subsequences l,sum x==n]++[0]

Kembali 0jika tidak ada solusi.

Contoh penggunaan: 10 # [1,5,7,3,7,3,6,3,2,6,3]->2 .

Temukan semua sub-daftar dari daftar input lyang memiliki jumlah n. Ambil panjang masing-masing sub-daftar tersebut dan urutkan. Tambahkan 0dan ambil elemen pertama.

Jika daftar tunggal diperbolehkan untuk output, misalnya [2], kita bisa menghemat 7 bytes: n#l=minimum[length x|x<-subsequences l,sum x==n]. Jika tidak ada solusi, daftar kosong []dikembalikan.

nimi
sumber