Python code for detecting a single item moved in a list

Question

I need to write a function that takes an original list of unique values and a resulting list:

[0,1,2,3]
[0,3,1,2]

and detect that only a single element was moved then report exactly what was moved where. If the resulting list is not the result of moving exactly one item from source to destination, this code should fail.

Here are some examples:

[0,1,2,3]
[0,3,1,2]

location 3 was moved to location 1

Failure cases (not exactly one move could be detected) include:

[4,1,2,3]
[1,3,1,2]

(before/after have different items)

[1,1,2,3]
[1,3,1,2]

(before has duplicate values)

[4,5,1,2,3]
[1,3,1,2]

(before/after not the same size)

My basic approach is to iterate both lists simultaneously until there's a difference. If the destination list has a different item, then we see if the next item matches the source lists current item. This indicates that something has been inserted at this point. We then move forward the destination list and proceed. We notice removals in a similar process. If the we've decided its not an insertion, that is two items are not equal but the source does NOT continue in the destination list, then we treat it as a removal.

In the case of an insertion, we only move the destination list forward. We expect the rest of the dest list/src list to match up until we detect a removal. In the case of detecting a removal, we move forward the source list. If both elements are equal, we move them both forward.

For example:

original:  result:
1----------4  // not equal, peek ahead and compare 1==1, this is just an insertion
2--- \-----1  // 1 == 1 same
3-- \------2  // 2 == 2 same
4- \-------3  // 3 == 3 same
  \--------   // result exhausted, removal

original:  result:
1----\-----4  // not equal, peek ahead and compare 1==1, this is an insertion, move just result ahead 1
2--\  \----1  // 1 == 1 same
3-\ \------2  // 2 == 2 same
4\ \-------3  // 3 == 3 same
  \--------   // result exhausted, removal

original:  result:
1----\-----4  // not equal, peek ahead and compare 1==1, this is an insertion, move just result ahead 1
2--\  \----1  // 1 == 1 same
3-\ \------2  // 2 == 2 same
4\ \-------3  // 3 == 3 same
  \--------   // result exhausted, removal

original:  result:
1----------1  // 1 == 1
2--\ ------3  // 2 != 3, but peek ahead 2==2 insertion at 1, move just result ahead 1
3-\ \------2  // 2 == 2 same
4\ \-------4  // 3 != 4 removal
  \--------   // result exhausted

Here's my solution so far. It uses an iterator I created that comes with bells and whistles to peek ahead, get the current value, get the current index etc:

class _ListIter(object):
    """ Iterate a list, expose some information such as
        the current index (.index()) and the current value (.curr())"""

    def __init__(self, l):
        self.l = l
        self._idx = 0

    def __iter__(self):
        return self

    def next(self):
        self._idx += 1
        if (self._idx > len(self.l)):
            raise StopIteration
        val = self.l[self._idx - 1]
        return val

    def index(self):
        """ Return index of current value, -1 if next hasn't
            been called yet"""
        return self._idx - 1

    def curr(self):
        """ Return current value, None if next hasn't
            been called yet"""
        if self.index() == -1 or self.exhausted():
            return None
        else:
            return self.l[self.index()]

    def peek(self):
        if self.index() + 1 >= len(self.l):
            return None
        return self.l[self.index() + 1]

    def numLeft(self):
        return len(self.l) - self._idx

    def exhausted(self):
        return (self._idx > len(self.l))

In this module are some helper functions:

def _fwd(*args):
    for arg in args:
        try:
            next(arg)
        except StopIteration:
            pass

def _areListsCandidates(original, result):
    origSet = set(original)
    resSet = set(result)
    return (len(original) == len(result) == len(origSet) == len(resSet)) and (origSet == resSet)

And finally the algorithm implemented itself:

def findMove(original, result):
    if (not _areListsCandidates(original, result)):
        return None

    orig, res = _ListIter(original), _ListIter(result)

    fromVal, toVal, fromIdx, toIdx = None, None, None, None

    _fwd(orig, res)
    while not (orig.exhausted() and res.exhausted()):

        def isInsertion():
            if orig.curr() != res.curr():
                return orig.exhausted() or (res.numLeft() > 0 and orig.curr() == res.peek())
            return False

        def isRemoval():
            return (orig.exhausted() or orig.curr() != res.curr())

        if isInsertion():
            toVal, toIdx = res.curr(), res.index()
            _fwd(res)
        elif isRemoval():
            fromVal, fromIdx = orig.curr(), orig.index()
            _fwd(orig)
        else:
            _fwd(orig, res)

        if (fromIdx is not None and toIdx is not None and fromVal == toVal):
            return (fromIdx, toIdx)

I fully expect somebody to point me to a Python library I missed or to 3 lines of itertools craziness that does this more intelligently.

