Find the shortest way to advance a counter to a certain number I have a counter. It's a small device that looks like this: 



The display goes from 0000 to 9999. It has a little push-button at the top that increases the count by 1, and a little knob at the right whose purpose is to reset the counter back to 0.

Now, the thing about the little knob is that if you turn it backwards, you can make it increase any digit that you want once you turn it forwards again. So if I push the counter button 10 times so that the counter shows 0010, I can then turn the knob backwards until i hear a tiny click, then turn it forwards again and make it go straight to 0090.

But, the knob will always increase all occurrences of the same digit by 1 every time it pushes numbers forward. So if the counter shows 6060, you can only make it increase to 7070, not to 6070 or 7060. Also, the knob will roll 9s over to 0 without carrying, so 0990 will advance to 0000 instead of 1000 or 1100.



I want to know the most efficient way to set the counter to a certain number. Your task is to write a program or function that will determine the shortest sequence of button pushes and knob advancements required to do so.

Your program will take as input a 4-digit number from 0000 to 9999, and return a series of steps in the following format:

&gt; 0001
C
&gt; 0093
C12345678C12345678CCC
&gt; 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
&gt; 9999
012345678


Where C stands for "push the counter button" and any digit D from 0 to 9 stands for "use the knob to advance all occurrences of D by 1".

Your program must produce a valid sequence of steps for all possible four-digit combinations, and will be scored by the total number of steps required for all 10,000 cases. In the case of a tie (most likely when the optimal algorithm is found), the shorter code will win.
Lua, 327763 steps (optimum, 276 bytes)
Golfed version:
a={[0]=&quot;&quot;}t=tonumber for i=0,52 do A={}for k,v in pairs(a)do A[k]=v L=(&quot;%04d&quot;):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&gt;#v)and v..c or e end b=k+1 if k&lt;9999then e=a[b]A[b]=(not e or #e&gt;#v)and v..&quot;C&quot;or e end end a=A endprint(a[(...)])

Improved version of the examples in question (only 1000 is improved):
0001:C
0093:CCCCCCCCCC12345678CCC
1000:0CCCCCCCCCCC2345678C23456789
     (0000&gt;1111&gt;1122&gt;1199&gt;1200&gt;1000)
9999:012345678

Ungolfed version:
a = {[0]=&quot;&quot;}
for i=0,52 do
    A = {}
    for k,v in pairs(a) do
        A[k] = v
        L=(&quot;%04d&quot;):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 &gt; #v) and v..c or e
        end
        b=k+1
        if k &lt; 9999 then
            e=a[b]
            A[b] = (not e or #e &gt; #v) and v..&quot;C&quot; or e
        end
    end
    a=A
end
print(a[93],a[1000],a[9999])