10
2
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 9
s 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
into0020
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, does1234567
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, does1234567
just mean turn the knob 7 times)? – R. Kap – 2016-04-02T03:16:31.217Looks like the above and the below are unrelated. – Leaky Nun – 2016-04-02T03:17:00.727
The knob can even choose digits in the below. – Leaky Nun – 2016-04-02T03:18:19.587
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. – 2016-04-02T03:58:39.123
each D signifies a separate advancement of the digits, so
1234567
signifies turning the knob 7 units. – Joe Z. – 2016-04-02T04:01:20.0631Seriously, this guy needs his counter at the correct value!!!! NOW!!! – CalculatorFeline – 2016-04-02T14:31:42.913
@edc65
0093:C12345678C12345678CCC
. AfterC12345678
:0009
. After anotherC
:0010
. After another12345678
:0090
. Then afterCCC
:0093
. – Leaky Nun – 2016-04-02T15:29:17.823