algorithmvimcomputer-sciencehalting-problemcomputability

Does there exist an algorithm that can solve Vim Golf problems


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.


Solution

  • EDIT: As was pointed out by WuTheFWasThat, VIM macros are turing complete, so the problem is most likely undecidable and hence the answer to your question is no. The reason my answer below is wrong is because it assumes we can decide in finite time whether a given sequence of keystrokes in VIM terminates, which is not the case.

    Old answer

    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.

    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.