Temukan cara terpendek untuk memajukan penghitung ke nomor tertentu

10

Saya punya konter. Ini adalah perangkat kecil yang terlihat seperti ini:

melawan

Layar beralih dari 0000ke 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 6070atau 7060. Juga, kenop akan berguling 9ke atas 0tanpa membawa, jadi 0990akan maju ke 0000bukan 1000atau 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 0000ke 9999, dan kembali serangkaian langkah dalam format berikut:

> 0001
C
> 0093
C12345678C12345678CCC
> 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
> 9999
012345678

Di mana Csingkatan "push the counter button" dan angka apa pun Ddari 0 hingga 9 berarti "gunakan kenop untuk memajukan semua kemunculan Doleh 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.

Joe Z.
sumber
Apa yang terjadi jika Anda memutar kenop ke depan? Apakah akan berubah 0010menjadi seperti 0020itu? Atau bisakah Anda memutar kenop ke belakang? Dan juga, apakah setiap "D" dihitung sebagai "D" jumlah kemajuan kenop (misalnya, apakah 1234567berarti memutar kenop 1 kali, lalu 2 kali, lalu 3 kali, begitu seterusnya)? Atau apakah itu hanya menandakan setiap kenop terpisah (misalnya, apakah 1234567hanya berarti memutar kenop 7 kali)?
R. Kap
Sepertinya yang di atas dan di bawah tidak berhubungan.
Leaky Nun
Kenop bahkan dapat memilih angka di bawah ini.
Leaky Nun
Memutar kenop ke depan akan maju dari 0010 ke 0020 atau 1111, tergantung pada posisi kenop yang sudah masuk. Anda memutar kenop ke belakang untuk mengatur posisinya, dan kemudian maju untuk memajukan angka.
Joe Z.
1
Serius, orang ini membutuhkan penghitungnya pada nilai yang benar !!!! SEKARANG!!!
CalculatorFeline

Jawaban:

5

Lua, 327763 langkah (optimal, 276 byte)

Versi golf:

a={[0]=""}t=tonumber for i=0,52 do A={}for k,v in pairs(a)do A[k]=v L=("%04d"):format(k)for i=1,4 do c=L:sub(i,i)d=L:gsub(c,(t(c)+1)%10)e=a[t(d)]A[d]=(not e or #e>#v)and v..c or e end b=k+1 if k<9999then e=a[b]A[b]=(not e or #e>#v)and v.."C"or e end end a=A endprint(a[(...)])

Versi contoh yang 1000diperbaiki dalam pertanyaan (hanya ditingkatkan):

0001:C
0093:CCCCCCCCCC12345678CCC
1000:0CCCCCCCCCCC2345678C23456789
     (0000>1111>1122>1199>1200>1000)
9999:012345678

Versi tidak disatukan:

a = {[0]=""}
for i=0,52 do
    A = {}
    for k,v in pairs(a) do
        A[k] = v
        L=("%04d"):format(k)
        for i=1,4 do
           c=L:sub(i,i)
           d=L:gsub(c,(tonumber(c)+1)%10)
           e=a[tonumber(d)]
           A[d] = (not e or #e > #v) and v..c or e
        end
        b=k+1
        if k < 9999 then
            e=a[b]
            A[b] = (not e or #e > #v) and v.."C" or e
        end
    end
    a=A
end
print(a[93],a[1000],a[9999])
Biarawati Bocor
sumber
1

Mathematica, skor 512710

Unprotect[StringRepeat]
StringRepeat[x_String, 0]:=""
Protect[StringRepeat]
#<>StringRepeat["C",#3-#2*1111]&[Array[ToString@#&,#,0],##]&[If[#<10^3,0,Quotient[#,1111]],#]&

Memperbaiki bug dengan StringRepeat(berperilaku salah untuk StringRepeat[x_String,0])

CalculatorFeline
sumber
Apakah perlu ada ruang StringRepeat[x_String, 0]:=""?
kucing
Tidak, tapi saya terlalu malas untuk menghapusnya. Apakah itu masalah?
CalculatorFeline
Tidak sama sekali: P Itu hanya ingin tahu saya bahwa sisa kode golf kecuali untuk satu spasi putih.
kucing
... yang adalah golfed, kan? Atau apakah Mathematica derau baris baru?
kucing
@ kucing Ini bukan kode-golf
pppery
1

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, 1dan 1111. Namun, secara teori dapat memecahkan masalah, karena menggunakan algoritma yang sama dengan Lua di atas.

Cobalah online!

=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ;@YQ

Bagaimana itu bekerja:

=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ)@YQ
                  assign_copy('Q',eval_input())
=Y.d((0k;         assign_copy('Y',dict(0=k))
V53               for N in range(0,53):
=ZY                   assign_copy('Z',Y)
FGY                   for G in num_to_range(Y):
 XZG=k@YG                 no_print(Z[G] = assign_copy('k',lookup(Y,G)))
=N%"%04d"G                assign_copy('N',format("%04d",G))
V4                        for H in range(0,4):
=b@NH                         assign_copy('b',lookup(N,H))
=di:Nb%"%d"ehibTT             assign_copy('d',base(replace(N,b,format("%d",mod10(increment(base(b,10))))),10))
 XZd.x?>l@Ydlk+kb@Yd+kb       no_print(Z[d]=try_and_catch(greater_than(Plen(lookup(Y,d)),Plen(k)) ? concat(k,b) : lookup(Y,d)), lambda:plus(k,b))
)                         <anti-indent>
=bhG                      assign_copy('b',head(G))
I<G9999                   if less_than(G,9999):
 XZb.x?>l@Yblk+k\C@Yb+k\C     no_print(Z[b]=try_and_catch(greater_than(Plen(lookup(Y,b)),Plen(k)) ? concat(k,"C") : lookup(Y,b)), lambda:plus(k,"C"))
)                         <anti-indent>
)                     <anti-indent>
=YZ                   assign('Y',Z)
)                 <anti-indent>
@YQ               print(lookup(Y,Q))
Biarawati Bocor
sumber
Hanya mencatat: The lua ada di bawah. : P Tapi ini luar biasa, kerja bagus.
Rɪᴋᴇʀ
Masih di atas bagi saya: o
Leaky Nun
Saya urutkan berdasarkan aktif, mungkin Anda memiliki suara. Tapi itu tidak masalah.
Rɪᴋᴇʀ
Oh itu di bawah untuk saya sekarang lol
Leaky Nun
1