I would like feedback on the approach used and style. I feel like I should be doing something more intelligently here, or there's an approach I'm not familiar with for this problem. I also feel like the code isn't terribly pythonic or elegant.

To help, here are my tests:

from findMove import findMove
from copy import copy

def testBackToFront():
    (fromIdx, toIdx) = findMove(original=[1,2,3,4], result=[4,1,2,3])
    assert(fromIdx == 3)
    assert(toIdx == 0)

def testFrontToBack():
    (fromIdx, toIdx) = findMove(original=[4,1,2,3], result=[1,2,3,4])
    assert(fromIdx == 0)
    assert(toIdx == 3)


def testMove():
    # Arbitrarilly reposition where insValue comes from
    # and goes to
    original = [1,2,3,5,6,7,8,9]
    result = [1,2,3,5,6,7,8,9]
    insValue = 4
    for origIdx in range(len(original) + 1):
        origCpy = copy(original)
        origCpy.insert(origIdx, insValue)

        for insIdx in range(len(original) + 1):
            resCpy = copy(result)
            resCpy.insert(insIdx, insValue)
            if (resCpy != origCpy):
                (fromIdx, toIdx) = findMove(origCpy, resCpy)
                if fromIdx < toIdx:
                    if abs(origIdx - insIdx) == 1:
                        assert(fromIdx == origIdx or fromIdx == insIdx)
                        assert(toIdx == insIdx or toIdx == origIdx)
                        assert(toIdx != fromIdx)
                    else:
                        assert(fromIdx == origIdx)
                        assert(toIdx == insIdx)

def testEmptyLists():
    assert(findMove([], []) is None)

def testEqualLists():
    assert(findMove([1], [1]) is None)

def testSmallLists():
    (fromIdx, toIdx) = findMove([2,1], [1,2])
    assert(fromIdx == 1 or fromIdx == 0)
    assert(toIdx == 0 or toIdx == 1)
    assert(toIdx != fromIdx)

def testDiffLenFails():
    res = findMove(original=[1,2,3,4], result=[4,1,2,3,5])
    assert(res is None)

def testDiffValsFails():
    res = findMove(original=[1,2,3,4], result=[1,2,3,5])
    assert(res is None)

def testDups():
    res = findMove(original=[1,1,3,4], result=[1,1,4,3])
    assert(res is None)

    res = findMove(original=[1,1,1,1], result=[1,1,1,2])
    assert(res is None)

Answer 1

This seems a shorter solution:

def findMove(original,result):
    if len(original) != len(result):
        return # different length                                               

    diff = [x for x,(c,d) in enumerate(zip(original,result)) if c!=d]
    if not diff:
        return # equal strings                                                  
    i,j = diff[0],diff[-1]

    if original[i+1:j+1] == result[i:j] and original[i] == result[j]:
        return (i,j)
    if original[i:j] == result[i+1:j+1] and original[j] == result[i]:
        return (j,i)

PS: this works also if the items are non unique.

Answer 2

This problem can be solved by finding the edit distance between the two sequences, where an edit is defined as being an insertion or a deletion (the usual definition includes substitution as an edit operation).

You can use the distance matrix computed by the following code to reconstruct the edit sequence. You then need to check that it consists of a single insert and a single delete, where the items inserted and deleted are equal.

