Rearranging Words

Question

You should write a program which receives two strings as input and outputs a sequence of movements which rearrange the first string into the second. You should use as few moves as you can.

Both strings will contain only lowercase letters and the second (goal) string is a permutation of the first (original) one.

Every move is described as char_index:direction where

• char_index is the 0-based index of the character in the original (first) string
• direction is one of u d l r corresponding to moving the selected character one step up, down, left or right.

You can only move a character to another position if no other character is there. The grid on which you can move the characters is infinite in every direction.

Your goal is to rearrange the letters of the first string so they take up the same area as at start but spell out the second string.

For example a valid move sequence for abc => acb would be 2:d 1:r 2:l 2:u (4 moves):

| abc | ab  | a b | a b | acb | 
|     |   c |   c |  c  |     | 

Another move sequence for the same input is 2:r 2:d 1:u 1:u 1:r 1:d 1:d 2:l 2:l 2:u (10 moves):

|      |      |      |      |  b   |   b  |      |      |      |      |      |
|      |      |      |  b   |      |      |   b  |      |      |      |      |
| abc  | ab c | ab   | a    | a    | a    | a    | a b  | a b  | a b  | acb  |
|      |      |    c |    c |    c |    c |    c |    c |   c  |  c   |      |

Input

• Two strings (original and goal string) containing only the letters [a-z].
• The two strings are separated by a newline.

Output

• A space separated list of moves.
• Each move has the format char_index:direction as described above.

Scoring

• Your score is the total number of moves your program uses on the test case inputs. Lower score is better.
• In the event of a tie the earlier submission wins.
• Your submission is valid only if you ran your program on all the test cases and counted your score.
• You can validate your solutions with this python program. Provide input and output filenames as arguments or input and output as stdin (2 lines input and then 1line output).

Test cases

(Test cases are delimited by empty lines.)

ehmwgzcyoaedeyvckivf
chacfveyvwdeyoigezkm

ymnrpltwdyvlgdrgndgx
ggydpnrwgrdyvtnmldxl

gfceetyxotezibswjcdh
oeefgjciehyxswtcdbtz

qdjqiffrqokkitndmufl
oqfrmfudqktikfjqilnd

sxgsugcylgsfgznrktgp
cgsylsgnggkzurgptfxs

izzbcpvwpkackqykurghocpptmbtfcdorlmterhyellurudblqlbldaheorilrfzoonicbfwksdqjjeujvqluktamaurafberdcua
lwrkcbnlllycaorcfklebodkrjuapdbdforulqosofieeqcpzaebuqmuthdurvtpkbmageurlzbiwkaymcvctfhuzprajtlrqjdih

wdbyrdzneneydomipmrjoposrgjvdwmeijrnozapnroqtnayqbfdiojnddcijpdkkmglrwktpsyaoctpenqbmcooksjpeqfrjkgym
wamcedyibsopqckcrdomrzgpirmfrdmdqonmyknpgrbnbkdotrejonyelioaqoksoinzgprtwfednvpjsntjdyoadkwyjjjqpjepm

bwfgxpbxiztsasxkhvdwuhtylvzcmctwxfjahbnbbolcbysbtxfmmrlvptqpvrxfbvfoqjwgrsarvngvigmixlcfpvqyrhcddjiyv
qpjbwvrvgbccptmwxofuqvvltpxacrsanwcmjbkolyhjzbithyqhvxfrsttdmzdbilmhvrfcwrvafygipgbvfnblxvxsybfgsxdxi

gozvqtqxmpjqjftuvbaevdkmjtzylyyjsryfahzsotygxsuzihfwfzfmrvvcaqejpkjqzxyzeoxotdabpmmbknycvvkqlpxpkfory
jvaboapseayzbymyjfvkrozyutvqqsjfxjxfqnttuvejyhqiqzctlfkyxrcmvxjmdooksdvyzrlhpakpbfpzfpgvkgmyzzqmtoxew