JavaScript (ES6), 327763 langkah (optimal, 184 byte)

Pencarian Pertama Luasnya, tidak begitu pintar dan tidak begitu cepat.

t=>eval("for(k=[],s=[['0000',i='']];[u,p]=s[i++],u-t;k[v=(1+u-~0+'').slice(-4)]=k[v]||s.push([v,p+'C']))[...u].map(x=>k[v=[...u].map(y=>x-y?y:-~x%10).join``]=k[v]||s.push([v,p+x]));p")

Kurang golf

t=>{
  k=[]; // mark values already found to reduce search
  for( i=0, s=[['0000','']]; 
       [u,p]=s[i++], // u: current code, p:current steps
       u != t; // exit if target found
     )
  {
     // try all digits present in current code
     [...u].map(x=> {
       v=[...u].map(y=>x-y?y:-~x%10).join`` // apply digit x to u
       if (!k[v]) // check if value v not found already
          k[v] = s.push([v,p+x]));
     })
     v=(1+u-~0+'').slice(-4); // try operator C
     if (!k[v]) // check if value v not found already
       k[v] = s.push([v,p+'C']))
  }
  return p
}

Uji

f=t=>eval("for(k=[],s=[['0000',i='']];[u,p]=s[i++],u-t;k[v=(1+u-~0+'').slice(-4)]=k[v]||s.push([v,p+'C']))[...u].map(x=>k[v=[...u].map(y=>x-y?y:-~x%10).join``]=k[v]||s.push([v,p+x]));p")

function SingleTest()
{
  var i=S.value
  if (/^\d{4}$/.test(i)) X.value=f(i)
  else X.value='invalid input'
}  

SingleTest()

function LongTest()
{
  var i=0,v,r,t=0
  
  var step=_=>{ 
    v = ('000'+i).slice(-4);
    r = f(v);
    t+= r.length    
    V.value = v;
    R.value = r;
    T.value = t;
    ++i;
    if(i<10000) setTimeout(step, 0)
  }  
  
  step()
}
#V,#T,#S { width:5em }
#R,#X { width: 25em }
Single Test <input id=S value='0093'><button onclick="SingleTest()">-></button><input readonly id=X><hr>
Long test (0000 ... 9999) <button onclick="LongTest()">Go</button>(i mean <i>long</i>, runtime 1 hour)<br>
<input readonly id=V>
<input readonly id=R> 
Total steps:<input readonly id=T>

edc65
sumber