Last active
December 23, 2015 15:29
-
-
Save landau/6655551 to your computer and use it in GitHub Desktop.
Circular Array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def is_circular(arr, start): | |
if not isinstance(arr, list): raise TypeError('Expected arr to be list') | |
if not isinstance(start, int): raise TypeError('Expected start to be int') | |
size = len(arr) | |
n = size | |
pos = start | |
# key running count to track that each index is hit | |
# use the index as the count, total_exp will be the | |
# sum of all the index positions | |
total = 0 | |
total_exp = 0 | |
while n > 0: | |
next = arr[pos] | |
# use modulus to normalize negatives and numbers that loop | |
# around the array | |
pos = (next + pos) % size | |
# add the index found to the accumulator | |
total += pos | |
n -= 1 | |
# add to expected indexes hit | |
total_exp += n | |
# We should be at the initial value of the array again | |
if pos != start: return False | |
# verify that all indexes were hit | |
if total != total_exp: return False | |
return True | |
if __name__ == '__main__': | |
import unittest | |
class Test(unittest.TestCase): | |
def setUp(self): | |
self.tests = [ | |
([5, 2, -1], True), | |
([1, 2, 3], False), | |
([0, 2, 1], False), | |
([1, 2, 1], False), | |
([2, 2, 2], True), | |
([1, 2, 2, -1], True), | |
([-1, 2, -1], True), | |
([-2, 3, 3, 3, -2], True) | |
] | |
def test_types(self): | |
with self.assertRaises(TypeError): | |
is_circular(1, 2) | |
with self.assertRaises(TypeError): | |
is_circular([1, -1], {}) | |
def test_value(self): | |
for (vals, boolean) in self.tests: | |
# test circularness works from any starting point | |
for i in xrange(len(vals)): | |
self.assertEqual( | |
is_circular(vals, i), | |
boolean, | |
'Vals %s should be %s with rand %d' % (vals, boolean, i) | |
) | |
unittest.main() | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment