Ubah angka menjadi jumlah digit
Bukan jumlah berapa pun: kami membutuhkan jumlah terpendek
Bukan angka apa pun: Anda hanya dapat menggunakan angka itu
Contoh
Anda akan diberikan sebagai input integern>0
Katakan saja n=27
. Anda harus mengekspresikan 27
sebagai jumlah , hanya menggunakan digit[2,7]
, sesingkat mungkin. Anda tidak harus menggunakan semua digit dari angka yang diberikan!
Jadi 27=2+2+2+7+7+7
. Kami kemudian mengambil digit tersebut dan menghitungnya : [2,2,2,7,7,7]
.
Jawaban akhir untuk n=27
is6
Satu contoh lagi untuk n=195
mendapatkan jumlah terpendek kita harus menggunakan digit berikut:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
dan jawabannya adalah23
Tantangan
Diberikan bilangan bulat n>0
, output jumlah minimum digit (terkandung dalam nomor) yang meringkas hingga nomor ini
Uji Kasus
Input->Output
1->1
2->1
10->10
58->8
874->110
1259->142
12347->1765
123456->20576
3456789->384088
Ini adalah kode-golf. Jawaban terpendek dalam byte menang!
Jawaban:
Sekam , 12 byte
Menangani angka dua digit dengan cukup cepat. Cobalah online!
Penjelasan
sumber
Pyth , 12 byte
Cobalah online!
Sayangnya kesalahan memori pada input sebesar
58
.Penjelasan
sumber
./
lef<.{TjQ;./
(filter - subset yang tepat - dari digit input)Mathematica, 78 byte
menemukan test case terakhir dalam 5 detik
sumber
Length@IntegerPartitions[#, All, Sort@DeleteCases[0]@IntegerDigits@#, 1][[1]] &
R , 78 byte
Cobalah online! (versi golf)
Algoritma brute force murni, jadi itu tidak benar-benar menyelesaikan semua kasus uji, dan saya pikir itu mencoba mengalokasikan 40.000 GB untuk kasus uji terakhir ...
T
di R default untuk1
jadi kami mendapatkan kesalahan off-by-one yang kami perbaiki pada langkah kembali, tetapi kami juga mendapatkanF
default0
mana yang terbayar.Penjelasan tanpa ombak:
Cobalah online! (versi kurang golf)
sumber
Python 2,
168155144 byteIni bukan terpendek itu bisa, tapi sebaiknya-pertama dan tidak nyata buruk, runtime bijaksana.
Thefilter(None...
adalah untuk menghapus 0 sebagai digit, yang saya pelajari saya bisa melakukan sementara membuat ini.Masalah terbesar adalah bingkai python stack, yang secara realistis tidak memungkinkan saya untuk menjalankan ini pada input terbesar. Jadi, ini bukan solusi yang valid, sungguh, saya bermain-main dengan meningkatkan batas rekursi yang hanya menyebabkan seg-kesalahan. Ini harus dilakukan dengan loop dan stack atau dengan kecerdasan lebih banyak untuk bekerja dengan python.
sunting: Terima kasih kepada caird dan Chas Brown selama 13 byte!
sumber
input
dan meminta input untuk dikelilingi dengan tanda kutip.filter(None,sorted(map(int,set(n)))[::-1])
dengansorted(set(map(int,n))-{0})[::-1]
(meskipunNone
hal ini cukup bagus untuk diketahui).filter(len,...)
daftar dan string danfilter(abs,...)
untuk integer dan float.Sekam , 13 byte
Cukup tidak efisien
Cobalah online!
sumber
JavaScript (ES6), 82 byte
Mengambil input sebagai string.
sumber
1/0
?f=
awalnya adalah petunjuk besar, karena Anda tidak membutuhkannya untuk lambda non-rekursif .Ruby , 70 byte
Sangat lambat, coba semua kombinasi yang mungkin, tambah ukurannya hingga kita menemukan solusi.
Terima kasih Dennis untuk Ruby 2.4 di TIO.
Cobalah online!
sumber
Jelly , 23 byte
Cobalah online!
Ini sangat tidak efisien, sehingga tidak berjalan untuk kasus uji setelah yang ketiga di TIO karena batas waktu> _ <
Segala kiat bermain golf dipersilakan!
sumber
Python 2 ,
183176172166161 byteCobalah online!
Lebih lama dari jawaban Python yang lain, tetapi melakukan semua test case digabung plus
987654321
di bawah satu detik pada TIO.Mengambil keuntungan dari kenyataan bahwa jika
d1<d2
angka, maka perlu paling banyakd2-1
d1
jumlahnya (karenad2
contohd1
dapat diganti dengand1
contohd2
untuk jumlah yang lebih pendek). Jadi, mengurutkan digit dalam urutan menaik, ada "hanya"9! = 362880
jumlah yang paling mungkin untuk dipertimbangkan; dan kedalaman rekursi maksimum9
(terlepas dari nilain
).sumber
Haskell , 91 byte
Cobalah online! Contoh penggunaan:
f 58
hasil8
. Cepat untuk angka dua digit, sangat lambat untuk input yang lebih besar.Fungsi
f
mengubah nomor inputn
menjadi daftar digit saat memfilter angka nol. Kemudian daftar ini dann
dirinya sendiri diserahkan ke(#)
fungsi, yang mengembalikan daftar tunggal.!!0
mengembalikan elemen daftar tunggal ini.(#)
menggunakan daftar tunggal dan kosong sebagai jenis opsi. Diberikan masukan darin=58
dans=[5,8]
, idenya adalah untuk mengurangi semua digits
darin
, kemudian menerapkan secara rekursif(#)
dan memeriksa digit mana yang menghasilkan jumlah langkah minimum dan mengembalikan satu ditambah hasil minimum ini sebagai hasilnya. Bagian pertama dihitung dengan(s#).(n-)=<<s
, yang sama denganconcat(map(s#)(map(n-)s))
. Jadi, dalam contoh kita pertama[58-5,58-8]
dihitung, diikuti oleh[[5,8]#53,[5,8]#50]
yang menghasilkan[[7],[7]]
atau[7,7]
setelahconcat
. Hasilnya dicocokkan pada polax:m
untuk memastikan daftar memiliki setidaknya satu elemen (minimum
gagal jika tidak), maka daftar singleton 1 ditambah minimum hasil dikembalikan. Jikan
lebih kecil nol atau panggilan rekursif mengembalikan daftar kosong, kami berada di cabang pencarian yang gagal dan daftar kosong dikembalikan. Jikan==0
cabang berhasil dan[0]
dikembalikan.Haskell , 101 byte
Cobalah online! Pendekatan yang jauh lebih efisien, memeriksa semua kasus uji dalam waktu kurang dari satu detik.
Kali ini, daftar digit input dihitung dalam urutan menurun, yang memungkinkan
(#)
untuk mencoba menggunakan digit terbesar sesering mungkin, lalu terbesar kedua, dan seterusnya hingga solusi ditemukan. Solusi pertama yang ditemukan dengan cara ini juga dijamin sebagai yang terkecil.sumber