Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Programming Technology

Programming Contest: Efficient Editor Usage 33

Posted by timothy 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!"
This discussion has been archived. No new comments can be posted.

Programming Contest: Efficient Editor Usage More

Programming Contest: Efficient Editor Usage

Comments Filter:

  • vim-like? (Score:5, Interesting)

    by keesh ( 202812 ) on Wednesday March 16, 2005 @03:42PM (#11957371) Homepage
    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? (Score:3, Interesting)

      by zonx lebaam ( 688779 )
      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).

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

  • Contest to find most effienct keystrokes (Score:4, Interesting)

    by Mycroft_514 ( 701676 ) on Wednesday March 16, 2005 @03:44PM (#11957392) Journal
    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.

  • IP (Score:1)

    by Flinx_ca ( 809816 )
    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.

  • pff... (Score:3, Funny)

    by grub ( 11606 ) <slashdot@grub.net> on Wednesday March 16, 2005 @04:13PM (#11957750) Homepage Journal

    Just use sed, like a RealMan.
    • I'm glad I'm not the only one who thought 'why not use sed?'. What's the point of this contest?
      • The point of the contest is to win. You can't use sed, because that's not in the rules.

      • Re:pff... (Score:2, Funny)

        by grub ( 11606 )

        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... (Score:4, Interesting)

        by AuMatar ( 183847 ) on Wednesday March 16, 2005 @04:57PM (#11958347)
        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.
  • >aNEWLINEGOESHEREd>aNEXTLINEGOESHERE

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

  • Watch out (Score:2, Funny)

    by slapout ( 93640 )
    "'vim-like' editor commands"

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

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

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

  • Edit distance with traces (Score:4, Informative)

    by perkr ( 626584 ) on Wednesday March 16, 2005 @05:56PM (#11959077)

    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 (Score:4, Interesting)

      by Karma Farmer ( 595141 ) on Wednesday March 16, 2005 @09:09PM (#11961110)
      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).
      • 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.

        • Re:Edit distance with traces (Score:1, Interesting)

          by Anonymous Coward
          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
      • 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 make

Slashdot Top Deals

I cannot conceive that anybody will require multiplications at the rate of 40,000 or even 4,000 per hour ... -- F. H. Wales (1936)

Close