Describe briefly the strategy FCI_CairoUniv_EGYPT used for KEYSTROKES:

-----------------------
The Big Picture:
----------------
Step 1
For each starting block line, I get some possible solutions that
will convert it to the corresopnding block line.
Step 2
Combine some of the previous line solutions to get some whole 
problem solutions.
Step 3
I Investigate some of the whole problem solutions I get in step 2 
trying to make them better.
-----------------------
The Details:
------------
Step 1:
---------
For each line:
  For each possible line index (i):
    For each possible line index (j) where (j>=i):
      - Make '<' at position i-1 (if i-1 >= 0).
      - Make '>' at position j+1 (if j+1 < line size).
      - Get Longest Common Subsequence between the middle part of 
         the line (from i to j) and the corresonding whole target line.
      - Make insertions and deletions to convert the line part to
         the target line, such that the common parts which I have got 
         in the longest common subsequence are not touched.
      - Save the line solution consisting of the previous operations.
-----------------------
For each line:
  - Save the line solution of '>' at start then insert all target line.
  - Save the line solution of '<' at end then insert all target line.
-----------------------
Note: If the start line matches the goal line, the previous steps are 
  not performed.
-----------------------
After step 1, we have a lot of solutions for each line. Step 1 can 
be done in less that 1 second if the algorithm of the longest common 
subsequence is implemented carefully using dynamic programming as in
the book "Introduction to Algorithms" By "Cormen".
-----------------------
Each of the solutions which we have got for each line consists of
operations ordered from left to right (until now). We maintain these
operations in suitable structures.
-----------------------
Step 2:
---------
For each line:
  For each solution we got in step 1:
    - Simulate executing solution operations (kill, insert, delete) 
       in order from left to right, taking into consideration the 
       shortest path when going from one operation to the next one.
       (The shortest path can be obtained easily by carefully designed
        Algorithm that takes into consideration all current line sizes).
-----------------------
Now we want to get 100 good solutions for the whole problem:
- Make array of 100, and put in it the best 100 solutions for the first 
   line.
- Combine the current 100 solution with the best 100 solutions for the
   second line. (By simulating executing the first line operations from
   left to right - as done before - then moving the cursor to the starting
   operation in the second line, then executing the second line operations
   in order from left to right - also done before).
- Put in our array of 100 solutions the best 100 combined solutions we have
   obtained until now.
- Perform the previous two steps until lines are finished.
-----------------------
Now we have 100 good solutions for the whole problem. We will take the
best 5 solutions and go to step 3.
-----------------------
Step 3:
---------
For each of the best 5 solutions:
  - Get all children for each solution by:
     1- Moving one operation (<>ax) from its order of execution to 
      another order.
     2- Swapping two operations' order of execution.
  - Recompute the child solution cost (Using shortest paths between any 
     two operations), based on its operations execution orders.
  - If this child is encountered before, ignore it. (This is done by
     simple hashing, and collisions are not avoided).
  - Save the best 5 children in the place of the 5 parents and do this 
     loop again until 58 seconds finished.
-----------------------
Fine details:
-----------------
1- Consider the condition:
start: KKKKKMMMMM
goal:  LLLLLMMMMM
My line solution for this case in step 1 will be: 
- Kill the first 4 K's.
- Go to the remaining K, and Insert L's.
- Go to the biginning of the line and kill the remaining K.
So, in this case we have two '<' operations in the same solution.
At step 3, when the order of execution of the second kill becomes before
the first kill, the first kill will not be done.
Note: Also, In this situation, the second kill must wait for the insert
operation of L's. This constraint is preserved in Step 3.
-----------------------
2- Consider the condition:
start: K
        KKKKKKAKKKKKKK
goal:  KLLLLLLLLLLLLL
         KKKKKKKKKKKKK
The best solution will be to insert LLLLL then delete A the insert
remaining LLLLLLLL.
My described algorithm does not get this solution, because the whole
insert operations is treated as one unit. So, in step 3, I split the
large insert operations into multiple ones and continue searching.
(But this is done only when the best solution did not change for a 
long time).
-----------------------
3- To preserve prformance of step 3, the operations of line solutions 
  which have more than 10 operations are combined to be only 10 (This
  is done in step 1).
**********************************************************************
If I had it to do all over again, here's what I'd try:
Some modifications to my algorithm, like:
- Trying all best common subsequences in step 1 (currently if there is
   two best common subsequences, I take one of them only).
