4 ms·

FWIW, here is my solution. I think it is grokable and does not rely on one knowing complex python, I think even someone without Python knowledge would understan

FWIW, here is my solution. I think it is grokable and does not rely on one knowing complex python, I think even someone without Python knowledge would understand what is going on: def order_values(value, prev): """ Compare value and prev, returns, -1, 0, 1 depending on the relative ordering. """ return int(value > prev) - int(prev > value) def monotonic_increasing(seq): """ Given a sequence of elements, detect the inner sequences of increasing and decreasing values. Return a list of list of values of these inner sequences, but with the decreasing ones reversed to be increasing. """ if not len(seq): return [] new_seq = [seq[0]] # Record the current sequence being built. seq_of_seq = [new_seq] # The sequence of sequences to return. seq_of_order = [0] # Record the sequences ordering (0 for unknown). for value in seq[1:]: value_order = order_values(value, new_seq[-1]) if value_order == seq_of_order[-1] or not value_order or not seq_of_order[-1]: new_seq.append(value) # If sequence order was unknown, adopt value order. if value_order and not seq_of_order[-1]: seq_of_order[-1] = value_order continue new_seq = [value] seq_of_seq.append(new_seq) seq_of_order.append(0) # Reverse decreasing sequences. for seq, order in zip(seq_of_seq, seq_of_order): if order < 0: seq.reverse() return seq_of_seq print(list(monotonic_increasing([1, 2, 3, 2, 1, 4, 5, 6, 7]))) print(list(monotonic_increasing([1, 1, 2, 3, 3, 2, 1, 1]))) print(list(monotonic_increasing([2, 1, 1]))) print(list(monotonic_increasing([])))

eesmith 5y ago
My updated version is more like a state machine. Your function and mine give the same answers both with the manual test cases and with a cross-comparison using random inputs: def monotonic_direct(seq): prev_value = None prev_dir = 0 # 0 for increasing or decreasing, 1 for increasing, -1 for decreasing group = [] #print("Run", seq) for value in seq: #print(prev_dir, prev_value, value) if not group: # Can only get here with the first element prev_value = value group.append(value) continue if prev_dir == 0: # Undecided order if prev_value < value: dir = 1 elif prev_value == value: # Still undecided group.append(value) continue else: dir = -1 elif prev_dir == 1: # Monotonic increasing if prev_value <= value: dir = 1 else: dir = 0 # reset for the next run elif prev_dir == -1: if prev_value < value: dir = 0 else: dir = -1 # reset for the next run if prev_dir == 0 or dir == prev_dir: # Still in the same direction group.append(value) else: # New direction if prev_dir == -1: group.reverse() yield group group = [value] prev_value = value prev_dir = dir if group: if prev_dir == -1: group.reverse() yield group def run_test_cases(): for dir_case, expected in ( ([1], [[1]]), ([1, 2], [[1, 2]]), ([2, 1], [[1, 2]]), # because of the reverse ([1, 2, 3], [[1, 2, 3]]), ([1, 3, 2], [[1, 3], [2]]), ([1, 1, 2], [[1, 1, 2]]), ([1, 1, 0], [[0, 1, 1]]), ([1, 1, 2, 0], [[1, 1, 2], [0]]), ([1, 1, 0, 0], [[0, 0, 1, 1]]), ([3, 3, 2, 2, 1, 1], [[1, 1, 2, 2, 3, 3]]), #([3, 3, 2, 3, 1, 1], [[2, 3, 3], [3], [1, 1]]), ([3, 3, 2, 3, 1, 1], [[2, 3, 3], [1, 1, 3]]), ([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]), ("AABCBADCABC", [["A", "A", "B", "C"], ["A", "B"], ["A", "C", "D"], ["B", "C"]]), ): got = list(monotonic_direct(dir_case)) assert got == expected, (dir_case, got, expected) print("All test cases passed.") def run_cross_test(): import random for i in range(10000): n = random.randrange(2, 10) values = [random.randrange(10) for _ in range(n)] result1 = list(monotonic_direct(values)) result2 = list(monotonic_increasing(values)) assert result1 == result2, (values, result1, result2) print("Random cross-comparison tests passed.") if __name__ == "__main__": run_test_cases() run_cross_test()
- klyrs 5y ago
  I came up with a similar solution; using True/None/False instead of 1/0/-1 allows for more self-documenting code def monotonics(seq): run = [] last_v = None increasing = None for v in seq: if last_v is None: pass elif increasing is None: if v != last_v: increasing = v > last_v elif increasing: if v < last_v: increasing = None yield run run = [] else: if v > last_v: increasing = None yield run[::-1] run = [] last_v = v run.append(v) if run: yield run and, I'd add a two more test cases: [], and [1, 2, 3, 1, 2, 3]

