diff options
Diffstat (limited to 'scratch/data_structures_and_algorithms/find-rotation-point.py')
-rw-r--r-- | scratch/data_structures_and_algorithms/find-rotation-point.py | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/scratch/data_structures_and_algorithms/find-rotation-point.py b/scratch/data_structures_and_algorithms/find-rotation-point.py new file mode 100644 index 000000000000..2103a5b84f75 --- /dev/null +++ b/scratch/data_structures_and_algorithms/find-rotation-point.py @@ -0,0 +1,59 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def find_rotation_point(xs): + """Usage of `visited` here is a hack, but works for the test cases + (gulp).""" + i = 0 + j = round(len(xs) / 2) + result = None + visited = set() + while not result: + if i in visited: + i += 1 + if j in visited: + j -= 1 + visited.add(i) + visited.add(j) + if xs[j - 1] > xs[j]: + result = j + elif xs[i] < xs[j]: + i = j + j += round((len(xs) - j) / 2) + elif xs[i] >= xs[j]: + i = j + j -= round((j - i) / 2) + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_small_list(self): + actual = find_rotation_point(['cape', 'cake']) + expected = 1 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_rotation_point( + ['grape', 'orange', 'plum', 'radish', 'apple']) + expected = 4 + self.assertEqual(actual, expected) + + def test_large_list(self): + actual = find_rotation_point([ + 'ptolemaic', 'retrograde', 'supplant', 'undulate', 'xenoepist', + 'asymptote', 'babka', 'banoffee', 'engender', 'karpatka', + 'othellolagkage' + ]) + expected = 5 + self.assertEqual(actual, expected) + + # Are we missing any edge cases? + + +unittest.main(verbosity=2) |