Slashdot Mirror

← Back to Stories (view on slashdot.org)

Programming Contest: Efficient Editor Usage

Posted by timothy on from the colon-w-colon-q dept.

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!"

33 comments

  1. vim-like? by keesh · · Score: 5, Interesting

    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?

    1. Re:vim-like? by zonx+lebaam · · Score: 3, Interesting
      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).

    2. Re:vim-like? by pepsee · · Score: 1

      Um, do you really find f F t F useful in vi(m)? More useful than a plain search?

  2. Contest to find most effienct keystrokes by Mycroft_514 · · Score: 3, Interesting

    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.

    1. Re:Contest to find most effienct keystrokes by pclminion · · Score: 1

      Is it your brain? ;-)

    2. Re:Contest to find most effienct keystrokes by duggy_92127 · · Score: 1

      Submit it, then. I'll look for Mycroft in the live standings.

      Doug

  3. IP by Flinx_ca · · Score: 1

    Don't forget to copyright and patent your brilliant idea before you submit it. Microsoft might use it in Longhorn and then sue you later.

    1. Re:IP by Anonymous Coward · · Score: 0

      It never ceases to amaze me how people can talk about IP issues so much and still be so utterly clueless about them. Does it ever occur to you dummies to say "Gee, maybe if I learned a little bit, I could say non-stupid things instead of utterly stupid things!"?

  4. dupe by Anonymous Coward · · Score: 0

    i saw this already on slashdot

  5. pff... by grub · · Score: 3, Funny


    Just use sed, like a RealMan.

    --
    Trolling is a art,
    1. Re:pff... by Craig+Maloney · · Score: 1

      I'm glad I'm not the only one who thought 'why not use sed?'. What's the point of this contest?

    2. Re:pff... by Profane+MuthaFucka · · Score: 1

      The point of the contest is to win. You can't use sed, because that's not in the rules.

      --
      Fascism trolls keeping me up every night. When I starts a preachin', he HITS ME WITH HIS REICH!
    3. Re:pff... by grub · · Score: 2, Funny


      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.

      --
      Trolling is a art,
    4. Re:pff... by AuMatar · · Score: 3, Interesting

      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.

      --
      I still have more fans than freaks. WTF is wrong with you people?
  6. Easy by Anonymous Coward · · Score: 0

    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."

    Hmm... change one block of text into another with editor commands. So we'd need an editor... let's call it 'ed'... and we'd need it to operate on a stream rather than a file... so I suppose we could call it 'sed'. Quite frankly, I'm amazed that nobody has thought of this before.

  7. Brute Force solution by Craig+Maloney · · Score: 1

    >aNEWLINEGOESHEREd>aNEXTLINEGOESHERE

    I'm thinking this may be the most efficient for really different sets of files. :)

    1. Re:Brute Force solution by duggy_92127 · · Score: 2

      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

    2. Re:Brute Force solution by Craig+Maloney · · Score: 1

      Whoops... I forgot about resetting the line so I'm working from the beginning.

      Hope your solution wins! :)

    3. Re:Brute Force solution by duggy_92127 · · Score: 2, Interesting

      Tied for 6th place!

      Doug

  8. Watch out by slapout · · Score: 2, Funny

    "'vim-like' editor commands"

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

    --
    Coder's Stone: The programming language quick ref for iPad
    1. Re:Watch out by atomic-penguin · · Score: 1

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

      There is already a M-x vi-mode.

      --
      /^([Ss]ame [Bb]at (time, |channel.)){2}$/
    2. Re:Watch out by Anonymous Coward · · Score: 0

      Emacs has two of 'em: elvis and viper.

      Then there's vile, which attempts to put emacsisms into vi. Succeeds a great deal less, it still can't lose the modality.

    3. Re:Watch out by slapout · · Score: 1

      So now emacs people argue with themselves?

      --
      Coder's Stone: The programming language quick ref for iPad
    4. Re:Watch out by smittyoneeach · · Score: 1

      Dude, gmane.emacs.devel had a lengthy discussion (well short of a flame war) about whether or not emacs should automatically put a new line character at the end of a file.
      We're talking text-editor passion here, baby.

      --
      Get thee glass eyes, and, like a scurvy politician, seem to see things thou dost not.--King Lear
  9. Genetic Algorithm anybody? by stevey · · Score: 2, Insightful

    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.

    1. Re:Genetic Algorithm anybody? by pclminion · · Score: 1
      I was thinking along the same lines... For a fitness function, some combination of sequence length and Levenshtein distance between the source and transformed source strings?

      The obvious would be a simple linear combination: a1 * Len(P) + a2 * Lev(Src, P(Src))

      Where P is the editing sequence, P(Src) is the result of running P on the source string, and Lev is the distance between the source and target.

      a1, a2 could be manually tuned, or superselected by some appropriate method.

    2. Re:Genetic Algorithm anybody? by pclminion · · Score: 1

      Erf... That should have been a2 / Lev(Src, P(Src))

    3. Re:Genetic Algorithm anybody? by Anonymous Coward · · Score: 0

      Eugenics is never fun.

  10. Edit distance with traces by perkr · · Score: 4, Informative

    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.

    1. Re:Edit distance with traces by Karma+Farmer · · Score: 3, Interesting

      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).

    2. Re:Edit distance with traces by perkr · · Score: 2, Informative

      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.

    3. Re:Edit distance with traces by Anonymous Coward · · Score: 1, Interesting

      I think there you have actually hit the crux of the issue. There is a ton of work, some of which half-way solves the issue. This means that you have to
      a) work out which part of the ton does actually half solve the problem, and
      b) work out how to extend it to do the other half of the work.
      The fact the scoring is based upon all commands including cursor movements means that it isn't the case of just finding the smallest number of changes for each line.

      Mole125

  11. Triviality by zonx+lebaam · · Score: 1
    This is a great problem - I'm sorry I don't have time to really try to work on a submission :(.

    Finding a shortest edit on any one of those lines would be trivial.
    Perhaps I'm being thick here, but I can't really see how to do this. For example, consider trying to reduce the problem using maximal length shared substrings (sort of like doing greedy regex searches). Consider transforming this:

    AABCDE

    into this

    AAABCD
    Even though the shared substring takes up most of the example, trying to preserve it makes for an expensive solution (because of the penalty for inserting characters in front). Of course one can insert in the second position much more cheaply than the first, but it "ruins" the substring that starts in the zeroth column.

    In fact, I'm sort of starting to wonder if finding "the solution" to this problem is intractable (at least for the specified input sizes and CPU time max). This means that heuristics are the name of the game, and the problem does lend itself to some interesting ones.

    Finding the shortest edit on all of the lines simultaneously would be interesting
    Indeed. Particularly intriguing is the topological characteristic that it is fast and cheap to jump (or even delete) one's way to the start or end of a line, but expensive to get to a place in the middle. One can wormhole around this by virtue of having lines of different lengths to go into and out of (as alluded to in parent). A final strategic observation is that as one starts to close in on the endgame, and the strings start to get long again (short strings at the beginning make for less maneuvering), one would like to be more or less appending things to the end.

    Can anyone come up with a convincing argument that the single-line subproblem is easy/hard?