Programming Contest: Efficient Editor Usage

Fred (a.k.a. The POTM-MASTER) writes "Anyone can write editors, but it's surprisingly hard to write a program to USE an editor. This latest Programming challenge asks you to write a program that will change one block of text into another using a simple set of 'vim-like' editor commands." (Find the details here.) "Deadline is May 31, 2005 so you've got plenty of time. The POTM is the 'Programmer Of The Month' contest - newly revived and active with about 1000 folks registered for the forums. It is completely for fun - unsponsored and prize-less except for the fame!"

Comments

Edit distance with traces

[perkr]

So what's the deal with this?

Use the edit distance algorithm and find all traces transforming the source string into the target string. Then go through all traces and try to chunk them into as big "editing chunks" as possible, which depends on whatever the editing operations they permit.

Re:Edit distance with traces

[perkr]

I missed the multiple independent lines of text part. I still feel this should be at least half-way solved, there's a ton of work that has been vested in finding efficient algorithms to transform large strings under various conditions and circumstances.