ishatpmxygjhxnndyzmmhpjregfmdvtfstgiojcxbstwcghtuckftwrwchepgojxkfgwnynximhnnovhdytmrtiugcmzkwweuudoi
fekopnynwgjvyojnizxcxmustpihhursiwhdhegrcgtkimxutmbgfchoeawmdmwfpkwwyhxdnftthsiuzmtmgtcjvngntrcoxydgj

ehigvxohaivehtdemdjofhkjrxtzsukaccxzyjpufyspfokjxkxztrcmchykhiwfnsgibnjfagntdowkpcogndrafknymzsrkqnelkfrfoltkhfvrwguwpgbkwovfyqpnzmagiakbaduurkgsdeylqemfjklglybdihxptzzxcffqqfoykfrtexhqxdpuwnqjwrnyugkrghwvazaihvjtofrcympsvgaeuorctqmabkokqmwraifdwmphxbbdqjm
gyotpajrrtelqgfezwacfvsinulknmzfpfrplwjxzawkarxkgiookfokjvxbhdqcphohcqmxfdwxksohgrhybzhtrfeksrqedznggxxfamjorwyomaqnliyapdnhvypfkzcdyjknnyxstpyrvggmhxcwrbpfguomksffqyrzhrcmukqaaabaehugifowtpdxiakuhtowvwttnkdbcjtuzfvueieukgdkmfncfwbmjkkdisblrkmhyigqfqvejjqd

lbudhpvhdrlsqmwhsrlzozowdkpesrawprfoqdilpcacboqdxbohnpgeogcqtlhruidvytylckgpdfnfqqvstivzkduttqjgfifcglhajmnzithbyzohiviwuudohppebyqnvhogsqwtywyfegkryxpjphoipiunnhfsbkdsieoqyebluppatgsawnwsaieujsxmanysxcdmjvvymcbqsxiqlihxidajwqrthhjhfncwoxmwumguvhtvxjtgoimd
tqzgsaafjtieekfrsjmxcvqshtxlyltqyoqwdwwowlszlhktiovciigewsdpwxcnhgglwmslcjinnsluxsooimkrpuytupgohfhycdpvcmshxfebqcxpaodiawfsgbwhqahdnvnrvmtqiddmjopdtxhvbwgqvhaihhhkiwjxfnidertpujupoiqrspavyjcqguhdedbpzhnyhhjbuiytqorrgypbbinslmfyqvpykziatulogfdmdqbunpeuzvoo

ryhphfyvyzgaabyqjyjhbsfixgxwdubtlljgjlmzlrbnsmkvjuxgszafnayywvrcbwmttocfppxhbjcqpvyunxkfvinfhnozgvolcowbcppvejiiljiagdmwxvrsblzxsyrsnaivkbnffdduwzkgtpvhmbxavzdcrhpxhnzzcupmekvufvfcfpxnqyoiruofwddwjzihffuvmfeyelwevqbjtsrkujalsambaepbajziptrujjorwhcozmegohho
fafdfvzedydrkyuudnngnzftohdwjrcvyfbtdwbjcmapgmeffpxicrvjuhszpvpplcrqkojvwbatngxizzkrdaehovampctaptrjgsyubawbvuirkvmzoziyozhbhurnflqmplsbhhhllhbxswrxbflxyylruyoftvpwephjowzaiajfehgkyiyobgxemobmjopmnufwswjxpqbsanjjficcmqvxzvfilucbjhcvuwenxzlsvvsxfznyvkjgjagi

zpsnvzghldshvllfrnwjwltecaopsuuucrnsjggcsirymywtmdzpmdoqylbtjavdtvwviohvjtldjdwjoumffmzjjmltcjqtjsryualzqfjdrcunbmquirqcdpcedlyznzkgtrpxldelkmogiutyfjwntjvzfmowcjzlnrivtlajrpowkxykbsxzvhsahsigobkunfxashtcbqmepiyhbuuyfwrbfoknivocyivznnethpcbmztyxfvekqfejcfe
oyetfwkgskcygvszugygtumojmljdcrhnlljgomnrzubcjjlcnyzvzfuyshdchxytbiljjirvvxdkfosfuitdedocwlnsmjmbemowpftabyltjumlwfzfufkurozzichcqwkqasdnimvdbdsjfpmhrkhlnzisvjpapmyrwedcgmudtqtjvtqwluawtqviktxnzyirlspqbnthfxtapbescjvcbohyqejfialrznrojnlfeevxrnpzczvtvyojupw

