카운터를 특정 숫자로 이동시키는 가장 짧은 방법 찾기 6060, 당신은 단지이 증가

카운터가 있습니다. 다음과 같은 작은 장치입니다.

카운터

디스플레이가에서 0000로 바뀝니다 9999. 상단에 작은 푸시 버튼이있어 카운트가 1 씩 증가하고 오른쪽에 작은 노브가있어 카운터를 다시 0으로 재설정하는 것이 목적입니다.

이제 작은 손잡이의 특징은 뒤로 돌리면 다시 앞으로 돌리면 원하는 숫자를 늘릴 수 있다는 것입니다. 따라서 카운터 버튼이 10 번 눌러 카운터가 표시 0010되면 작은 딸깍 소리가 들릴 때까지 노브를 뒤로 돌린 다음 다시 앞으로 돌리면 바로 가십시오 0090.

그러나 노브는 숫자를 앞으로 밀 때마다 항상 같은 숫자의 모든 발생을 1 씩 증가시킵니다. 그래서 카운터 표시되면 6060, 당신은 단지이 증가 할 수 있습니다 7070하지 않도록, 6070또는 7060. 또한, 손잡이가 출시됩니다 9에의를 통해 0, 수행하지 않고 지금 0990에 진출하게됩니다 0000대신 10001100.


카운터를 특정 숫자로 설정하는 가장 효율적인 방법을 알고 싶습니다. 당신의 임무는 그렇게하는 데 필요한 가장 짧은 버튼 누름과 노브 전진을 결정하는 프로그램이나 기능을 작성하는 것입니다.

귀하의 프로그램에서 입력으로 4 자리 숫자를 취할 것 0000으로 9999, 다음과 같은 형식의 일련의 단계를 반환 :

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

어디 C를 의미하고 숫자 “카운터 버튼을 눌러” D“의 모든 발생을 사전에 노브를 사용하여 0 ~ 9 스탠드에서 D1″을.

프로그램은 가능한 모든 4 자리 숫자 조합에 대해 유효한 단계 시퀀스를 생성해야하며 10,000 개의 모든 사례에 필요한 총 단계 수로 점수가 매겨집니다. 동점 인 경우 (최적의 알고리즘을 찾은 경우) 짧은 코드가 승리합니다.



답변

Lua, 327763 단계 (최적, 276 바이트)

골프 버전 :

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

문제가되는 예제의 개선 된 버전 ( 1000향상된 개선 사항) :

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

언 골프 버전 :

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

답변

매스 매 티카, 점수 512710

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

버그 수정 StringRepeat(에 대해 잘못 작동 StringRepeat[x_String,0])


답변

Pyth, 327763 단계 (최적, 130 바이트)

온라인 컴파일러는 엄청난 작업 처리에 적합하지이기 때문에, 나는 단지 생성 그래서, 그것을 적은 작업을 준 0, 1하고 1111. 그러나 이론 상으로는 루아와 동일한 알고리즘을 사용하기 때문에 문제를 해결할 수 있습니다.

온라인으로 사용해보십시오!

=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

작동 방식 :

=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 단계 (최적, 184 바이트)

영리하고 빠르지 않은 너비 우선 검색.

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

덜 골프

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
}

테스트

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>