Transform a sequence using the fewest number of steps possible

Question

My question is, what algorithm should I use to implement a function translate that works according to the following Python examples:

>>> translate('aa', 'a')
[('S', -1)]
>>> translate('a', 'aa')
[('R', 0, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('abc', bca')
[('R', 0, 'x'), ('R', 1, 'y'), ('R', 2, 'z'),
 ('W', 2, 'x'), ('W', 0, 'y'), ('W', 1, 'z')]
>>> translate('abc', 'cabc')
[('R', 2, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('ab', 'bab')
[('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('abc', 'bcabc')
[('R', 1, 'x'), ('R', 2, 'y'), ('S', 2), ('W', 0, 'x'), ('W', 1, 'y')]

It's a generalization of a problem related to generating optimal code in a compiler that I'm having. The algorithm is what I'm after so the solution does not necessarily have to be in Python. In "reality" the variables ('x', 'y' and 'z' in the above) are machine registers and the string indices stack locations.

As you can see from the example, the algorithm is about transforming a string from one sequence of characters to another using the fewest number of steps. With the caveat that there are only three possible operations to choose from:

1. Shift the string to the left or right N number of steps. If it's shifted to the right, the new indices introduced are filled with ? characters. E.g ('S', 2) -- shift the string two indices to the right.
2. Read character at index into a variable. This operation cant be performed if there are any ? characters in the string. E.g ('R', 4, 'q') -- read the character at index 4 and store it in the variable q.
3. Write character from variable into index at destination string. The index must be within bounds. E.g ('W', 1, 'q') -- write the character in the variable q at index 0 in the string.

Here is trivial Python code to implement those operations and an example of how the transformation from ab to bab would be performed manually:

def shift(str, n): return str[-n:] if n < 0 else '?'*n + str
def read(str, n): assert not '?' in str; return str[n]
def write(str, n, ch): return str[:n] + ch + str[n:]

S = 'ab'
x = read(S, 1)
S = shift(S, 1)
S = write(S, 0, x)

This sequence of steps would correspond to the solution [('R', 1, 'x'), ('S', 1), ('W', 0, 'x')].

I have a feeling there is some similary between this problem av levenshtein editing distance, but I can't figure it out. So can you write the translate algorithm for me?

I'll add more examples if this problem description isn't clear enough but I hope it is.

Answer 1

First things first, I think I fixed your Python code. Here's a class that can run a sequence of steps and give the result. Your example left a ? in the result, which I think wasn't supposed to happen.

Here's the SequenceRunner

class SequenceRunner:

    def __init__(self):
        self.INSTRUCTIONS = {
            'R': self.read,
            'S': self.shift,
            'W': self.write
            }

    def set(self, S):
        self.S = S[::-1]

    def shift(self, n):
        self.S = self.S[-n:] if n < 0 else  '?'*n + self.S

    def read(self, n, v):
        assert not '?' in self.S; return self.S[n]

    def write(self, n, v):
        v = getattr(self, v)
        self.S = self.S[:n] + v + self.S[n+1:]

    def run(self, program):
        for line in program:
            func = self.INSTRUCTIONS[line[0]]
            args = line[1:]
            result = func(*args)
            if result:
                setattr(self, args[-1], result)

    def get(self):
        return self.S[::-1]

And here's how to use it

c = SequenceRunner()
program = [('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]
c.set('ab')
c.run(program)
print c.get()

Question so I understand better: do you need an algorithm that can deduce the (least amount of) steps needed to go from one string to another?