hhhhyyvnnbqgmiiaaabzoamiudppplwhmjkwjxstcgzprhjknhijcpqqwmcpkbzlngugifmdzyclsokhgogtntheztvwmugitijbmukjllxsgcazdwlfwyzhbkkvhdllfzhpnltfbbijcrpxyjpupqifevxxfbhzqjfjqfgadwgumqxkcocugjdwxkhorjsspdswqlzsdobtjeucpbfthumsscmfwkovwljvunikttgcgcawsevmlfhcpeupwazs
pdqpkzdfmlkjqagwmkyohwdkbchinefzcjmsngxbuptsultmytgagjkfvkscjdlswuujbrachvspfmlfgwplqfipeaobiiupghyoxeswuqschtrccwzpijcbotklzjmtvhgljfzerujmafwvphuhkcfhixacjalxjhlsxshzzdgwiqopxmdvtwhkfzwbgfsknvmgwthogbbvtphuwyqpmtpuqcobwkjihisldelcphylajcdigqbxunzjnmgznnz

Answer 1

CJam, 58,598 58,494 57,898 57,772 57,704 57,680 moves

This approach takes the family of all unordered sets of horizontal moves of minimum cardinality (with some false positives) and adds the minimum number (over all sets) of vertical moves required to avoid superpositions.

If the resulting number of horizontal moves is suboptimal (a false positive), it starts adding more vertical moves until the number of horizontal ones is optimal.

Finally, it orders the generated moves to form a valid sequence.

Try it online in the CJam interpreter.

Animated test cases

Test case 1 | Test case 2 | Test case 3 | Test case 4 | Test case 5

Test case 6 | Test case 7 | Test case 8 | Test case 9 | Test case 10

Thanks to @Doorknob for his help with the animations.

Test cases

$ time for f in xx*; do python3 val.py $f <(cjam prog.cjam < $f); done
move sequence verified with step count 156
move sequence verified with step count 126
move sequence verified with step count 120
move sequence verified with step count 124
move sequence verified with step count 112
move sequence verified with step count 2228
move sequence verified with step count 1862
move sequence verified with step count 2066
move sequence verified with step count 1738
move sequence verified with step count 1932
move sequence verified with step count 8200
move sequence verified with step count 10770
move sequence verified with step count 10360
move sequence verified with step count 8716
move sequence verified with step count 9170

real    0m22.672s
user    0m37.372s
sys     0m1.869s

Pairing characters

Let's analyze the following example (provided by @randomra):

012345678
axabababa
abababaxa

By inspection, it suffices to swap the x with the b that takes its place, which can be done in 16 moves:

1:u 1:r 1:r 1:r 1:r 1:r 1:r 7:d 7:l 7:l 7:l 7:l 7:l 7:l 1:d 7:u

The minimum number of horizontal moves can always be achieved by pairing the n^th occurrence of each letter in the first line with the n^th occurrence in the second line. However, this is highly suboptimal in this case, since we have to add too many vertical moves to avoid superpositions.

The letter x occurs only once and there is only one optimal choice for pairing the as, so we already know which horizontal moves will be required to get them to their targets.

However, the letter b is trickier:

012345678
   b b b 
 b b b

Pairing the bs in order would require moving either the bs itself or the as between them either up or down, since no b can take the place currently occupied by an a.

The right choice is to pair the b at index 7 of line 1 with the b at index 1 of line 2 and not to move the other bs at all. We'll refer to the pairings by their initial and final position, which are [7 1], [3 3] and [5 5] in our example.

But how to find these pairings? In theory, we could just go through all sets of possible pairings for each letter and select the set that requires the least amount of total moves. However, for a letter that occurs n times, there are n! possible sets of pairings, which is impractical.

In this approach, we determine all possible pairings of two letters that, by themselves, won't increase the number of horizontal moves. To achieve this, we take all possible pairs of letters of lines 1 and 2 and, if the letters are the same, replace both by an underscore and determine to number of moves needed to move n^th occurrences to n^th occurrences.

