diff options
-rw-r--r-- | scratch/deepmind/part_two/todo.org | 2 | ||||
-rw-r--r-- | scratch/deepmind/part_two/top-scores.py | 47 |
2 files changed, 48 insertions, 1 deletions
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org index 3562dbe5be55..72b0e99a4253 100644 --- a/scratch/deepmind/part_two/todo.org +++ b/scratch/deepmind/part_two/todo.org @@ -8,7 +8,7 @@ ** DONE Inflight Entertainment ** DONE Permutation Palindrome ** DONE Word Cloud Data -** TODO Top Scores +** DONE Top Scores * Greedy Algorithms ** TODO Apple Stocks ** TODO Highest Product of 3 diff --git a/scratch/deepmind/part_two/top-scores.py b/scratch/deepmind/part_two/top-scores.py new file mode 100644 index 000000000000..0ac349c1f880 --- /dev/null +++ b/scratch/deepmind/part_two/top-scores.py @@ -0,0 +1,47 @@ +import unittest + + +def sort_scores(xs, highest_possible_score): + result = [] + buckets = [0] * highest_possible_score + + for x in xs: + buckets[x - 1] += 1 + + for i in range(highest_possible_score - 1, -1, -1): + if buckets[i] > 0: + for _ in range(buckets[i]): + result.append(i + 1) + + return result + + +# Tests +class Test(unittest.TestCase): + def test_no_scores(self): + actual = sort_scores([], 100) + expected = [] + self.assertEqual(actual, expected) + + def test_one_score(self): + actual = sort_scores([55], 100) + expected = [55] + self.assertEqual(actual, expected) + + def test_two_scores(self): + actual = sort_scores([30, 60], 100) + expected = [60, 30] + self.assertEqual(actual, expected) + + def test_many_scores(self): + actual = sort_scores([37, 89, 41, 65, 91, 53], 100) + expected = [91, 89, 65, 53, 41, 37] + self.assertEqual(actual, expected) + + def test_repeated_scores(self): + actual = sort_scores([20, 10, 30, 30, 10, 20], 100) + expected = [30, 30, 20, 20, 10, 10] + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |