Find the shortest way to advance a counter to a certain number
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])