Minimum steps to set a series of rotating dials to

问题:

So I have the following problem: There are n rotating dials each set to some number between 0-9 and they need to be matched with another series of n numbers(also between 0-9).

One step of rotation is rotating any number of consecutive dials up or down by one step. The dials wrap around 9. i.e. rotating one step up from 9 gives 0 and vice versa.

I need to find the minimum number of steps to match the initial configuration with the given configuration.

Ex: Initial -> 154 Given -> 562

1. first move first 2 dials up by 1 154 -> 264->1 step
2. move 1st dial 3 up 264->564 ->3 steps
3. move 3rd dial 2 down 564->562 ->2 steps
So min steps is 6.
I don't need the code, only some insights to the approach.

回答1:

I'm not sure if I understand correctly the problem. It seems that if you rotate two numbers together 1 step, that move is counted only as one move, not two, correct?

In that case why not count the minimum distance between every number and its match in the other series. After that group together minus moves and plus moves, and move the numbers together where possible.

Ex:

145 -> 632

• 1 has min distance 5+- (up or down)
• 4 has min distance 1-
• 5 has min distance 3-

Since there only are minus moves, I would count the 5 also as a minus move, and do following:

1. move all numbers down one step -> 034
2. move first and last number down two steps -> 832
3. move last number down two steps -> 632 = total 5 steps