I have a counter. It's a small device that looks like this:
The display goes from
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
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
7060. Also, the knob will roll
9s over to
0 without carrying, so
0990 will advance to
0000 instead of
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
9999, and return a series of steps in the following format:
> 0001 C > 0093 C12345678C12345678CCC > 1000 C12345678C12345678C12345678C12345678C12345678C12345678C12345678C > 9999 012345678
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.