Saya punya konter. Ini adalah perangkat kecil yang terlihat seperti ini:
Layar beralih dari 0000
ke 9999
. Ini memiliki tombol kecil di bagian atas yang meningkatkan hitungan oleh 1, dan tombol kecil di sebelah kanan yang tujuannya adalah untuk mengatur ulang penghitung kembali ke 0.
Sekarang, hal tentang tombol kecil adalah bahwa jika Anda memutarnya ke belakang, Anda dapat membuatnya menambah angka apa pun yang Anda inginkan setelah Anda memutarnya lagi. Jadi jika saya menekan tombol penghitung 10 kali sehingga penghitung itu muncul 0010
, saya kemudian dapat memutar kenop ke belakang sampai saya mendengar bunyi klik kecil, lalu putar ke depan lagi dan membuatnya lurus 0090
.
Namun, kenop akan selalu meningkatkan semua kemunculan angka yang sama sebanyak 1 setiap kali mendorong angka ke depan. Jadi, jika penghitung muncul 6060
, Anda hanya dapat membuatnya bertambah menjadi 7070
, bukan ke 6070
atau 7060
. Juga, kenop akan berguling 9
ke atas 0
tanpa membawa, jadi 0990
akan maju ke 0000
bukan 1000
atau 1100
.
Saya ingin tahu cara paling efisien untuk mengatur penghitung ke nomor tertentu. Tugas Anda adalah menulis program atau fungsi yang akan menentukan urutan terpendek dari penekanan tombol dan kemajuan tombol yang diperlukan untuk melakukannya.
Program Anda akan mengambil sebagai masukan angka 4 digit dari 0000
ke 9999
, dan kembali serangkaian langkah dalam format berikut:
> 0001
C
> 0093
C12345678C12345678CCC
> 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
> 9999
012345678
Di mana C
singkatan "push the counter button" dan angka apa pun D
dari 0 hingga 9 berarti "gunakan kenop untuk memajukan semua kemunculan D
oleh 1".
Program Anda harus menghasilkan urutan langkah yang valid untuk semua kemungkinan kombinasi empat digit, dan akan dinilai dengan jumlah langkah yang diperlukan untuk semua 10.000 kasing. Dalam kasus seri (kemungkinan besar ketika algoritma optimal ditemukan), kode yang lebih pendek akan menang.
sumber
0010
menjadi seperti0020
itu? Atau bisakah Anda memutar kenop ke belakang? Dan juga, apakah setiap "D" dihitung sebagai "D" jumlah kemajuan kenop (misalnya, apakah1234567
berarti memutar kenop 1 kali, lalu 2 kali, lalu 3 kali, begitu seterusnya)? Atau apakah itu hanya menandakan setiap kenop terpisah (misalnya, apakah1234567
hanya berarti memutar kenop 7 kali)?Jawaban:
Lua, 327763 langkah (optimal, 276 byte)
Versi golf:
Versi contoh yang
1000
diperbaiki dalam pertanyaan (hanya ditingkatkan):Versi tidak disatukan:
sumber
Mathematica, skor 512710
Memperbaiki bug dengan
StringRepeat
(berperilaku salah untukStringRepeat[x_String,0]
)sumber
StringRepeat[x_String, 0]:=""
?Pyth, 327763 langkah (optimal, 130 byte)
Karena compiler online adalah tidak kompeten di berurusan dengan tugas yang sangat besar seperti itu, aku telah memberikan sedikit pekerjaan, sehingga hanya menghasilkan
0
,1
dan1111
. Namun, secara teori dapat memecahkan masalah, karena menggunakan algoritma yang sama dengan Lua di atas.Cobalah online!
Bagaimana itu bekerja:
sumber
JavaScript (ES6), 327763 langkah (optimal, 184 byte)
Pencarian Pertama Luasnya, tidak begitu pintar dan tidak begitu cepat.
Kurang golf
Uji
sumber