For our example, this yields the following:

[0 0] [1 7] [2 2] [3 1] [3 3] [4 4] [5 1] [5 3] [5 5] [6 6] [7 1] [7 3] [7 5] [8 8]

As we already knew, the letters at indexes 0, 2, 4, 6 and 8 (the as) should not be moved horizontally and the x has to move from index 1 to index 7.

For the bs, there are several choices to be considered. The b at index 3, for example, can move to index 1 or index 3.

To minimize the number of vertical moves over all possible sets of pairings, we select as many non-overlapping pairings as possible, since moving the corresponding characters to their destinations will require no vertical moves at all.

Finding these proper pairings is a variant of the longest common subsequence problem. and can be done as follows.

We start by replacing the letters of each line by their indexes:

012345678
012345678

The first column ([0 0]) is one of the precomputed pairings, so we select it and remove it from the lines.

We now have

12345678
12345678

The pairing [1 1] is invalid (x would stay in its position). We now remove the first element of the line 1 and the first element of line 2 (not simultaneously) and apply the process exemplified above to

2345678
12345678

and

12345678
2345678

The higher amount of pairings resulting from the two choices will get appended to [0 0].

Thanks to memoization, CJam completes this recursive process almost instantly.

For our example, this selects the following pairings:

[0 0] [2 2] [3 3] [4 4] [5 5] [6 6] [8 8]

This way, all letters except the x and the b that takes its place won't have to move at all.

Moving characters

Consider the input

0123456789AB
xaxxbycydyye
yyabcydxxxey

for which the moves

[1 2] [4 3] [6 4] [7 5] [8 6] [10 11]

get selected. The corresponding characters won't have to move vertically and we can pair the remaining characters in order.

To implement the pairing, we use the same algorithm we have already used to determine the minimum number of horizontal moves.

We start by replacing characters corresponding to selected pairings with underscores:

0123456789AB
x_xx_y___y_e
yy_____xxxe_

Now, we enumerate each character's occurrences on both lines:

['x 0] ['_ 0] ['x 1] ['x 2] ['_ 1] ['y 0] ['_ 2] ['_ 3] ['_ 4] ['y 1] ['_ 5] ['e 0]
['y 0] ['y 1] ['_ 0] ['_ 1] ['_ 2] ['_ 3] ['_ 4] ['x 0] ['x 1] ['x 2] ['e 0] ['_ 5]

Now, we compute the indexes of all pairs in both the second and first line:

[0 7] [1 2] [2 8] [3 9] [4 3] [5 0] [6 4] [7 5] [8 6] [9 1] [10 11] [11 10]

As before, the pair [0 7] means that the character at index 0 has to move to index 7.

We eliminate the pairs that had been selected been selected before and examine the remaining pairs:

[0 7] [2 8] [3 9] [5 0] [9 1] [11 10]

We divide these pairs into two groups, differentiating between characters that move left and those who do not:

[0 7] [2 8] [3 9]
[5 0] [9 1] [11 10]

Now, we move each character from the second group one unit up and then right until it is below its target. To avoid superpositions, we sort the characters by their final positions (rightmost comes first).

Similarly, we move each character from the first group one unit down and then left until it is below its target. Again, we sort the characters by their final positions (leftmost comes first).

With the vertically moving characters out of the way, we can move the characters of the firstly selected pairs to their destinations.

We already know how many times we have to move each character in which direction; what is left to figure out is the correct order of these moves.

There are several ways of doing this. My implementation simply removes all characters that are already at its destination, moves each character one unit towards its destination if that position is not occupied and repeats the process.

For the pairs

[1 2] [4 3] [6 4] [7 5] [8 6] [10 11]

this gives the following move order:

1:r 4:l 6:l 10:r 6:l 7:l 7:l 8:l 8:l

Finally, we move each character that has moved vertically one unit down or up to reach its destination.

False positives

A cornerstone of this approach is the way it differentiates "good" from "bad" pairings. A good pairing, by itself, won't increase the number of horizontal moves.

