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
> 0093
> 1000
> 9999

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.

  • \$\begingroup\$ 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)? \$\endgroup\$
    – R. Kap
    Apr 2, 2016 at 3:16
  • \$\begingroup\$ Looks like the above and the below are unrelated. \$\endgroup\$
    – Leaky Nun
    Apr 2, 2016 at 3:17
  • \$\begingroup\$ The knob can even choose digits in the below. \$\endgroup\$
    – Leaky Nun
    Apr 2, 2016 at 3:18
  • \$\begingroup\$ 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. \$\endgroup\$
    – Joe Z.
    Apr 2, 2016 at 3:58
  • 1
    \$\begingroup\$ Seriously, this guy needs his counter at the correct value!!!! NOW!!! \$\endgroup\$ Apr 2, 2016 at 14:31

4 Answers 4


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


Ungolfed version:

a = {[0]=""}
for i=0,52 do
    A = {}
    for k,v in pairs(a) do
        A[k] = v
        for i=1,4 do
           A[d] = (not e or #e > #v) and v..c or e
        if k < 9999 then
            A[b] = (not e or #e > #v) and v.."C" or e

Mathematica, score 512710

StringRepeat[x_String, 0]:=""

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

  • \$\begingroup\$ Does there need to be a space in StringRepeat[x_String, 0]:=""? \$\endgroup\$
    – cat
    Apr 2, 2016 at 18:34
  • \$\begingroup\$ Nope, but I was too lazy to remove it. Is that a problem? \$\endgroup\$ Apr 2, 2016 at 18:59
  • \$\begingroup\$ Not at all :P It was just curious to me that the rest of the code is golfed except for one whitespace. \$\endgroup\$
    – cat
    Apr 2, 2016 at 19:01
  • \$\begingroup\$ ... that is golfed, right? Or is Mathematica the new line noise? \$\endgroup\$
    – cat
    Apr 2, 2016 at 19:01
  • \$\begingroup\$ @cat This isn't code-golf \$\endgroup\$ Jan 7, 2020 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
=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))
  • \$\begingroup\$ Just noting: The lua one is below. :P But this is amazing, good work. \$\endgroup\$
    – Riker
    Apr 2, 2016 at 15:22
  • \$\begingroup\$ Is still above for me :o \$\endgroup\$
    – Leaky Nun
    Apr 2, 2016 at 15:24
  • \$\begingroup\$ I sort by active, maybe you have votes. But it doesn't really matter. \$\endgroup\$
    – Riker
    Apr 2, 2016 at 15:25
  • \$\begingroup\$ Oh it's below for me now lol \$\endgroup\$
    – Leaky Nun
    Apr 2, 2016 at 15:25

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

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


Less golfed

  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



function SingleTest()
  var i=S.value
  if (/^\d{4}$/.test(i)) X.value=f(i)
  else X.value='invalid input'


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;
    if(i<10000) setTimeout(step, 0)
#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>


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.