Search code examples
algorithmdynamic-programming

Open a lock with the least number of moves

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
Solution

  • 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').