POTM: Programmer of the Month: KEYSTROKES: The Details

In general, if you have a question about the detailed rules, the simplest choice is usually the right choice - the goal being to encourage participation. If you have questions - please post them to the forum.
Any change made after the initial post will be marked (and dated) in red.
Deadline for KEYSTROKES is May 31, 2005.

I am not a good typist. When I was creating this POTM I typed in KYESTROKS when I meant to type KEYSTROKES. This POTM asks you to determine the most "efficient" way to correct such errors.

For example, you could delete all the letters and type in the correct spelling. Or you could move to the second position and delete the "YE" and then add "EY" and then move to the next-to-last position and then add the "E". But surely YOU can write a program figure out the most efficient way to perform this sort of operation.

You will be given two blocks of text, a "starting" block and a "target" block. Your program, using special POTM "editor-like" operations defined in the problem statement details, will be asked to provide a sequence of editing operations and typed letters that will transform the initial block to the target block. Shortest sequence wins. I'm hoping the problem turns out to be more difficult than it sounds! Full details are below - please read them!


errata
  • POTM is pronounced "PAH-TUM"
  • The M stands for Month - but problems are posed irregularly
  • The POTM-MASTER is omnipotent, but is allowed to change his mind whenever he sees fit.
  • Have fun ... if you're not having fun, do something else for a while!

    SPECIAL RULES FOR KEYSTROKES


    THE TASK AT HAND
  • You will be given a "block" of upper case letters containing from one to five lines of 80 or fewer upper case letters per line as you "STARTING" block.
    KEYSTROKESISTHEPOTM
    FORMARCHAPRILANDMAY
  • You will be given a second "TARGET" block which contains the same number of lines, each of which will contain 80 or fewer upper case letters per line.
    THEPOTMDEADLINEISTHE
    LASTDAYOFMAY
  • Using ONLY the editing commands defined below, your program must output a string of commands (and letters) that will transform the STARTING block into the TARGET block.
  • Each of your commands will either move a "cursor" through the text block, delete one or more characters, or add additional characters following the current cursor position.
  • The STARTING and TARGET blocks will have the same number of lines: at least one line and no more than five lines.
  • Each line of each block will contain at least one upper case letter and no more than 80 upper case letters. The number of characters may differ for each line and may differ between the starting and target blocks.
  • Both blocks will contain ONLY upper case (A-Z) letters. There will be no white space nor will there be any other characters other than the LF ( X(0a) or '\n' ) at the end of the line.
  • The cursor will initially be located on the first (leftmost) character of the first (top) line.
  • While neither the STARTING or TARGET blocks will have more than 80 characters per line, it is permissible for "interim" blocks to contain any number of characters per line.

    THE EDITING COMMANDS YOU CAN USE
  • All command letters are lower case, >, or <. The table shows the effect on the block of letters and the resulting cursor position:
     b move cursor to the beginning of line
     e move cursor to the end of line
     l move cursor one position to the left
     r move cursor one position to the right
     u move cursor one row up
     d move cursor one row down
     x delete current character*cursor doesn't move
     > delete current through end of line*cursor at end of line
     < delete front of line through current*cursor at beginning of line
     a add all upper case characters following the "a" after the cursorcursor on last character added

  • Only the commands above (b,e,l,r,u,d,x,>,<) or an "a" followed by any number of upper case letters may be contained in your output.
  • *See the examples below for "special cases" of command behavior which depend on where the cursor currently resides.
    EDITING COMMAND EXAMPLES
  • Just to be sure that things are clear, I wanted to provide some examples of the various editing commands. All examples assume that your cursor starts on the letter "N" and after the specified operation will reside on the position marked in red.
    These are the cursor movement commands. Starting on the letter "N", the commands will move the cursor to one of the positions marked in red as indicated by the following:
    b"beginning of line"J
    e"end of line"S
    l"left"M
    r"right"O
    u"up"E
    d"down"X

    This is the starting position for
    the examples below.
  • A cursor command may not move beyond the top or bottom row or past the end of the line.
  • A "d" or "u" command that would place the cursor beyond the end of the line will cause the cursor to move to the end of the specified line. (i.e: a "d" command at the letter "S" would move the cursor to "Z").
  • A command that cannot be performed will result in non-movement of the cursor (like a "d" on the last line or a "r" at the end of the line).
  • The "x" operation simply deletes the character under the cursor and leaves the cursor where it is - which now contains a new letter ("O" in this example). If the "x" is applied when the cursor is at the end of the line, the letter will be deleted and the cursor will move one position to the left and hover over the "new" last letter in the line. An "x" on an empty line will do nothing.
    The "x" operation deletes "N"
    The ">" operation deletes the current position and everything to the right. The cursor is then placed on the last character in the line. If ">" is used at the beginning of the line, all characters are removed and the cursor is left hovering at the beginning of the line. If ">" is used at the end of the line, the operation is equivalent to the "x" operation and deletes the final character.
    The ">" operation deletes "N-S"
    The "<" operation is similar to the ">" operation but deletes everything from the beginning of the line up to and including the current cursor position. In the first position it behaves like an "x". In the final position it will delete the entire line and place the cursor in position one of the blank line.
    The "<" operation deletes "J-N"
    The "a" command is the only command that will allow you to add text. The "a" will look at all upper case (capital) letters following the "a" and insert the new letters after the current cursor position. The cursor will end up on the last letter of text that is added. The example to the right assumes the cursor was positioned on the "N" and the command "aXX" was given. An "a" command on an empty line will add the following upper case letters to the line. An "a" command with the cursor positioned at the end of the line will add the text to the right of the current line and leave the cursor at the new end of the line. The next command (lower case letter, >, and <) will signal the end of the upper case string that is to be added. The end of the output may also signal the end of the string.
    The "aXX" operation adds the
    letters "XX" after "N"

    THE INPUT FILE
  • will be provided as a full pathname argument to your executable, as in:
    my_entry   /tmp/inputfile
  • The input file will contain the STARTING block followed by a single empty line followed by the TARGET block.
  • An example of the file your program will work with:

    KEYSTROKESISTHEPOTM
    FORMARCHAPRILANDMAY
    
    THEPOTMDEADLINEISTHE
    LASTDAYOFMAY

    Note that both blocks have two lines
    Note that the line lengths may vary
    Note the empty line separating the starting and target blocks
  • There will be no white space in the input file.
  • There will be only upper case letters (A-Z) in the file.
  • Each line (including the empty one) is terminated with a LF ('\n').
  • As stated above, the blocks will have the same number of lines, and each line may contain from one to 80 upper case characters.
  • The full path to the input file will be presented as an argument to your executable.
    OUTPUT OF YOUR ENTRY
  • Your output will be a string of commands (as above).
  • Aside from the commands themselves, the only other characters in the output string shall be stings of upper case letters that follow the "a" command.
  • No white space, no special characters, no numbers, nothing except the commands and upper case letters. (except for the following item)
  • Your output string should be terminated with a line feed ( X(0a) or '\n' )
  • Some sample legal output with explanations - obviously they can get quite long and quite complex:
    rrrdxx move three to the right, down one, delete two characters
    drrr< move down one, three to the right, delete postiions 1-4 (note that you will be on the fourth character after the "rrr")
    rrr>aABCdx move three to right (to column 4), delete positions 4 through the end of line, add three letters: "ABC", move the cursor down one (note that the "d" signals the end of the input string), and delete a character
    daABCbx move to the 2nd row, add the letters ABC in postions 2-4, return to position one (b) and delete the first character. In effect, this replaces the first character on line 2 with "ABC". Note that putting something at the beginning of the line is harder than adding something to the end of he line!

    WINNING KEYSTROKES
  • The score of your solution will be

    SCORE = commands + 2*letters

    where the number of letters is the number of upper case letters in your output string and the number of commands is everything else in your output string.
  • Example: the string " r r r a X Y Z d x x " would score 7 + 2*3 = 13
  • Low scores are good, high scores are bad
  • For the finals, three sets of input will be provided and the scores for each program will be computed. The winner will be determined based on the relative finishing positions on each of the three finals.
  • If necessary, only entries that tie for best positional finishes will be subjected to additional input to resolve the ties.
  • If there are still ties on the additional input files, the entry with the fewest upper case letters overall will be the better solution.
  • This particular problem may have several entries that all find the "best" solution every time - in which case the fastest entry will prevail.

    COMMON RULES FOR POTM PROBLEMS


    WINNING IN GENERAL
  • Entries completing system test will be eligible for the final runs.
  • one entry per forum login
  • multiple submissions of the same algorithm by the same person or team will NOT be tolerated - please don't do this - it will be obvious in the end and only cause pain for the other participants
  • Your official entry must be submitted for system test by the deadline (23:59 Eastern time on the deadline date) using the sandbox tools in order to participate in the finals.
  • Specific winning criteria will vary for each POTM and should be clear from the above sections. If there are questions, use the forums please.
    Personal info, Consolation Awards and Other Fun Stuff
  • Your email will never be made public and will not be shared with anyone. To communicate, use the "private message" capabilities in the forums.
  • Your full name (provided for the sandbox) will not be revealed unless you happen to win - in which case it will appear on the trophy as you are announced with pride as the winner. Of course, I will have no way of knowing if it is your real name.
  • Your code will be publicly available via the website (if you are worthy) and the top finishers are usually given an opportunity to make their code "pretty".
  • The POTM is for fun. In that spirit, there are generally awards for things like best program name and the like ... basically anything that I feel like at the end of a contest.
  • Participants are also encouraged to provide an exposition on their algorithm after the deadline passes ... these responses are often the most fun to read and offer insights into the foibles and quirks of the participants.
    Running The Tests - the POTM-MASTER's job
  • I will subject all entries to a "system test" to qualify them for the actual event - these are run regularly via cron (in general).
  • Scores on the system test problem may (or may not) be public - this will vary by POTM at my discretion.
  • System test results are sent to the participant via email including whatever might be of use for debugging purposes.
  • If asked nicely (via private message in the forums) it may be possible to make a debugging run and supply the output, but in general all debugging should be done on YOUR machine.
    Programming Stuff
  • Input will (most frequently) be provided as a full path argument to your entry
    my_entry   /tmp/inputfile
  • Input file format will be explicitly defined for each POTM problem.
  • Your POTM problem output (with no extra output) goes to stdout
  • Explicit required output format will be defined for each POTM problem.
  • Nothing should be written to stderr
  • You may "save" information in a small temp file in the local directory (at present there is no enforced size limit) if not explicitly prohibited by a particular problem.
  • There will be a per execution time limit (60 sec. sys+user time as measured by /usr/bin/time unless otherwise stated). Entries that exceed the time limit will receive a zero score. A signal (9) is sent to the program by the host when the time limit is exceeded.
  • any attempt to do anything whatever outside of your personal run directory will be cause for disqualification and banning.
  • C and C++ programs will be compiled with only the math library added to the standard libraries and no optimization.
  • Non C/C++ entries must contain a first line beginning with "#!" as specified in the sandbox instructions.


  • The POTM is unsponsored and just for fun.       Thursday 06:54:17 PM      Copyright © 2004-6 - Fred Hicinbothem