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)