I've reached a dead end in my algorithm

  • Thread starter Jamin2112
  • Start date
  • Tags
    Algorithm
In summary: I don't know how you're storing these steps, but just make sure the function knows to print them)The base matrix could be [d u d e 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] (20 values)Why not use a dictionary instead of a matrix? It would make it easier to access the values and compare them. Plus, you wouldn't have to worry about a predetermined size for the matrix.In summary, the conversation discusses the creation of a function that takes in two strings and prints out the necessary steps to transform the first string into the second string. The allowed steps are adding a character
  • #1
Jamin2112
986
12
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.)
 
Technology news on Phys.org
  • #2
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.
 
  • #3
jbunniii said:
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.
 
Last edited:
  • #4
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
 
  • #5
Travis_King said:
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.
 
  • #6
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
 
  • #7
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
 

Related to I've reached a dead end in my algorithm

1. What does it mean to reach a dead end in an algorithm?

Reaching a dead end in an algorithm means that the algorithm has run into a situation where it cannot proceed any further, usually due to a lack of information or incorrect logic.

2. How can I tell if I've reached a dead end in my algorithm?

If your algorithm is not producing any results or is stuck in an infinite loop, it is likely that you have reached a dead end. Debugging tools and step-by-step tracing can also help identify dead ends.

3. What are some common causes of reaching a dead end in an algorithm?

There are many potential causes, but some common ones include missing or incorrect input data, flawed logic or algorithms, and insufficient or conflicting constraints.

4. Can I fix a dead end in my algorithm?

Yes, it is possible to fix a dead end in an algorithm. This often involves identifying and addressing the root cause of the dead end, such as correcting errors in the input data or adjusting the algorithm's logic.

5. How can I avoid reaching a dead end in my algorithm in the future?

To prevent reaching a dead end in your algorithm, it is important to carefully plan and design your algorithm, thoroughly test it with a variety of inputs, and continuously monitor and debug as needed. Additionally, seeking feedback from others and utilizing best practices can help avoid dead ends.

Similar threads

  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
7
Views
2K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
4
Views
1K
  • Programming and Computer Science
Replies
2
Views
2K
Back
Top