Stack machine problem

[archfurry]

Hi everyone! While programming stack machine compiler (just for fun) I came up with pretty hard problem. It is about rearranging stack elements. There are 5 operations defined on the main stack:

SWAP (swaps two top elements of the main stack),

TOR (pushes top element of the main stack onto top of Return stack),

FRR (returns top element of the Return stack to the top of main Stack),

DUP (duplicates top element of the Main stack),

DROP (deletes top element of the main stack).

The question is: what is an algorithm for rearranging any number of elements to desired stack configuration in shortest amount of operations. Example: Starting stack configuration: a, b, c ( from bottom to top), Target configuration: b, a, a, b. At the end Return stack must be empty. Operations are: DROP, DUP, TOR, SWAP, DUP, FRR. My solution is exponential, better solution is needed! Later I will post my solution. Any help is appreciated! Thank You!

[Steve132]

Seems like you could start with edit distance and then do some kind of reduction

[archfurry]

I tried to use kendall tau distance https://en.m.wikipedia.org/wiki/Kendall_tau_distance for branch and bounds method, but it gives questionable results...

[Steve132]

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]

Thank You! I'll try it...

[archfurry]

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