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