- Better initial greedy algorithm for step 2.
- Some tabu search ideas in step 3.
**********************************************************************
I named my KEYSTROKES entry "FCI_CairoUniv_EGYPT" because ...
The entry name is the place I like so much, I have been graduated
from it, and I work as a teaching assistant in it also:
-----------------------
Faculty of Computers and Information,
Cairo University,
Egypt.
**********************************************************************
Where do you live?  work?  What do you do for fun?  Family?
-----------------------
- My name is "Amin Mohammad Allam".
- My age is 23.
- I live in Suez, Egypt. 
- I work as a teaching assistant at:
    Computer Science Department,
    Faculty of Computers and Information,
    Cairo University, 
    Egypt.
- I am interested in "Natural Language Processing".
- I like reading, programming, and playing football.

Describe briefly the strategy grilfiend used for KEYSTROKES:

Dynamic programming. Dumb and simple but challenging enough to write.
It finds an optimal solution from the set of solutions satisfying the following constraints:
 1. While editing a line, we can only visit other lines, not edit
  them.
 2. At any point of time, the current line could be split into two
  continuous parts, one of them being a prefix or suffix of the
  source line and another being a prefix or suffix of the destination
  line. Other lines should be exact copies of the corresponding source
  or destination lines.

Sounds too restrictive? Well, the second constraint is somewhat relaxed 
keeping in mind the fact that we cannot add letters to the beginning 
of a non-empty line. So, the algorithm also allows for one 'garbage' 
symbol at the beginning of the line which is deleted after we get 
the destination line beside it.

There are a couple more tricks in the exact definition of the constraints;
the aim of the above declaration is to show the general idea.
Anyway, there are simple tests which leave this algorithm no chance,
but on random tests, it's at least not too bad. If not for the time 
limit which is still hit on very big tests, especially nontrivial ones.
  
If I had it to do all over again, here's what I'd try:

Generate a solution (with the algorithm described above or some other) 
and then treat it as a sequence of changes and cursor movements. 
Make a graph with changes as vertices and movements as edges. 
Find optimal and various suboptimal paths in that graph. 
The problem is, when you change the order of vertices (i.e. changes),
the lengths of edges also vary. Thus, building a path, we should 
take current lengths of the edges into account and cannot guarantee 
optimality when building it with standard graph algorithms. 
So, the way of building suboptimal paths should be tricky enough to 
produce a good solution.

I named my KEYSTROKES entry "grilfiend" because ...

grilfiend is probably not a fiend of grill (wonder what it looks
like) but more likely a 'kyestroks'-style misprinting of the word 
'girlfriend'. By the way, writing a contest program is somewhat 
like treating a girlfriend... However, tastes differ! ;-)

Where do you live?  work?  What do you do for fun?  Family?