eesmith 5y ago

My updated version is more like a state machine. Your function and mine give the same answers both with the manual test cases and with a cross-comparison using random inputs: def monotonic_direct(seq): prev_value = None prev_dir = 0 # 0 for increasing or decreasing, 1 for increasing, -1 for decreasing group = [] #print("Run", seq) for value in seq: #print(prev_dir, prev_value, value) if not group: # Can only get here with the first element prev_value = value group.append(value) continue if prev_dir == 0: # Undecided order if prev_value < value: dir = 1 elif prev_value == value: # Still undecided group.append(value) continue else: dir = -1 elif prev_dir == 1: # Monotonic increasing if prev_value <= value: dir = 1 else: dir = 0 # reset for the next run elif prev_dir == -1: if prev_value < value: dir = 0 else: dir = -1 # reset for the next run if prev_dir == 0 or dir == prev_dir: # Still in the same direction group.append(value) else: # New direction if prev_dir == -1: group.reverse() yield group group = [value] prev_value = value prev_dir = dir if group: if prev_dir == -1: group.reverse() yield group def run_test_cases(): for dir_case, expected in ( ([1], [[1]]), ([1, 2], [[1, 2]]), ([2, 1], [[1, 2]]), # because of the reverse ([1, 2, 3], [[1, 2, 3]]), ([1, 3, 2], [[1, 3], [2]]), ([1, 1, 2], [[1, 1, 2]]), ([1, 1, 0], [[0, 1, 1]]), ([1, 1, 2, 0], [[1, 1, 2], [0]]), ([1, 1, 0, 0], [[0, 0, 1, 1]]), ([3, 3, 2, 2, 1, 1], [[1, 1, 2, 2, 3, 3]]), #([3, 3, 2, 3, 1, 1], [[2, 3, 3], [3], [1, 1]]), ([3, 3, 2, 3, 1, 1], [[2, 3, 3], [1, 1, 3]]), ([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]), ("AABCBADCABC", [["A", "A", "B", "C"], ["A", "B"], ["A", "C", "D"], ["B", "C"]]), ): got = list(monotonic_direct(dir_case)) assert got == expected, (dir_case, got, expected) print("All test cases passed.") def run_cross_test(): import random for i in range(10000): n = random.randrange(2, 10) values = [random.randrange(10) for _ in range(n)] result1 = list(monotonic_direct(values)) result2 = list(monotonic_increasing(values)) assert result1 == result2, (values, result1, result2) print("Random cross-comparison tests passed.") if __name__ == "__main__": run_test_cases() run_cross_test()

klyrs 5y ago
I came up with a similar solution; using True/None/False instead of 1/0/-1 allows for more self-documenting code def monotonics(seq): run = [] last_v = None increasing = None for v in seq: if last_v is None: pass elif increasing is None: if v != last_v: increasing = v > last_v elif increasing: if v < last_v: increasing = None yield run run = [] else: if v > last_v: increasing = None yield run[::-1] run = [] last_v = v run.append(v) if run: yield run and, I'd add a two more test cases: [], and [1, 2, 3, 1, 2, 3]