def edit_distance(a, b):
    m = len(a)
    n = len(b)
    dist = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(m + 1):
        dist[i][0] = i
    for j in range(n + 1):
        dist[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dist[i][j] = dist[i - 1][j - 1]
            else:
                dist[i][j] = min(dist[i - 1][j], dist[i][j - 1]) + 1
    return dist[m][n]

This can be improved upon, since our problem is more specific.

Ukkonen describes a variant that takes two strings and a maximum edit distance \$s\$, and returns \$\min(s, d)\$. It achieves this by only computing and storing a part of the dynamic programming table around its diagonal. This algorithm takes time \$O(s \min(m,n))\$, where \$m\$ and \$n\$ are the lengths of the strings. Space complexity is \$O(s^2)\$ or \$O(s)\$, depending on whether the edit sequence needs to be read off. (Wikipedia)

Since we're interested in \$s = 3\$, the time and space complexity is greatly reduced with that variant.

A further hint on how to implement that improvement is provided on Wikipedia's page on the Wagner–Fischer algorithm.

If we are only interested in the distance if it is smaller than a threshold \$k\$, then it suffices to compute a diagonal stripe of width \$2k+1\$ in the matrix. In this way, the algorithm can be run in \$O(kl)\$ time, where \$l\$ is the length of the shortest string.

Answer 3

Here's my take. Nothing fancy.

a=[10,11,12,13,14,15,16,17,18,19]
b=[10,11,12,13,15,14,16,17,18,19]

#####
def first_different_at(a,b):
    for i in range(min(len(a),len(b))):
        if a[i] != b[i]:
            return i
    return -1

def findMove(original,result):
    if len(original) != len(result):
        return None

    start = first_different_at(original,result)
    end = len(original) - first_different_at(list(reversed(original)),list(reversed(result)))

    if start==end or start == -1:
        return None

    original_ = original[start:end]
    result_ = result[start:end]

    if [result_[-1]]+result_[:-1]==original_:
        return (start,end-1)
    elif result_[1:]+[result_[0]]==original_:
        return (end-1,start)
    else:
        return None

findMove(a,b)

Basically I'm chopping off the list before the first difference and after the last difference. If the lists are valid then you can take the result and morph it into the original by either sticking the first element on the end or sticking the last element at the beginning.

It passes all of your tests except for testMove() and testSmallLists() because those have ambiguous results. For instance

orig =   [1, 4, 2, 3, 5, 6, 7, 8, 9]
result = [4, 1, 2, 3, 5, 6, 7, 8, 9]

Can be from 0 to 1 or the opposite. These ambiguities Always happen when the from and two numbers are one apart, so you can easily fix your test by checking for this and then sorting the indices.

Fun problem!

P.S. numpy has a find_where function IICR that can be used for the first_different_at func above.

Answer 4

Review:

I would make passing in results that have different values, lengths, and multiple moves to be ValueErrors instead of None returns, as those don't seem to be valid input.

You missed a test case: your test cases do not cover multiple moves (which is supposed to fail by your definition).

You do not follow the Python programming style-guide: PEP-8. Function names should be lowercase_with_underscores, docstrings are missing, spacing isn't consistent...

Additionally, defining functions within functions is generally less readable and less useful than defining them externally (so that they might be used elsewhere for instance)

Lastly, I would have your tests run in some sort of main function. This can be done by adding this code snippet to the location of the tests:

if __name__ == '__main__':
    # run tests here

This allows you to run all the tests automatically when you run the module with the tests, which simplifies testing.

My solution:

The basic idea is to iterate through the values to find a difference, determine if it is a forward move or a backwards move, and then find where the move came from.

1 step at a time:

• To find a difference, we zip the two iterables together to get an iterator over tuples containing one item from one, one item from the other. Eg. zip([1, 2, 3], [3, 2, 1]) produces an iterator containing (1, 3), (2, 2), (3, 1). We then see if the elements of the tuple are equal.

• To determine if the move was forwards or backwards, we check to see if removing the item in the result at the current step from the original produces the tail of the result. Eg. [1, 2, 3, 4] -> [4, 1, 2, 3] has a modified original of [1, 2, 3] (4 is removed), and the tail of the result is [1, 2, 3] as well, so the move is forwards. If we take the reverse: [4, 1, 2, 3] -> [1, 2, 3, 4], we can see the modified original is [4, 2, 3] (1 is removed), while the tail of the result is [2, 3, 4], so the move is backwards. Moving backwards is the same thing as moving forwards in reverse, so I just reverse the result from the helper method

• To determine where the value came from, I once again iterate through the zipped lists, starting at the beginning of the difference, and find a pair of equal elements, indicating that the move occurred from the end to the beginning. If there are no equal elements, then the item came from the very end.

The enumerate function I'm using is basically adds a counter over the tuples for the zip function, so that I don't have to keep track of an extra variable and the results are in a convenient index, tuple format.

Code:

def find_move(original, result):
    """Returns the move the changes original into result, if possible"""
    if len(original) != len(result):
        raise ValueError("lists have different lengths")
    for counter, (a, b) in enumerate(zip(original, result)):
        if a != b:
            original_copy = original[counter:]
            try:
                original_copy.remove(b)
            except ValueError:
                raise ValueError("result has different values from original")
            if original_copy == result[counter+1:]:
                return find_forward_move(original, result, counter)
            else:
                # move is backwards
                a, b = find_forward_move(result, original, counter)
                return (b, a)


def find_forward_move(original, result, diff_start):
    """Produces the move that transforms original into result if moving forwards"""
    diff_end = 0
    for counter, (a, b) in enumerate(zip(original[diff_start+1:], result[diff_start+1:])):
        if a == b:
            diff_end = counter + diff_start
            break
    if diff_end == 0:
        diff_end = len(original) - 1
    # Test to make sure moving does the trick to ensure it really is 1 move only
    original_copy = original[:]
    original_copy.remove(original[diff_end])
    original_copy.insert(diff_start, original[diff_end])
    if original_copy != result:
        raise ValueError("More than 1 move detected")
        
    return diff_end, diff_start