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

vim-like?

[keesh]

Hardly vim-like... It's missing all the useful stuff like f F t T, all text objects and motions and all the modal stuff. These're the things that make vim so much more powerful than anything else.

But then, I guess "using a few simple manipulation commands" doesn't sound as sexy, eh?

Re:vim-like?

[zonx lebaam]

Perhaps they should have said TECO-like (to give us the idea without raising vi-religious hackles), but, of course, that wouldn't address your actual point that the problem rules aren't targetted at as rich a command space as vi (or ed or TECO either (by a long shot)).

In that regard, I think the problem is quite cleverly designed, as the choice of commands is small yet sufficient to invite complex solutions (beyond just finding the smallest diff between the inputs).

Contest to find most effienct keystrokes

[Mycroft_514]

should be changed to a contest to find the most efficient way to do the job. I wrote such a job finisher years ago, and it is used by myself and others to check Project Gutenberg texts.

And my method is capable of learning.

pff...

[grub]

Just use sed, like a RealMan.

Re:pff...

[grub]

The winning entry will probably have a nice, eye-candy laden window with animated spinning skulls, crappy MIDI music (just like a geocities page) with an Expect backend. Naturally the name will be called "Kreplace" or "GNU/Instead" or something equally stupid.

Re:pff...

[AuMatar]

For fun.

Its also a non-trivial algorithm. Basicly a bunch of partial line diffs and trying to find as much commonality as you can. RCS systems use this type of functionality. The better you make them, the better they can do. ALthough a real RCS system would need to be able to analyze over y as well as x, this seems to have a very limited y.

Re:Brute Force solution

[duggy_92127]

That solution fails, by the way, to reproduce the target. I'm using:

>aFIRSTLINEd<>aNEXTLINE

That should reproduce any target, without regard to the input. And I submitted it, we'll see just how well it does. :)

Doug

Watch out

[slapout]

"'vim-like' editor commands"

Oh no. Don't tell the emacs people about this...

Re:Brute Force solution

[duggy_92127]

Tied for 6th place!

Doug

Genetic Algorithm anybody?

[stevey]

I think an obvious approach here is to use a genetic algorithm - literally breed the best collection of editting commands to generate the output.

Reading the rules says that there is a time limit of 60 seconds per program, so it might not be the best approach in reality - but it might be a fun way to attack the problem.

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

[Karma Farmer]

The problem involves transforming multiple, independent lines of text. Finding a shortest edit on any one of those lines would be trivial. Finding the shortest edit on all of the lines simultaneously would be interesting.

For example, change a couple of characters on the first line (which moves the cursor left or right); go down a line; change a couple of characters (again moving the cursor left or right); return to the first line and perform some more edits...

So, there are two problems -- solving the problem in the minimum number of moves (which should be doable with a small amount of thought), and solving the problem in the minimum amount of time (which will be more difficult, because the standard diff algorithms aren't sufficient).

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.