Open the lock with the least number of moves

Question

Consider a lock made from a system of wheels. Each wheel has 26 letters of the alphabet in order, and each wheel is initialized with 'a' . If you move one wheel up, the display for that wheel will move to the next letter of the alphabet; On the other hand, moving the wheel down switches the display to the previous letter of the alphabet. For instance:

 ['a'] -> UP -> ['b'] ['b'] -> DOWN -> ['a'] ... ['z'] -> UP -> ['a'] ['a'] -> DOWN -> ['z'] 

You can move any adjacent subsequence of wheels in one direction with just a click. This has the same effect as moving all the wheels of a subsequence in one motion. For example, if the target line is 'zzzzzzzzz' , a single move that changes 'a' to 'z' will change the entire sequence of wheels from 'a' to 'z' , thus reaching the target line - it will open the lock.

How to determine the least number of moves to open a lock? Is there a dynamic solution to this problem? The algorithm should give the following results:

  Target string | # moves ______________________________ __________ 1 | abcxyz | 5 2 | abcdefghijklmnopqrstuvwxyz | 25 3 | aaaaaaaaa | 0 4 | zzzzzzzzz | 1 5 | zzzzbzzzz | 3 

Case 1, target abcxyz :

 aaa[aaa] -> DOWN -> aaazzz aaa[zz]z -> DOWN -> aaayyz aaa[y]yz -> DOWN -> aaaxyz a[aa]xyz -> UP -> abbxyz ab[b]xyz -> UP -> abcxyz 

Case 5, the goal of zzzzbzzzz :

 [aaaaaaaaa] -> DOWN -> zzzzzzzzz zzzz[z]zzzz -> UP -> zzzzazzzz zzzz[a]zzzz -> UP -> zzzzbzzzz 

Answer 1

This problem can be recounted as:

What is the minimum number of moves to convert a string S to a string containing only 'a'?

Definition

Consider a continuous subsequence as a sequence of identical characters in a string. The smallest contiguous subsequence is naturally the only symbol. If you normalize small subsequences, you naturally get large subsequences, eventually getting one subsequence - the whole line.

What is normalized for :

Only the UP or DOWN character can be moved, so the character itself is a sequence of UP and DOWN steps. The worst case of representing a character is a letter in the middle of the alphabet, which requires at least len(alphabet) / 2 movement. In the alphabet {a..z} worst are 'm' and 'n' .

Since we want to minimize the number of moves, we need to pull out the letters DOWN C <= m and pull them out C >= n . Thus, in order to minimize the normalization process, we must find the largest subsequences that require equal normalization moves. For example, if we have a goal zzzzbzzzz , we know that the minimum directions of UUUUDUUUU are U for UP and D, DOWN.

Normalization

For each movement, the counter is incremented, which gives the least number of moves needed to convert the string. Given the above example, we can take the following steps:

 # = 0 | zzzzbzzzz | UUUUDUUUU (choose the smallest subsequence to normalize) # = 1 | zzzzazzzz | UUUUDUUUU (since 'a' is the base character, we choose the move that increases the largest subsequence; if 'a' was the first or last character, moving it would simply be overhead) # = 2 | zzzzzzzzz | UUUUUUUUU (choose the subsequence to normalize) # = 3 | aaaaaaaaa | _________ (choose the subsequence to normalize) 

Another example, with the target string abcxyz :

 # = 0 | abcxyz | _DDUUU (choose the smallest subsequence to normalize) # = 1 | aabxyz | __DUUU (choose the smallest subsequence to normalize) # = 2 | aaaxyz | ___UUU (choose the smallest subsequence to normalize) # = 3 | aaayza | ___UU_ (choose the smallest subsequence to normalize) # = 4 | aaazaa | ___U__ (choose the smallest subsequence to normalize) # = 5 | aaaaaa | ______ (choose the smallest subsequence to normalize) 

EDIT

As @ user1884905 pointed out, this solution , as suggested, is not optimal . In the case of the target string mn algorithm does not lead to an optimal solution:

 # = 0 | mn | DU (choose the smallest subsequence to normalize) # = 1 | ln | DU (choose the smallest subsequence to normalize) # = 2 | kn | DU (choose the smallest subsequence to normalize) ... # = 12 | an | _U (choose the smallest subsequence to normalize) # = 13 | ao | _U (choose the smallest subsequence to normalize) # = 14 | ap | _U (choose the smallest subsequence to normalize) ... # = 24 | aa | __ (choose the smallest subsequence to normalize) 

And this is not optimal, since the following steps require less moves:

 #0 #1 #2 ... #12 mn -> mm -> ll -> ... -> aa 

Perhaps the optimal substructure of the greedy algorithm is to reduce the global distance between characters from the string, instead of focusing on the difference between such characters and the base case ( 'a' ).

Answer 2

Since this is just additional information and, possibly, some kind of optimization, this should be a comment on Rubens' answer, but in response I can explain it better, and this can be useful for the questioner.

I also use Rubens' excellent inverse idea.

So, I think that there is no situation when it is necessary to turn a to something else. If this is correct (I do not have a counterexample), there is no situation where we should rotate something in the wrong direction (I have no mathematical proof, but this is probably correct).

Thus, each subsequence of U and D will rotate each time with one movement. This algorithm will not accept O (n ^ 2) time. Here is the algorithm:

We will call the string Rubens direction string

• set counter 0
• calculate direction line
• scan the direction line.
• If you find a continuous subsequence of letters U or D, rotate the target line at a position in the direction a and increase the counter (once for each subsequence).
• if there was any operation, go back to step 2

This algorithm will rotate each wheel to a , and this will be done after no more than k/2 scans, where k is the counter of the elements of the alphabet, so this may be a solution that runs in linear time.

---

Perhaps there is a solution with even less operation. This is just an idea with the search for increasing, decreasing or subsequences of "hill shape" and extracting the maximum value. For example: we can say without computation that the cost of a solution

• abcde ,
• ecb ,
• abceeddcb

equal to the cost of solving one e

EDIT: I saw user1884905 counterexample. Therefore, my algorithm will not find the optimal solution, but it may be useful for finding the right algorithm, so I still do not delete it.

EDIT 2: Another idea that works with sample target lines: the middle letter can be calculated. This is the one for which the sum of the distances from the target string letters is minimal. Each letter must be rotated here using the algorithm above, then the entire string can be rotated to aaaaaaaaaa . Since the alphabet is cyclical, there can be more than one middle letter (as in the second example in the question), in this case we must choose the one that has a minimum distance from a .