Open a lock with the least number of moves

Question

Consider a lock, made of 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 moves to the next letter of the alphabet; moving a wheel down, on the other hand, switches the display to the previous letter of the alphabet. For example:

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

One can move any contiguous subsequence of wheels in the same direction with just a flick. This has the same effect of moving all the wheels of the subsequence that way, with a single motion. For example, if the target string is 'zzzzzzzzz', a single movement, changing 'a' to 'z', will change the entire sequence of wheels from 'a' to 'z', thus reaching the target string -- opening the lock.

How can I determine the least number of moves to open a lock? Is there a dynamic solution for this problem? The algorithm must yield 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, target zzzzbzzzz:

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

Answer 1

This problem may be restated as:

What is the minimum number of moves to turn a string S, into a string that only contains 'a'?

Definition:

Consider a contiguous subsequence as a sequence of equal characters in the string. The smallest contiguous subsequence is, naturally, a single character. If you normalize small subsequences, you'll, naturally, end up with bigger subsequences, eventually reaching a single subsequence -- the entire string.

What to normalize to:

One can only move a character UP or DOWN, so, a character itself is a sequence of UP and DOWN moves. The worst case of representation of a character is the letter in the middle of the alphabet, which requires at least len(alphabet) / 2 moves to be described. In the alphabet {a..z}, the worst cases are 'm' and 'n'.

Since we want to minimize the number of moves, we need to pull DOWN letters C <= m, and pull UP those C >= n. Thus, to minimize the normalization process, we must find the greatest subsequences that requires equal normalization moves. For example, if we have a target zzzzbzzzz, we know the minimal directions are UUUUDUUUU -- U for UP, and D, DOWN.

Normalizing:

For each move, the counter is incremented, yielding the least number of moves required to transform a string. Considering the above example, we may 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 pointed by @user1884905, this solution, as it is proposed, is not optimal. In the case of a target string mn, the 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, as the following steps require less moves:

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

Maybe the optimal substructure to a greedy algorithm lies in reducing the global distance between the characters from the string, instead of focusing on the difference between such characters and the base case ('a').

Answer 2

Since this is just some additional info and maybe some optimization, this should be a comment to the answer of Rubens, but in an answer I can explain it better and it can be useful for the questioner too.

I also use the great reverse idea of Rubens.

So, I think there's no situation when it is necessary to rotate an a to something else. If this is correct (I have no counterexample), there is no situation where we should rotate something to the wrong direction ( I have no mathematican proof, but probably this is correct).

So, every subsequences of Us and Ds will be rotated each time with one motion. This algorithm won't take O(n^2) time. Here is the algorithm:

Let we call Rubens's string direction string

1. set a counter to 0
2. compute the direction string
3. scan the direction string.
4. if You find a contigous subsequence of U or D letters, rotate the target string at the positions towards a and increment the counter(once for each subsequence).
5. if there was any operation, go back to step 2

This algorithm will rotate every wheel to a and it will be done after at most k/2 scanning, where k is the count of the elements of the alphabet, so this may be a solution that runs in linear time.

---

Maybe there is a solution with even less operation. It is just an idea, with finding increasing, decreasing or "hill-shape" sub-subsequences and extract the maximum value.For example: We can say without computing, that the cost of solving

• abcde,
• ecb,
• abceeddcb

is equal to the cost of solving a single e

EDIT: I've seen user1884905's counterexample. So my algorithm will not find the optimal solution, but it can be usable to find the correct algorithm, so I don't delete it yet.

EDIT 2: Another idea that works with the sample target strings: There could be computed an average letter. It is the one for which the sum of the distances from the target string's letters is minimal. Every letter should be rotated here with the algorithm above, then the whole string can be rotated to aaaaaaaaaa. Since the alphabet is cyclic, there could be more than one average letter( like in the second example in the question), in this case we should chose the one with the minimal distance from a.