Russia, Saint Petersburg. I'm a student, doing my master thesis 
right now. I enjoy playing computer games as well as writing them 
(simple ones for my own and my friends' use), participating in 
programming contests, programming for fun, and investigating the 
properties of various software I get. Apart from computers, I study 
pure mathematics and enjoy it just as much. I live with my parents 
who are geographers and have somewhat different ways of having fun.

Thank you for the contest!
Ivan Kazmenko.

Describe briefly the strategy dsyleixc used for KEYSTROKES:

I have a greedy algorithm that attempts to change a single line 
of text at a time, and once one line is changed, it will move on 
to another line of text.

I keep track of the absolute minimum cost to change everything, 
and the greedy cost (see previous paragraph).

I somehow order all change sequences by minimum cost&greedy cost.  
Then I take the best one, and add all possible single character 
moves onto the end of it.  And then extend each of those using the 
greedy algorithm.

Repeat until time runs out.

If I had it to do all over again, here's what I'd try:

I would run the algorithm based on the closest change that can be made.  
This should significantly reduce the complexity

I named my KEYSTROKES entry "dsyleixc" because ...

Dyslexic.  Why else would you have small spelling/typing mistakes.

Where do you live?  work?  What do you do for fun?  Family?

Live: San Diego, CA
Work: The Dini Group
Fun: bike, dive, build brother's mansion...

- Describe briefly the strategy cross_word used for KEYSTROKES:

cross_word first examines each line for an 'optimal' set of common 
characters between the starting line and the target line.  
It then tries several ways of converting each starting line to the 
target line and outputs the one with the lowest score.

- If I had it to do all over again, here's what I'd try:

I'd try a more general purpose approach that generated many more 
different ways to convert the lines and evaluated them for optimal approaches.

- I named my KEYSTROKES entry "cross_word" because ...

My last name is Cross, and it's the best I could come up with :)

- Where do you live?  work?  What do you do for fun?  Family?

I live in southern New Hampshire (in the U.S.).  I work in Massachusetts 
at a company that makes consumer robotics.  For fun, my wife and I 
own horses and ride them on trails around town.

Describe briefly the strategy KeyCracker1c_30lines used for KEYSTROKES:

KeyCracker1 started out simply replacing each line with the target text. 
Later I spent an hour on KC1b and KC1c making some small optimisations 
while still keeping the code short.
KeyCracker1c simply leaves letters on the left alone if they match, and 
uses '<' rather than 'b>' if at the end of the line.

If I had it to do all over again, here's what I'd try:

Lobbying for an 'insert' command. The problem was interesting, but the 
difficult protocol killed my motivation (bring back the squirrels please).


I named my KEYSTROKES entry "KeyCracker1c_30lines" because ...

The program started out as an adaption of NutCracker, so the name was also 
adapted. There might be a long line of Cracker entries in the POTM...

I could not find any field for program length, so I put the length 
(30 program lines) in the title. I try to write code that is 
lightweight but performs at a reasonable level.

I briefly toyed with the idea of using a name that was a command string 
that would transform itself into something clever, however the KEYSTROKES 
language cannot execute itself (instructions are lower case, data is uppercase).

Where do you live?
Canberra, Australia.

work?
Computer scientist.

What do you do for fun?
Play with my kids, cook, dine out with my wife, write python, build robots, 
lose at computer strategy games, automate my house, and play 
badminton.    (and enter POTM challenges!)

Family?
Wife (who puts up with my technology interests), 3 kids (who play with 
technology), and cat (who couldn't care less).

Describe briefly the strategy Barbara_Blackburn used for KEYSTROKES:

  Like everyone, I started off with the trivial "replace the entire line".

  Next iteration was to take note of identical starting strings in
  both the START and TARGET lines and move the cursor to the first
  non-matching letter most efficiently and THEN replace the rest of the line.

  Next step was to notice matching substrings later on in the line
  and cease the adding of letters and rather move the cursor to the right


If I had it to do all over again, here's what I'd try:

  The next steps ... which I never quite got to ... were to have been:
  
  Looking ahead on the same line for substrings and being more efficient
  about when to type in new letters and when to move the cursor.

  In my dreams, my efforts moved vertically as well as horizontally -
  but only in my dreams.  My solution remained a one-line-at-a-time solution.


I named my KEYSTROKES entry "Barbara_Blackburn" because ...

  she is the "world's fastest typist" ... 212 words per minute peak using
  the Dvorak keyboard (rather than the more common QWERTY keyboard).
  http://en.wikipedia.org/wiki/Dvorak_Simplified_Keyboard 


Where do you live?  work?  What do you do for fun?  Family?
  Still New Jersey.  Still working for AT&T (although now as a contractor).
  Still doing the POTM and playing Everquest II (Gneen on Antonia Bayle).
  Married off another kid (my son May 13th) ... two down and one to go!

Describe briefly the strategy GapAlign used for KEYSTROKES:

I used a dynamic programming edit distance for each line to define what 
operations need to be made for that line.  Then used simulated 
annealing to optimize the order of operations.

If I had it to do all over again, here's what I'd try:
Spend more time on it...

I named my KEYSTROKES entry "GapAlign" because ...
Used similar algo in DNA alignments.

Where do you live?  work?  What do you do for fun?  Family?
Laurel, MD.

Describe briefly the strategy SkeletonSculling used for KEYSTROKES:
  
My algorithm is based off of levenshteins edit distance, starting at 
the beginning of the string and working to the end.  However since 
levenshteins algorithm only uses insert, delete, and copy or replace, 
it has been modified to a network with each position in the matrix as 
a node.  The valid arcs are then determined for append, right, delete, 
end, and deleteend (I was not able to get the rest of them working).  
The Dijkstra's shortest path algorithm is used to determine the minimum 
edits for that line.  This algorithm is fairly limited because it does 
not take multiple lines into account - next pass maybe.

If I had it to do all over again, here's what I'd try:
  
Quit my job, so I would have more time to spend on keystrokes.

I named my KEYSTROKES entry "SkeletonSculling" because ...
  
Skeleton is a type of key and stroking is something you do in 
sculling (rowing). It just gave a nice image of several skeleton's 
rowing with a coxswain yelling "stroke, stroke, stroke".

Where do you live?  work?  What do you do for fun?  Family?
  
I live in Longmont Colorado, USA.
I work at StorageTek.
Programming problems
1 Wife, no kids.

Describe briefly the strategy VinzClortho used for KEYSTROKES:

Erm, delete everything and write out the correct text.
Unless a line is already correct, in which case leave it.

If I had it to do all over again, here's what I'd try:

To find more time to have a go at a non-trivial solution.

I named my KEYSTROKES entry "VinzClortho" because ...

Its the name of the keymaster character in Ghostbusters.

Where do you live?  work?  What do you do for fun?  Family?

Live and work in Edinburgh. Guess I do this sort of thing for fun. 
Getting married in less than two weeks.

Describe briefly the strategy Dvorak used for KEYSTROKES:

- The program uses a very simple strategy. It deletes all lines 
and fills it with the correct keys.

If I had it to do all over again, here's what I'd try:

- Start early. Because of a late start I did not have enough time 
to finish a better strategy.

I named my KEYSTROKES entry "Dvorak" because ...

- I am using  a logical Dvorak keyboard layout.

Where do you live?  work?  What do you do for fun?  Family?

- The Netherlands.
- Yes.
- Playing with the "Fly! 2K" flight simulator.
- Married.

Describe briefly the strategy SuperEditorPlusExtremeGOLD used for KEYSTROKES:

    I submitted this entry as sort of a baseline. It uses what I 
    consider to be the most naive method to solve the problem: 
    simply delete the entire line and type in the new line.
    Move to the next line, and repeat. 

If I had it to do all over again, here's what I'd try:

    Well, there are obviously many ways to approach this problem. 
    I'd probably modify one of the algorithms existing that can mutate 
    a word like 'SOCK' into 'RACE' by changing one word at a time 
    ('ROCK', 'RACK', 'RACE') and see if I could use it to find the 
    least amount of changes to transform the source line into the 
    target line. Then try and optimise those changes to the 'editor' commands.

I named my KEYSTROKES entry "SuperEditorPlusExtremeGOLD" because ...

    All the other program names were boring and uninspired, at least 
    when I submitted it. Also, the irony of naming a naive algorithm 
    with such a flashy name appealed to me.

Where do you live?  work?  What do you do for fun?  Family?

    I live and work in the outer suburbs of Chicago. For fun, I train 
    for the triathlon, play computer games, read, and spend as much 
    time as possible with my girlfriend.

Describe briefly the strategy itwontwork used for KEYSTROKES:

My 1st version, does a full delete & insert, has no optimisation, it won't win!

If I had it to do all over again, here's what I'd try:

Submit my 2nd version (if it ever gets finished), ie start earlier.

I named my KEYSTROKES entry "itwontwork" because ...

For a surprise.

Where do you live?  work?  What do you do for fun?  Family?

Auckland.

Describe briefly the strategy kyestroks used for KEYSTROKES:

I took the very simple approach at first - just delete and replace lines.  
Then I tried to get fancy with a Levenshtein distance algorithm. 
Then life intervened and I went back to the simple approach just 
to get a working entry. 

If I had it to do all over again, here's what I'd try:

Win the lottery, quit my job, only program for fun.

I named my KEYSTROKES entry "kyestroks" because ...

It is the name of the contest and it's sort of punnish. 

Where do you live?  work?  What do you do for fun?  Family?

I live on the north side of Denver (Westminster) and work on the 
south side (Englewood.)  I'm learning to fly as we plan to move 
to Alaska in about 4 years or so when my youngest finishes high 
school and the life of a bush pilot is how I want to finish off my life. 
I recently became a grandfather for the first time on the 24th of April.

  Describe briefly the strategy scamEx used for KEYSTROKES:

The planned strategy, which is not yet fully implemented one week 
before the deadline, is as follows:

1) Working line by line, determine long common subsequences of the 
source and the target. In other words, find sets of letters that 
do not have to be changed.
2) From this, derive necessary replacements in each line.
3) Arrange the replacements in such a way as to minimize necessary 
move instructions.
4) Time permitting, try several sets of subsequences.
5) Compile the sequence of replacements into KEYSTROKES instructions.

  If I had it to do all over again, here's what I'd try:

