algorithm - 用最少的步数打开锁

Question

考虑一个由轮子系统制成的锁。每个轮子按顺序有 26 个字母，每个轮子都用 初始化'a'。如果您向上移动一个轮子，则该轮子的显示将移至字母表的下一个字母；另一方面，向下移动轮子会将显示切换到字母表的前一个字母。例如：

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

只需轻弹一下，就可以沿同一方向移动任何连续的轮子序列。这与以这种方式移动子序列的所有轮子具有相同的效果，只需一次运动。例如，如果目标字符串是'zzzzzzzzz'，则一个单一的运动，改变'a'到'z'，将改变整个轮子序列从'a'到'z'，从而到达目标字符串 - 打开锁。

如何确定打开锁的最少移动次数？这个问题有动态解决方案吗？该算法必须产生以下结果：

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

案例1，目标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

案例5，目标zzzzbzzzz：

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

Answer 1

这个问题可以重新表述为：

将字符串 S 变为仅包含 'a' 的字符串的最小移动次数是多少？

定义：

将连续子序列视为字符串中相等字符的序列。最小的连续子序列自然是单个字符。如果你对小子序列进行归一化，你自然会得到更大的子序列，最终达到一个子序列——整个字符串。

规范化到什么：

一个角色只能向上或向下移动，所以，一个角色本身就是一个向上和向下移动的序列。字符表示的最坏情况是字母表中间的字母，这至少len(alphabet) / 2需要描述动作。在字母表{a..z}中，最坏的情况是'm'和'n'。

由于我们想最小化移动的数量，我们需要拉下字母C <= m，然后拉上那些C >= n。因此，为了最小化归一化过程，我们必须找到需要相同归一化移动的最大子序列。例如，如果我们有一个目标zzzzbzzzz，我们知道最小的方向是UUUUDUUUU——U 表示向上，D 表示向下。

规范化：

对于每次移动，计数器都会递增，从而产生转换字符串所需的最少移动次数。考虑到上面的例子，我们可以采取以下步骤：

# = 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)

另一个例子，使用目标字符串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)

编辑：

正如@user1884905 所指出的，这个解决方案，正如它所提出的那样，不是最优的。在目标字符串的情况下mn，该算法不会导致最优解：

# = 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)

这不是最优的，因为以下步骤需要较少的移动：

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

也许贪心算法的最佳子结构在于减少字符与字符串之间的全局距离，而不是关注这些字符与基本情况 ( '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.