Last active
July 12, 2022 16:42
-
-
Save jomido/4105444d1b6f0a933662e3fe0576f861 to your computer and use it in GitHub Desktop.
CodeSignal: Descending/Ascending Towers
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
| cases = [ | |
| ([], 0), | |
| ([10], 0), | |
| ([1, 2, 3, 4], 0), | |
| ([1, 1, 1, 1], 6), | |
| ([1, 3, 2, 1], 3), | |
| ([1, 7, 1, 4], 13), | |
| ] | |
| def get_max_indices(towers: list[int]) -> list[int]: | |
| """ | |
| Returns the indexes of the max value in `towers`. | |
| Since we're already iterating over all of the elements, we could do a | |
| monotony-check here and short-circuit IIF `towers` is already monotonous. | |
| Skipping that. | |
| """ | |
| max_n = -1 | |
| indices = [] | |
| for i, n in enumerate(towers): | |
| if n > max_n: | |
| indices = [i] | |
| max_n = n | |
| elif n == max_n: | |
| indices.append(i) | |
| return indices | |
| def monotonize_left_descending(towers: list[int]) -> int: | |
| # be kind | |
| clone = towers[:] | |
| if not towers: | |
| return 0 | |
| max_indices = get_max_indices(towers) | |
| index_of_last_max = max_indices[-1] | |
| bump = 0 | |
| # tie-break max values: if there is more than one index for the max value, | |
| # bump preceding max values by their index-distance from the final max value | |
| # (and accumulate the bumps) | |
| for index_of_a_max in max_indices[:-1]: | |
| this_bump = index_of_last_max - index_of_a_max | |
| bump += this_bump | |
| clone[index_of_a_max] += this_bump | |
| index_of_first_max = max_indices[0] | |
| current_max = clone[index_of_first_max] | |
| # for every number, calculate a target value from their index-distance to | |
| # the first occurrence of the max value; bump than number by the target | |
| # value (and accumulate the bumps) | |
| for i, n in enumerate(clone): | |
| offset = index_of_first_max - i | |
| target = current_max + offset | |
| this_bump = target - n | |
| bump += this_bump | |
| clone[i] += this_bump | |
| return bump | |
| def solution(towers: list[int]) -> int: | |
| """ | |
| Given a list of random integers `towers`, make the `towers` either ascending | |
| or descending monotonically by 1, by adding 0 or more to each integer. Find | |
| the total amount added to all integers (the "bump"). There are multiple | |
| solutions. Return the best one, where best == smallest bump. | |
| This is O(kn). | |
| """ | |
| bump = monotonize_left_descending(towers) | |
| if bump == 0: | |
| return bump | |
| towers_reversed = list(reversed(towers)) | |
| if towers == towers_reversed: | |
| return bump | |
| bump_reversed = monotonize_left_descending(towers_reversed) | |
| return min(bump, bump_reversed) | |
| def test(): | |
| for i, case in enumerate(cases): | |
| input, expected_output = case | |
| output = solution(input) | |
| msg = f"case #{i} failed: {output} != {expected_output}" | |
| assert output == expected_output, msg | |
| print("All is well.") | |
| if __name__ == "__main__": | |
| test() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment