# 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:

> 0001
C
> 0093
C12345678C12345678CCC
> 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
> 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.

• What happens if you turn the knob forward? Will it turn 0010 into 0020 in that case? Or can you only turn the knob backwards? And also, does each "D" count as "D" number of advancements of the knob (for instance, does 1234567 mean turn the knob 1 time, then 2 times, then 3 times, so on so forth)? Or does it just signify each separate knob turn (for instance, does 1234567 just mean turn the knob 7 times)? – R. Kap Apr 2 '16 at 3:16
• Looks like the above and the below are unrelated. – Leaky Nun Apr 2 '16 at 3:17
• The knob can even choose digits in the below. – Leaky Nun Apr 2 '16 at 3:18
• Turning the knob forward will either advance 0010 to 0020 or 1111, depending on the position the knob is already in. You turn the knob backwards to set its position, and then forward to advance the digits. – Joe Z. Apr 2 '16 at 3:58
• Seriously, this guy needs his counter at the correct value!!!! NOW!!! – CalculatorFeline Apr 2 '16 at 14:31

# Lua, 327763 steps (optimum, 276 bytes)

Golfed version:

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


Improved version of the examples in question (only 1000 is improved):

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


Ungolfed version:

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, score 512710

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


Fixes a bug with StringRepeat (behaves incorrectly for StringRepeat[x_String,0])

• Does there need to be a space in StringRepeat[x_String, 0]:=""? – cat Apr 2 '16 at 18:34
• Nope, but I was too lazy to remove it. Is that a problem? – CalculatorFeline Apr 2 '16 at 18:59
• Not at all :P It was just curious to me that the rest of the code is golfed except for one whitespace. – cat Apr 2 '16 at 19:01
• ... that is golfed, right? Or is Mathematica the new line noise? – cat Apr 2 '16 at 19:01
• @cat This isn't code-golf – pppery Jan 7 at 0:08

# Pyth, 327763 steps (optimum, 130 bytes)

Since the online compiler is inept at dealing with such enormous task, I have given it less work, so that it only generates 0, 1, and 1111. However, it can theoretically solve the problem, because it uses the same algorithm as the Lua at the top.

Try it 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


How it works:

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

• Just noting: The lua one is below. :P But this is amazing, good work. – Rɪᴋᴇʀ Apr 2 '16 at 15:22
• Is still above for me :o – Leaky Nun Apr 2 '16 at 15:24
• I sort by active, maybe you have votes. But it doesn't really matter. – Rɪᴋᴇʀ Apr 2 '16 at 15:25
• Oh it's below for me now lol – Leaky Nun Apr 2 '16 at 15:25

# JavaScript (ES6), 327763 steps (optimum, 184 bytes)

A Breadth First Search, not so smart and not so fast.

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


Less golfed

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
k[v] = s.push([v,p+x]));
})
v=(1+u-~0+'').slice(-4); // try operator C
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>
Total steps:<input readonly id=T>