Mam licznik. To małe urządzenie, które wygląda tak:

Wyświetlacz przechodzi od 0000do 9999. Ma mały przycisk u góry, który zwiększa liczbę o 1, i małe pokrętło po prawej stronie, którego celem jest zresetowanie licznika z powrotem do 0.

Rzecz w tym małym pokrętle polega na tym, że jeśli przekręcisz go do tyłu, możesz zwiększyć dowolną cyfrę, gdy ponownie przekręcisz do przodu. Więc jeśli naciśniesz przycisk licznika 10 razy, aby wyświetlał się licznik 0010, mogę następnie przekręcić pokrętło do tyłu, aż usłyszę małe kliknięcie, a następnie przekręcić je ponownie do przodu i sprawić, aby od razu jechało 0090.

Ale pokrętło zawsze zwiększa wszystkie wystąpienia tej samej cyfry o 1 za każdym razem, gdy popycha liczby do przodu. Więc jeśli licznik pokazuje 6060, możesz tylko zwiększyć go do 7070, a nie do 6070lub 7060. Ponadto pokrętło przewróci 9się do położenia 0bez przenoszenia, więc 0990przejdzie do 0000zamiast 1000lub 1100.

Chcę poznać najbardziej efektywny sposób ustawienia licznika na określoną liczbę. Twoim zadaniem jest napisanie programu lub funkcji, która określi najkrótszą sekwencję naciśnięć przycisków i postępów pokrętła wymaganych do tego.

Twój program pobierze jako 4-cyfrową liczbę od 0000do 9999i zwróci serię kroków w następującym formacie:

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

Gdzie Coznacza „naciśnij przycisk licznika” i dowolna cyfra Dod 0 do 9 oznacza „użyj pokrętła, aby przesunąć wszystkie wystąpienia o D1”.

Twój program musi wygenerować prawidłową sekwencję kroków dla wszystkich możliwych kombinacji czterocyfrowych i zostanie oceniony przez całkowitą liczbę kroków wymaganych dla wszystkich 10 000 przypadków. W przypadku remisu (najprawdopodobniej po znalezieniu optymalnego algorytmu) wygrywa krótszy kod.

Lua, 327763 kroki (optymalne, 276 bajtów)

Wersja golfowa:

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[(...)])

Ulepszona wersja omawianych przykładów (tylko 1000ulepszona):

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

Wersja bez golfa:

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])

Mathematica, wynik 512710

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

Naprawia błąd z StringRepeat(zachowuje się niepoprawnie dla StringRepeat[x_String,0])

Pyth, 327763 kroki (optymalne, 130 bajtów)

Ponieważ kompilator online jest nieudolna w kontaktach z tak ogromnym zadaniem, dałem mu mniej pracy, tak, że tylko generuje 0, 1oraz 1111. Jednak teoretycznie może rozwiązać problem, ponieważ używa tego samego algorytmu, co Lua u góry.

Wypróbuj 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

Jak to działa:

=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))

JavaScript (ES6), 327763 kroki (optymalne, 184 bajty)

Szerokie pierwsze wyszukiwanie, nie tak mądre i nie tak szybkie.

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")

Mniej golfa

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
}

Test

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>