diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
commit | fb9380ba268b3cd27372acadb87b14cc96163374 (patch) | |
tree | f65d7fc8d8726499165a0949af39afd1abc8118c /universe/deepmind/find-rotation-point.py | |
parent | 15110e6de9f85537c7847267caa35fa068aea001 (diff) | |
parent | 8ad51b24dd8719840aac47134835ea25cfe1b0b8 (diff) |
Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'
git-subtree-dir: universe git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001 git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8
Diffstat (limited to 'universe/deepmind/find-rotation-point.py')
-rw-r--r-- | universe/deepmind/find-rotation-point.py | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/universe/deepmind/find-rotation-point.py b/universe/deepmind/find-rotation-point.py new file mode 100644 index 000000000000..5c21d5167ce9 --- /dev/null +++ b/universe/deepmind/find-rotation-point.py @@ -0,0 +1,55 @@ +import unittest +from math import floor + + +def midpoint(a, b): + return a + floor((b - a) / 2) + + +def do_find_rotation_point(a, b, xs): + i = midpoint(a, b) + count = b - a + 1 + + if count == 2: + if xs[a] > xs[b]: + return b + else: + return -1 + + if i in {a, b}: + return i + + if xs[a] < xs[i]: + return do_find_rotation_point(i, b, xs) + else: + return do_find_rotation_point(a, i, xs) + + +def find_rotation_point(xs): + return do_find_rotation_point(0, len(xs) - 1, xs) + + +# 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) + + +unittest.main(verbosity=2) |