diff options
author | Vincent Ambo <mail@tazj.in> | 2021-12-13T22·51+0300 |
---|---|---|
committer | Vincent Ambo <mail@tazj.in> | 2021-12-13T23·15+0300 |
commit | 019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch) | |
tree | 76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py | |
parent | 464bbcb15c09813172c79820bcf526bb10cf4208 (diff) | |
parent | 6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff) |
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208 git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py')
-rw-r--r-- | users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py b/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py new file mode 100644 index 000000000000..889663e058da --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py @@ -0,0 +1,89 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# f :: [Int] -> Int +def highest_product_of_3(xs): + """Here we're greedily storing: + - current max + - largest product of two + - largest positive number + - second largest positive number + - largest negative number + """ + if len(xs) < 3: + raise Exception + + cm = None + ld = xs[0] * xs[1] + l2 = min(xs[0], xs[1]) + if xs[0] < 0 or xs[1] < 0: + ln = min(xs[0], xs[1]) + else: + ln = 1 + l = max(xs[0], xs[1]) + + for x in xs[2:]: + if not cm: + cm = max(x * ln * l, ld * x, x * l * l2) # beware + ld = max(ld, x * ln, x * l) + ln = min(ln, x) + l = max(l, x) + if x < l: + l2 = max(l2, x) + else: + cm = max(cm, x * ln * l, x * ld, x * l * l2) + ld = max(ld, x * ln, x * l) + ln = min(ln, x) + l = max(l, x) + if x < l: + l2 = max(l2, x) + + return cm + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_short_list(self): + actual = highest_product_of_3([1, 2, 3, 4]) + expected = 24 + self.assertEqual(actual, expected) + + def test_longer_list(self): + actual = highest_product_of_3([6, 1, 3, 5, 7, 8, 2]) + expected = 336 + self.assertEqual(actual, expected) + + def test_list_has_one_negative(self): + actual = highest_product_of_3([-5, 4, 8, 2, 3]) + expected = 96 + self.assertEqual(actual, expected) + + def test_list_has_two_negatives(self): + actual = highest_product_of_3([-10, 1, 3, 2, -10]) + expected = 300 + self.assertEqual(actual, expected) + + def test_list_is_all_negatives(self): + actual = highest_product_of_3([-5, -1, -3, -2]) + expected = -6 + self.assertEqual(actual, expected) + + def test_error_with_empty_list(self): + with self.assertRaises(Exception): + highest_product_of_3([]) + + def test_error_with_one_number(self): + with self.assertRaises(Exception): + highest_product_of_3([1]) + + def test_error_with_two_numbers(self): + with self.assertRaises(Exception): + highest_product_of_3([1, 1]) + + +unittest.main(verbosity=2) |