是否存在一种算法，可以解决Vim的高尔夫问题 [英] Does there exist an algorithm that can solve Vim Golf problems

问题描述

是否有可能建立一个算法解决的Vim高尔夫球场的问题？对于那些不熟悉的是什么，您将得到两个不同的文本块，并且必须使用按键（在典型的例子使用Vim的最低数量改造的第一个块至第二或任何文本编辑程序，你选择使用）。我最初的怀疑是，答案是否定的;我们知道一个上限所需要的文本更改数 - 手动删除的差异，并输入正确的文字。然而越来越下降到的最低金额是更为复杂 - 文本编辑器可以编程强大的宏来执行任务，你可以有多个宏的组合物 - 我猜，可能有一些方式来展现一个对应的停机问题，但我'不十分清楚的细节。

Is it possible to create an algorithm to solve Vim-golf problems? For those not familiar with what that is, you are given two different blocks of text, and must transform the first block into the second using the lowest possible number of keystrokes (using Vim in the canonical example, or whatever text editing program you choose to use). My initial suspicion is that the answer is no; We know an upper bound on the number of text changes required - manually delete the differences and enter the correct text. However getting down to the minimum amount is more complicated - text editors can program powerful macros to perform tasks, and you can have compositions of multiple macros - I'm guessing that there might be some way to show a correspondence with the halting problem but I'm not quite sure of the details.

推荐答案

那么它肯定不是不可判定的，因为你可以试试按键的所有可能的序列，直到你找到答案。有一个上限的长度，因为你可以删除一个，然后插入其他。而且，即使有减少一些NP难的问题，你可能罚款的近似值。如果一个人能做到这一点，计算机应该能更好的做到这一点。

Well it's certainly not undecidable, because you can just try all possible sequences of keystrokes until you find the answer. There's an upper bound on the length, because you can just delete one and insert the other. And even if there is a reduction to some NP-hard problem, you are probably fine with a good approximation. If a human can do it, a computer should be able to do it even better.

因此​​，它是可行的？也许，但它似乎是一个棘手的问题。

So is it doable? Probably, but it seems like a tough problem.

为什么呢？因为很多不平凡的问题，如编辑距离，字符串分解和无数的COM pression算法似乎减少到Vim的问题。一个人可以采取的解决方案为所有这些问题，并结合他们创造性地达成解决办法。

Why? Because a lot of non-trivial problems such as edit distance, string factorization and countless compression algorithms seem to reduce to the Vim problem. A human can take the solutions for all of these problems and combine them creatively to arrive at a solution.

这篇关于是否存在一种算法，可以解决Vim的高尔夫问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！