Start earlier, and start working in Ruby right away. I'm new to this 
language, but I love it!

  I named my KEYSTROKES entry "scamEx" because ...

... because ScamEx Can Accelerate My Editing Xperience. Or, if 
you're sick of self-referential acronyms, it's the name of 
my favorite editor, read backwards. :)

  Where do you live?  work?  What do you do for fun?  Family?

I live in North-Eastern Germany and currently teach Math, CS, and 
Physics at a high school. However, I'm looking for a new job in 
development or academia.

I'm married, and we have a little daughter of 11 months.

For fun, I obviously try to design weird algorithms to solve academic 
problems and to implement them in object oriented scripting languages... 
Other than that, I like billiards (pool, snooker), volleyball, 
rollerblading, and movies.

Describe briefly the strategy Nerd_Perfect used for KEYSTROKES:

I first find the edit distance (Levenshtein distance <- thanks Michael, 
I never knew the proper term for it.) of each line, without considering 
the '<' or '>' edits.  Then I progressively chop off the beginning 
and end of the lines and check the edit distance again to see if '<' 
or '>' helps.

From that step, I gather a list of edits which contain the changes 
and the locations of those changes.

I then do an asymetrical Travelling Salesman Problem (ATSP) algorithm 
to find the shortest path between the edits.  It's not a true TSP, 
as the final point does not loop back to the first (starting point 0,0).  
I start with a random path, then try reversing subpaths until I find 
one that's  shorter.