However, we select several of these pairings to minimize the number of vertical moves. Certain combinations of good pairings can increase the number of horizontal moves, leading to suboptimal results.

The following example illustrates this.

01234567
a a a
   a a a

For this input, we obtain this list of good moves:

[0 3] [0 5] [0 7] [2 3] [2 5] [2 7] [4 5] [4 7]

Indeed, neither [0 5] nor [2 7] is a bad move by itself.

However, if both moves get selected, we are forced to use the paring [4 3], which is a bad move since a goes in the wrong direction.

We define a false positive in the selection of pairings as a set of good moves that force us to select a bad one later.

These false positives seem to be rather uncommon. Of all fifteen test cases, there was only one false positive.

In the eleventh test case, the distribution of the letter h is the following:

 h     h    h        h                                   h  h                                                h                                                    h                    h                  H      H                                      h       
                                                            h    h h           h  h   h                                    h                        h                   H            H              h                                              h            

The uppercase Hs highlight two good pairings that both get selected and cause the hs between them to make a bad pair.

For the general case, we'd either have to avoid these false positives during the selection process or remove the good pairs that caused them afterwards and repeat the selection.

For the test cases, it suffices to proceed as follows:

1. After selecting all pairings, count the number of horizontal moves we have to make.

2. If it is suboptimal, remove each pair of the selection and recount.

3. If the number of horizontal moves is optimal after removing one of the pairs, remove it permanently.

4. If no pair can be removed to achieve the minimum number of horizontal moves, give up and keep all original pairings.

Step 4 is never reached for the test cases.

Code

