I've reached a dead end in my algorithm

[Jamin2112]

I'm trying to write a function that takes as parameters two strings, textStart and textTarget, and prints out the steps necessary to transform transform the first into the second, with the allowed steps being:

(1) Add a character somewhere in textStart
(2) Remove a character somewhere textStart

I've reached the point in the algorithm where I've made maps for the characters that need removed and added. For instance, if textStart="dude" and textTarget="deck", then my procedure gives needAdded['c']=1, needAdded['k']=1, needRemoved['u']=1, and needRemoved['d']=1.

Now I need to use this information to figure out the proper removal and insertion steps. Let's deal with the removal steps first.

In the example above, 1 'd' needs removed -- the 2nd one of 2 'd's. But how can I design an algorithm to figure out which of the 2 'd's to remove?

For now, I'm just going to go ahead and write an algorithm that removes the first occurrences of letters that need removed, and adds at the beginning the letters that need added, before finally sorting everything.

(I understand the way of doing this with a tree and branch-and-bound algorithm, but I'm not using it. Maybe some other time.)

 

[jbunniii]

In addition to the considerations you mentioned, what if you need to add or remove more than one instance of a letter? E.g. to transform "dude" to "cake", you will need to remove both 'd's. How do you represent that? Is it needRemoved['d'] = 2?

Also, how do you represent a situation where the letters are all OK but need to be rearranged? E.g. transform "meat" to "team".

Finally, you need a better specification of what you are trying to achieve. One way to transform "dude" to "cake" is to remove 'd', 'u', 'd', 'e', and add 'c', 'a', 'k', 'e'. If that is not an acceptable solution, then define what is acceptable.

 

[Jamin2112]

In addition to the considerations you mentioned, what if you need to add or remove more than one instance of a letter? E.g. to transform "dude" to "cake", you will need to remove both 'd's. How do you represent that? Is it needRemoved['d'] = 2?

Yes, that's right.

Also, how do you represent a situation where the letters are all OK but need to be rearranged? E.g. transform "meat" to "team".

That's why, right now, my procedure is to get them to have the same letters and then sort the letters. In the situation you mentioned, needAdded and needRemoved would be empty and the function would move straight into the rearrangement process.

Finally, you need a better specification of what you are trying to achieve. One way to transform "dude" to "cake" is to remove 'd', 'u', 'd', 'e', and add 'c', 'a', 'k', 'e'. If that is not an acceptable solution, then define what is acceptable.

It's acceptable as long as we're removing/adding 1 letter at a time.

Since the point of this is to print out the steps, my hope would be that a call to transform_steps("dude", "cake") would yield something like:

Remove 2 occurrences of 'd's: "dude" --> "ue"
Remove 1 occurrence of 'u': "ue" --> "e"
Add 1 'c': "e" --> "ce"
Add 1 'a': "ce" --> "cae"
Add 1 'k': "cae" --> "cake"

That's the "smart" version that I'm still not sure how to make. I don't know how to make function know to put the 'a' between the 'c' and 'e'.

Again, I'm still in the planning phase of how to finish this off.

 

[Travis_King]

How are these items stored?

The easiest solution would be to set these up as a matrix so that a1=d, a2=u, a3=d, a4=e
Then, you can set your target as a matrix: b1=d, b2=e, b3=c, b4=k

If b1=a1, then leave a1 alone and print "current word: a1 a2 a3 a4", else set a1 = b1 and print "substitute (value)a1 with (value)b1" then print, "current word: a1 a2 a3 a4"
b1=a1, therefore print "current word: a1 a2 a3 a4" (at this point, it will still read D U D E"

If b2=a2, then leave a2 alone and print "current word: a1 a2 a3 a4", else set a2 = b2 and print "substitute (value)a2 with (value)b2" then print, "current word: a1 a2 a3 a4"
b2 =/= a2, therefore set a2 = b2 and print "substitute (value)a2 with (value)b2" then print, "current word: a1 a2 a3 a4"
(at this point the word will be "D E D E"

and so on

 

[Jamin2112]

How are these items stored?

The easiest solution would be to set these up as a matrix so that a1=d, a2=u, a3=d, a4=e
Then, you can set your target as a matrix: b1=d, b2=e, b3=c, b4=k

If b1=a1, then leave a1 alone and print "current word: a1 a2 a3 a4", else set a1 = b1 and print "substitute (value)a1 with (value)b1" then print, "current word: a1 a2 a3 a4"
b1=a1, therefore print "current word: a1 a2 a3 a4" (at this point, it will still read D U D E"

If b2=a2, then leave a2 alone and print "current word: a1 a2 a3 a4", else set a2 = b2 and print "substitute (value)a2 with (value)b2" then print, "current word: a1 a2 a3 a4"
b2 =/= a2, therefore set a2 = b2 and print "substitute (value)a2 with (value)b2" then print, "current word: a1 a2 a3 a4"
(at this point the word will be "D E D E"

and so on

Right, but if the words are of different length then some adding and/or subtracting of characters has to take place at some point.

 

[Travis_King]

Ok, well I don't know what programming language you are using (I probably couldn't help with the specific syntax if I did) but the way I see it would be:

You still use the matrix idea, but you make a base matrix of, say, 20 characters. a1, a2,...a20.
Set the values of each node to their respective letters and set the others to zero.
run the algorithm as normal and have in the loop a call out that says, "if An=Bn=0, stop the loop and print the resulting word

 

[.Scott]

Part of the problem is that, if the letters aren't in the same order, they don't count.

Here's my shot at it.
For example:
A: "different"
B: "traffic"

1) Create four "Remnant lists" Ar, Br, As, and Bs. Each element in these lists is able to hold a letter and a position.
2) Create a "Match list" M. Each element in this list is able to carry a letter and two letter positions.
3) Copy the letter and its position of every letter in word A that matches a letter in word B into Ar.

Result: Ar: i2 f3 f4 r6 t9

4) Copy the letter and its position of every letter in word B that matches a letter in word A into Br.

