Naming
Your 2 arrays are used the same way, it is a bit weird to have 2 different names for them. Maybe int_arr1
and int_arr2
would be better names. Also the fact that they contain integers may be irrelevant for the naming: arr1
and arr2
would do the trick (or lst1
and lst2
because the corresponding Python primitive data structure is list
).
Problem with the check for length equal to 0
Checking for identical lengths as the beginning of the function is a nice touch.
However, the or len(lst1) == 0
condition makes me uneasy. It only makes a different when the first part of the check was false and the second part is true which means: len(lst1) == len(lst2) == 0
which really means: lst1 == lst2 == []
.
I'd expect the empty array to be a rotation of the empty array. The alternative would be to document the function to precise that only non-trivial rotations are considered (which is not the case at the moment). The easy fix is probably to remove this test or to return True in that case (or whenver lst1
== lst2
).
Comments
Commenting your code is nice but adding obvious comments doesn't help anyone. There is a fine line between too many comments and not enough comments.
I'd get rid of #lengths of arrays are the same and not equal to zero?
for instance.
On the other hand, #@cmp_arr, is the array being compared to see if it is a rotation
could be kept somehow. This should be moved in the function docstring. Also, Python has a Docstring convention called PEP 257. You could write:
def is_rotated(lst1, lst2):
"""Test whether list lst1 is a rotation of list lst2."""
Same value computed multiple times
You compute set(lst1)
multiple times which is not as efficient as it could be (which is sad for something meant to be an optimisation).
#does array contain same numbers?
s1 = set(lst1)
s2 = set(lst2)
if not s1 <= s2 and not s1 >= s2:
return False
Optimisation does not work
I guess the point of the optimisation would be to detect situations like:
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
print(is_rotated(lst1, lst2))
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
print(is_rotated(lst1, lst2))
Unfortunately, this is not detected.
I guess instead of not s1 <= s2 and not s1 >= s2
, you meant: not s1 <= s2 or not s1 >= s2
which is equivalent to not (s1 <= s2 and s1 >= s2)
which is equivalent to the more straight-forward: s1 != s2
.
In any case, as pointed out by Oscar Smith, this optimisation may not be worth doing.
Reusing existing functions
Looking for index can be done with the already existing function: index = lst2.index(lst1[0])
.
Loop like a native
Your final loop is not really Pythonic. Most of the time in Python, you can avoid messing with indices. I hightly recommand Ned Batchelder's talk: "Loop like a native".
In your case, we can improve your code in multiple steps. (Some of the steps are pretty artificial in your case but I use them to show you the different functions you have in your Python toolbox).
Introducing enumerate
to get rid of the code to track index
:
#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for i, x in enumerate(lst1):
if x != rot2[i]:
return False
return True
Using zip
to avoid accessing rot2
by index:
#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for x1, x2 in zip(lst1, rot2):
if x1 != x2:
return False
return True
Using all
to make things more concise:
return all(x1 == x2 for x1, x2 in zip(lst1, rot2))
The final revelation: all this is not needed:
return lst1 == rot2
At this point, the code looks like:
def is_rotated(lst1, lst2):
"""Test whether list lst1 is a rotation of list lst2."""
if len(lst1) != len(lst2):
return False
if lst1 == lst2:
return True
if set(lst1) != set(lst2):
return False
index = lst2.index(lst1[0])
#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
return lst1 == rot2
Broken code
As pointed out by Oscar Smith, your code does not work.
For that kind of programming task, it is very easy to write tests to help you catch issues. These can be written before, during and after writing the code. You could use a proper testing framework or just simple assertions like:
# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)
# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)
# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)
# equal
lst2 = lst1
assert is_rotated(lst1, lst2)
# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)
# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)
is_rotated([1, 1, 2], [1, 2, 1])
returnsFalse
. \$\endgroup\$ – Gareth Rees Feb 9 '18 at 10:52