...terhitung!
Anda akan lulus program Anda variabel yang mewakili jumlah uang dalam dolar dan / atau sen dan berbagai nilai koin. Tantangan Anda adalah menampilkan jumlah kombinasi yang mungkin dari array nilai koin yang diberikan yang akan menambah jumlah yang diteruskan ke kode. Jika tidak mungkin dengan koin yang dinamai, program harus kembali 0
.
Catatan tentang terminologi numismatik Amerika:
- Koin 1 sen: sen
- Koin 5 sen: nikel
- Koin 10 sen: uang receh
- Koin 25 sen: seperempat (seperempat dolar)
Contoh 1:
Program disahkan:
12, [1, 5, 10]
(12 sen)
Keluaran:
4
Ada 4 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 12 sen:
- 12 sen
- 1 nikel dan 7 sen
- 2 sen dan 2 sen
- 1 sen dan 2 sen
Contoh 2:
Program disahkan:
26, [1, 5, 10, 25]
(26 sen)
Keluaran:
13
Ada 13 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 26 sen:
- 26 sen
- 21 sen dan 1 nikel
- 16 sen dan 2 sen
- 11 sen dan 3 sen
- 6 sen dan 4 sen
- 1 sen dan 5 sen
- 16 sen dan 1 sen
- 6 sen dan 2 sen
- 11 sen, 1 sen, dan 1 nikel
- 6 sen, 1 sen, dan 2 sen
- 1 sen, 1 sen, dan 3 sen
- 1 sen, 2 sen, dan 1 nikel
- 1 seperempat dan 1 sen
Contoh 3:
Program disahkan:
19, [2, 7, 12]
Keluaran:
2
Ada 2 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 19 sen:
- 1 koin 12 sen dan 1 koin 7 sen
- 1 koin 7 sen dan 6 koin 2 sen
Contoh 4:
Program disahkan:
13, [2, 8, 25]
Keluaran:
0
Tidak ada cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 13 sen.
Ini telah melalui Sandbox. Celah standar berlaku. Ini adalah kode golf, jadi jawabannya dengan byte paling sedikit menang.
s/count/earn
.Jawaban:
Jelly ( garpu ), 2 byte
Ini bergantung pada cabang Jelly di mana saya sedang mengerjakan implementasi atom pemecahan Frobenius jadi sayangnya Anda tidak dapat mencobanya secara online.
Pemakaian
Penjelasan
sumber
Haskell,
3734 byteContoh penggunaan:
26 # [1,5,10,25]
->13
.Pendekatan rekursif sederhana: coba kedua nomor berikutnya dalam daftar (asalkan jumlahnya kurang atau sama dengan jumlahnya) dan lewati saja. Jika mengurangi angka mengarah ke jumlah nol, ambil yang
1
lain (atau jika daftar elemen habis) ambil a0
. Jumlahkan1
dan0
s.Sunting: @Damien: disimpan 3 byte dengan menunjuk ke casing dasar yang lebih pendek untuk rekursi (yang juga dapat ditemukan dalam jawaban @xnors ).
sumber
1209 # [1,5,10,33,48]
->1314050
.6000 # [1,5,10,33]
->22086484
.Mathematica,
3522 byteTerima kasih kepada miles untuk menyarankan
FrobeniusSolve
dan menghemat 13 byte.Mengevaluasi fungsi yang tidak disebutkan namanya, yang menjadikan daftar koin sebagai argumen pertama dan nilai target sebagai yang kedua.
FrobeniusSolve
adalah singkatan untuk menyelesaikan persamaan Diophantine dari formuliruntuk bilangan bulat non-negatif dan memberi kami semua solusi.
xi
sumber
(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
Pyth, 8 byte
Mentah kasar, terlalu intensif memori untuk pengujian yang sebenarnya. Ini adalah O (2 mn ), di mana n adalah jumlah koin dan m adalah jumlah target. Mengambil input sebagai
target\n[c,o,i,n,s]
.sumber
Haskell, 37 byte
Menggunakan beberapa kelipatan dari koin pertama
h
mengurangi jumlah yang diperlukans
ke nilai non-negatif dalam perkembangan yang menurun[s,s-h..0]
, yang kemudian harus dilakukan dengan koin yang tersisa. Setelah tidak ada koin yang tersisa, periksa apakah jumlahnya adalah nol secara hitung0^s
.sumber
JavaScript (ES6),
5148 byteTerima koin dalam urutan apa pun. Mencoba menggunakan dan tidak menggunakan koin pertama, secara rekursif menghitung jumlah kombinasi dengan cara apa pun.
n==0
berarti kombinasi yang cocok,n<0
berarti bahwa koin melebihi jumlah sementarac==undefined
berarti tidak ada koin yang tersisa. Perhatikan bahwa fungsi ini sangat lambat dan jika Anda memiliki koin sen maka fungsi berikut ini lebih cepat (jangan melewati koin sen dalam array koin):sumber
Perl, 45 byte
Hitungan byte mencakup 44 byte kode dan
-p
bendera.Mengambil nilai koin pada baris pertama, dan jumlah yang ditargetkan pada baris kedua:
Penjelasan singkat:
sumber
Jelly ,
109 byteCobalah online!
Bagaimana?
sumber
JavaScript (ES6), 59 byte
Koin adalah input dari tertinggi ke terendah, mis
f(26,[100,25,10,5,1])
. Jika Anda memiliki satu sen, hapus dan gunakan versi yang jauh lebih cepat ini sebagai gantinya:Ini menggunakan rumus rekursif seperti @ nimi. Saya awalnya menulis ini beberapa hari yang lalu ketika tantangan masih di kotak pasir; terlihat seperti ini:
Satu-satunya perbedaan menjadi nilai default
c
(itu memiliki nilai yang ditetapkan dalam tantangan asli), dan mengubah0
dalam.reduce
fungsi1
(ini adalah dua byte lebih pendek dan bazillion kali lebih cepat daric=[100,25,10,5,1]
).Berikut adalah versi yang dimodifikasi yang menampilkan semua kombinasi, bukan jumlah kombinasi:
sumber
PHP, 327 Bytes
Cobalah
sumber
Aksioma,
6362 byte1 byte disimpan oleh @JonathanAllan
Pendekatan ini menggunakan fungsi pembangkit. Mungkin itu tidak membantu menurunkan ukuran kode. Saya pikir ini adalah pertama kalinya dalam bermain saya dengan Aksioma saya pergi sejauh mendefinisikan fungsi saya sendiri.
Pertama kali fungsi ini disebut memberikan peringatan yang menghebohkan, tetapi tetap menghasilkan hasil yang benar. Setelah itu, semuanya baik-baik saja asalkan daftarnya tidak kosong.
sumber
for
?R,
817663 byteTerima kasih kepada @rturnbull untuk bermain golf 13 byte!
Contoh (perhatikan bahwa
c(...)
Anda memberi vektor nilai ke R):Penjelasan:
u
adalah nilai yang diinginkan,v
adalah vektor nilai koin.menciptakan bingkai data dengan setiap kemungkinan kombinasi 0 hingga k koin (k tergantung pada denominasi), di mana k adalah yang terendah sehingga k kali nilai koin itu setidaknya u (nilai untuk mencapai).
Biasanya kami akan menggunakan
as.matrix
untuk mengubah itu menjadi matriks, tetapi itu banyak karakter. Alih-alih, kami mengambil transpose dari transpose (!) Yang secara otomatis memaksanya, tetapi mengambil lebih sedikit karakter.%*% v
kemudian menghitung nilai moneter dari setiap baris. Langkah terakhir adalah menghitung berapa dari nilai-nilai itu sama dengan nilai yang diinginkanu
.Perhatikan bahwa kompleksitas komputasi dan persyaratan memori ini mengerikan, tetapi hei, ini kode golf.
sumber
expand.grid
! Dan saya sukat(t())
triknya. Karena fungsi Anda hanya melibatkan satu baris kode, Anda dapat menghapus kurung kurawal, menghemat 2 byte. Anda juga dapat beralihdo.call(expand.grid,lapply(u/v,seq,from=0))
hanyaexpand.grid(lapply(u/v,seq,f=0))
, menghemat 11 byte.expand.grid
akan mengambil daftar sebagai masukan. Ini sedikit memalukan yang":"
tidak bekerja dengan baik dengan non-integer kalau tidaklapply(u/v,":",0)
akan menyelamatkan pasangan lagi.do.call(x,y)
sama denganx(y)
, jadi ini bukan tentang jenis input apa yang diterima. Jika Anda benar-benar ingin menggunakan:
, saya kira Anda bisa menggunakanlapply(u%/%v,`:`,0)
, tetapi itu adalah jumlah byte yang sama.do.call(x,y)
sama denganx(y)
" --- hanya jikay
bukan daftar, yang ada dalam kasus ini. Setuju dengan poin kedua Anda.J, 27 byte
Pemakaian
Penjelasan
sumber
TSQL, 105 byte
Ini hanya dapat menangani hingga satu dolar dengan 4 jenis koin ini. Versi ungolfed dapat menangani hingga sekitar 4 dolar, tetapi sangat lambat - pada kotak saya ini membutuhkan waktu 27 detik. Hasilnya adalah 10045 kombinasi btw
Golf:
Tidak Disatukan:
Biola
sumber
penggantian tinylisp , 66 byte
Solusi rekursif: mencoba menggunakan koin pertama dan tidak menggunakan koin pertama, lalu menambahkan hasilnya dari masing-masing. Kompleksitas waktu eksponensial dan tidak ada rekursi ekor, tetapi menghitung kasus uji dengan baik.
Tidak digabungkan (kunci untuk builtin:
d
= define,q
= quote,i
= if,l
= less-than,s
= kurangi,h
= head,t
= tail):Contoh penggunaan:
sumber
PHP, 130 byte
Fungsi rekursif 99 byte (dan 31 byte menyebutnya) yang berulang kali menghilangkan nilai koin saat ini dari target dan menyebut dirinya dengan nilai baru dan koin lainnya. Menghitung berapa kali target tepat mencapai 0. Jalankan seperti:
sumber
Racket 275 byte
Tidak Disatukan:
Pengujian:
Keluaran:
Solusi rekursif berikut memiliki beberapa kesalahan:
Tidak berfungsi dengan baik untuk:
Keluaran:
(1 1 3 3) dimungkinkan tetapi tidak ada dalam daftar solusi.
sumber
reduce
Scheme
( groups.csail.mit.edu/mac/projects/scheme ) yang akhirnya menghasilkan full-blownRacket
( racket-lang.org , stackoverflow.com/questions/3345397/… )!Jelly , 15 byte
Cobalah online! atau Verifikasi semua kasus uji.
Ini lebih merupakan latihan menulis versi efisien dalam Jelly tanpa menggunakan builtin. Ini didasarkan pada pendekatan pemrograman dinamis tipikal yang digunakan untuk menghitung jumlah cara untuk membuat perubahan
Penjelasan
sumber
Sebenarnya , 15 byte
Saran golf diterima. Cobalah online!
Tidak melakukanolf
sumber
Python, 120 byte
Bruteforce melalui semua kombinasi koin hingga nilai target (bahkan jika yang terkecil bukan 1).
sumber