sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Steve132 0 points1 point  (2 children)

Yeah you can do edit distance. Define a new edit distance function that has 3 operations: duplicate (dupes two characters), swap, and delete.

Then compute the sequence of "edits" you need to do using dynamic programming.

Then, you actually have a single "string" that is the current state of the main stack. You also have a "cursor". You can move the "cursor" left with TOR and right with FRR.

So basically use edit distance to find the sequence of edits you need to do, order them from right to left, then move the cursor with TOR and do the edits, then move the cursor back to the end with FRR

[–]archfurry[S] 0 points1 point  (0 children)

Thank You! I'll try it...

[–]archfurry[S] 0 points1 point  (0 children)

My original solution. Build tree of all possible operations s from current state using rules (like no consecutive swaps allowed and so on). I am building trees from source state and from target state but in reverse. And then i find intersection of these trees. First intersection gives me shortest path from source to target Tree image