It's sort of like a 2-Opt.  I do the random path & improvement thing 
10 times and save the bestest one.

If I had it to do all over again, here's what I'd try:

Answer Checker:  I would have created an "answer checker" sooner.  
For some dopey reason, I just assumed that since my program produced 
correct output on smaller problems that I could test by hand, then my 
program was producing correct output on all the problems.  When I 
submitted with 3 days to go, I realized that I needed to doublecheck 
my answers.  It took me all the way until 30 minutes left to go before 
I at least got all 5 system test solutions working correctly.  
Obviously there was still a bug, as 2 of the final solutions failed.  :(

TSP:  I need to have a better way of solving TSP problems.  I've 
encountered these a few times in past POTMs or other programming 
contests and each time I work it like I've never seen it before.  
I should have a favorite (good) TSP algorithm ready to use.  I 
read and re-read the Lin-Kernighan descriptions that I've found 
on the internet, but haven't been able to figure out how to implement it.

Testing:  If I had more time and a working solution, I would have liked
to have generated more test cases.  Okay, _any_ test cases. :)

Levenshtein Distance:  I implemented the Dynamic Programming (DP) solution 
to find the edit distance, but I couldn't figure out how to implement 
the dynamic costs that should have been included (such as the 3+2+2+2... 
for adding a string with multiple characters, or the extra cost at the 
beginning of a line, which I thought should be 5 to account for the 
extra movement and delete that was necessary).  I need to understand DP better.

Java:  I wish I could code the POTM in Java.  I learned Java in order to 
compete in TopCoder, and haven't been programming in C++ for a while.  
I'm a bit rusty and had to do some string/character manipulation the hard way.

I named my KEYSTROKES entry "Nerd_Perfect" because ...
It's a pun off the old "Word Perfect" editor that used to be the 
leading document editor.

Where do you live?
Houston, TX.
Work?
Houston, TX. (NASA Johnson Space Center) What do you do for fun?
Programming Contests - POTM (I'm glad Fred's back!), TopCoder (lot's of 
time pressure!), Al Zimmerman's (might be starting back up) Computer 
Games - KOTOR, Riddick, HL2, BF1942 TV, Movies, - the usual.
Family?
My wife, Marianne helps me with the naming ideas and is always super-supportive.
Our cats, who haven't been as forthcoming with ideas, and tend to lay on 
the keyboard and jab at the mouse.  Our dog, who's eyesight is failing and 
barks at invisible kids to keep them off our lawn.

Describe briefly the strategy Abracadabra used for KEYSTROKES:

1) searching matches of line parts and making patterns
2) making operations in according to patterns
3) iterating through list of operations to find the shortest chain of them

If I had it to do all over again, here's what I'd try:
I'd try to think more

I named my KEYSTROKES entry "Abracadabra" because ...
Just look at input file :-)

Where do you live?  work?  What do you do for fun?  Family?
Russia

Describe briefly the strategy PHP_Editor_php used for KEYSTROKES:
If I had it to do all over again, here's what I'd try:

Not sure what other approach to take. I hit a dead end on the approach 
used in the entry, and couldn't figure out a better way.

I named my KEYSTROKES entry "PHP_Editor_php" because ...

I have no imagination. :)

Where do you live?  work?  What do you do for fun?  Family?

I live in Utah, and work for a small company, maintaining their websites, 
and setting up new ones. I also do server admin work on the side for a 
few people. For fun, I play EverQuest and FFXI, and read books. 
I'm married, with no kids.

Describe briefly the strategy test_first used for KEYSTROKES:

To first find matches between the source and target. Then to build 
a graph of the possible solutions. I'll make the code public if you'd like. 
I had to drop out at the beginning of the month because of personal 
time constraints.

If I had it to do all over again, here's what I'd try:
I think I was on the right track.

Where do you live?  work?  What do you do for fun?  Family?
My wife and I live in the White Mountains of Arizona. We have a 
software company, here is our product:  http://reserveanalyst.com

I like to program for fun. :)