Result: Br: t1 r2 f3 f4 i5

5) Create two indices iA and iB, one into "Ar" and one into "Br" and set both of them to 1 - representing the first letter in each list.
6) Copy Ar[iA++] to the end of As (since As is empty, it will be the only element).

Current State:
iA:2; iB: 1; As: i2, Bs: empty
Note that iA is 20% used and iB is 0% used.

7) Judging from (iA-1)/sizeof(Ar) and (iB-1)/sizeof(Br), pick the list that is least used and copy the next character and position into the corresponding As or Bs list. If both are equally used, the choice is arbitrary - so move from Ar to As.

On the first time through, the state will be:
iA:2; iB: 2; As: i2, Bs: t1
Note that now both iA and iB are 20% used.

8) Compare the letter just moved in step 7, to each of the letters in the other As or Bs list.
9) If no match is found, and either Ar or Br still has unused letters, loop to step 7.
10) If a match is found, copy the information from the match from As and Bs to M.

On the first time through, the state will be:
Ar: i2 f3 f4 r6 t9
Br: t1 r2 f3 f4 i5
iA:4; iB: 4
As: i2 f3 f4
Bs: t1 r2 f3
M: (f,3,3)

11) Now remove the matching letters and all letters that preceded them from both As and Bs.

On the first time through, the state will be:
As: f4
Bs: empty
M: (f,3,3)

12) If there are still unused characters in Ar or Br, loop to step 7.

So, with "different" and "traffic" you get:
Ar: i2 f3 f4 r6 t9
Br: t1 r2 f3 f4 i5
Which is processed into:
M: (f,3,3), (f,4,4)

Although there are other matches, they are too far out of order to be used.

Since you're only keeping three letter from the original work, your first steps will be to remove letter. I would remove them from last to first:
remove #9: differen
remove #8: differe
remove #7: differ
remove #6: diffe
remove #5: diff
remove #2: dff
remove #1: ff

Now you would just build up the word "traffic":
add "t" to 1: tff
add "r" to 2: trff
add "a" to 3: traff
add "i" to 6: traffi
add "c" to 7: traffic