[l:Al:B]    e# Read two lines from STDIN and store them in A and B.
{           e# Define a function:
  {         e#   Define a function:
    {       e#     For each line:
      :Lee  e#       Save the line in L and enumerate its characters.
      {     e#         For each pair (index, character):
        ~_  e#           Dump the pair and copy the character.
        @L< e#           Cut L off at that index.
        e=  e#           Count the occurrences of the same character to its left.
        a+  e#           Push the pair (character, occurrence).
      }%    e#         This turns "aba" into [['a 0] ['b 0] ['a 1]].
    }/      e#
    f{\a#}  e#     Push the indexes of the pair of line 1 in line 2.
    ee      e#     Enumerate them.
            e#     This turns ["aba" "baa"] into [[0 1] [1 0] [2 2]].
  }:I~      e#   Name the function I and execute it.
  ::-:z     e#   Compute the absolute difference of each pair.
  :+        e#   Add those differences.
}:C~        e# Name the function C and execute it.
            e# C counts the minimum number of horizontal moves to get each
            e# character to its destination.
:O;         e# Save the result for the original input in O.

A,2m*       e# Push an array of all pairs of non-negative integers below len(A).
{           e# Filter those pairs:
  :P[AB].=  e#   Save a pair in P and select the corresponding chars of A and B.
  :=        e#   Check if the characters match.
  {         e#   If they do:
     [      e#
       AP0= e#     Push A and the first index of P.
       '_t  e#     Replace the corresponding char of A with an underscore.
       BP1= e#     Push B and the second index of P.
       '_t  e#     Replace the corresponding char of B with an underscore.
     ]      e#
     C      e#     Execute C on the modified lines.
     O=     e#     Check if the minimum over the modified lines matches O.
  }         e#
  0?        e#   Else, push 0.
},          e# If the result was 1, keep the pair.
:M;         e# Save the result in M and pop it form the stack.
            e# M contains all possible pairings of characters of line 1 and line
            e# 2 that do not increase the minimum number of horizontal moves.

[A,,_]      e# Push the array [[0 ... len(A)-1][0 ... len(A)-1]].
Q{          e# Set up a memoized recursive function j:
  _:e&      e#   Check if if both arrays are non-empty.
  {         e#   If they are:
    _0f=:P  e#     Retrieve the first element of each array and save in P.
    M\e=    e#     Check if P belongs to M.
    {       e#     If it does:
      Pa\   e#       Push [P] and swap it with the arrays.
      1f>j  e#       Remove P from the arrays and execute j.
      +     e#       Concatenate [P] and the result of j.
    }{      e#     Else:
      _2,W% e#       Copy the arrays and push [1 0].
      .>    e#       Vectorized tail. Removes the first element of array 1.
      j     e#       Execute j on the result.
      \2,   e#       Swap with the arrays and push [0 1].
      .>    e#       Vectorized tail. Removes the first element of the array 2.
      j     e#       Execute j on the result.
      _,2$, e#       Push the lengths of both results of j.
      <@@?  e#       Select the longer array.
    }?      e#
  }{        e#   Else:
    ;Q      e#     Remove the arrays and push an empty array.
  }?        e#
}j          e# Execute j on the initial arrays.
            e# This pushes a set of non-overlapping pairings of maximal size.

W\+W+       e# Prepend and append -1 (dummy value) to the pairings.
:G,,        e# Save in G and push [0 ... len(G)-1].
{           e# Find in G:
  G\Wt      e#   Replace the element in G at that index with -1.
  W-:H      e#   Remove all -1's and save the result in H.
  z         e#   Zip the array of parings. This groups the indexes of the first
            e#   line in one array and the indexes of the second line in another.
  [AB]\     e#   Push the array of lines.
  .{        e#   Vectorized foreach:
    {'_t}/  e#     Replace the corresponding characters by underscores.
  }         e#
  :T        e#   Save the result in T.
  CO=       e#   Count the minimum number of horizontal moves and compare with O.
}#          e#   Stop if they match.
;           e#   Discard the index returned by {}#.
            e# This saves G itself in H if the number of horizontal moves was
            e# already optimal and discards at most one element of G to achieve
            e# optimality. T now equals [A B], where characters that will 
            e# move only horizontally have been replaced by underscores.

TIH-        e# Execute I on T and remove the elements from H.
            e# This pairs all characters that will have to move vertically.
{           e# Sort by the following key:
  _1=       e#   Retrieve the second element (index of line 2).
  \:>       e#   Push 1 if the index of line 1 is bigger than the one of line 2.
  2*(       e#   1 -> 1 and 0 -> -1
  *         e#   Multiply by the index of line 2.
}$          e# This sorts the pairings by direction, then final position.

{           e# For each pair [X Y]:
  _:>:D;    e#   Set D := 1 if X > Y and D :=0 otherwise.
  ~\:I      e#   Save X in I.
  ":d :u "  e#   Push that string.
  3/        e#   Split it into [":d " ":u "].
  f+        e#   Prepend I to both strings.
  Dm>       e#   Swap the order of the array's elements if D == 1.
  ~o        e#   Dump the array and print its second element.
            e#   The first element will be left on the stack. CJam will print it
            e#   after executing the rest of the program.
  \I-z      e#   Compute abs(Y - I).
  ":r :l "  e#   Push that string.
  3/        e#   Split it into [":r " ":l "].
  D=        e#   Retrieve the string at index D.
  I\ +      e#   Prepend I.
  *o        e#   Repeat the string abs(Y - I) times and print.
}/          e#

H{          e# For each pair in H:
  [         e#
    ~\:I    e#   Save the initial position in I.
    I@I-    e#   Subtract the initial position from the final position (D).
    _ga     e#   Push [sign(D)].
    \z*~    e#   Repeat the array abs(D) times and dump it.
  ]         e# 
}%          e# The result contains I twice, followed by abs(D) copies of sign(D).

{           e#
  {2>},     e# Filter out elements with length two.
  _         e# Push a copy.
}{          e# While the copy is non-empty:
  _0f=:P;   e#   Save the positions the elements currently occupy in P.
  {         e#   For each array:
    __,(%   e#     Retrieve the first and last element (position, direction).
    :+:J    e#     Add them and save the result in J.
    P&      e#     Intersect with P.
    {       e#     If J is not in P:
      _1=o  e#       Print the character's identifier.
      ':o   e#       Print a colon
      )0>   e#       Retrieve the direction.
      "lr"= e#       Push 'l' or 'r'.
      S+o   e#       Append a space and print.
      0Jt   e#       Save the new position in the array element.
      PJ+   e#       Append the new position to P.
      :P;   e#       Save in P.
    }|      e#
  }%        e#
}w          e#