In a recent conversation, someone shared some code from a book about technical job interviews. They wanted to know if I agreed that the code was “Pythonic.”
The problem was to find the runs of increasing and decreasing values in a list, and to produce a sequence of the runs, but to reverse the decreasing runs, so that they are also increasing. This was the “Pythonic” code:
import itertools
def mono_runs_pythonic(seq):
class Monotonic:
def __init__(self):
self._last = float("-inf")
def __call__(self, curr):
res = curr < self._last
self._last = curr
return res
return [
list(group)[::-1 if is_decreasing else 1]
for is_decreasing, group in itertools.groupby(seq, Monotonic())
]
mono_runs_pythonic([1, 2, 3, 2, 1, 4, 5, 6, 7])
# --> [1, 2, 3], [1, 2], [4, 5, 6, 7]
My first response was that I don’t like this code, because I had to read it with my eyebrows. That is, I furrow my brow, and read slowly, and scowl at the code as I puzzle through it. This code is dense and tricky.
Is it Pythonic? I guess in the sense that it uses a number of Python-specific constructs and tools, yes. But not in the sense of Python code being clear and straightforward. It uses Python thoroughly, but misses the spirit.
I tried my hand at my own solution. It came out like this:
def mono_runs_simpler(seq):
seqit = iter(seq)
run = [next(seqit)]
up = True
for v in seqit:
good = (v > run[-1]) if up else (v < run[-1])
if good:
run.append(v)
else:
yield run if up else run[::-1]
run = [v]
up = not up
if run:
yield run
This code also uses some unusual Python techniques, but is clearer to me. I’m not sure everyone would agree it is clearer. Maybe you have an even better way to do it.
Aside from the question of which code is better, I also didn’t like that this code was presented as a good solution for a job interview. Studying code like this to learn intricate tricks of Python is not a good way to get a job. Or, it might be a good way to get a job, but I don’t like that it might work. Job interviews should be about much deeper concerns than whether you know little-visited corners of the Python standard library.
Comments
got
[[1, 2, 3], [1, 2], [8], [4], [5, 6, 7]]
why not
[[1, 2, 3], [1, 2], [8], [4, 5, 6, 7]]
or
[[1, 2, 3], [1, 2], [4, 8], [ 5, 6, 7]]
[1, 2, 3, 1, 2, 3, 1, 2, 3] should yield [ [1, 2, 3], [1, 2, 3], [1, 2, 3] ]
def mono_runs_simpler(seq): seqit = iter(seq) run = [next(seqit)] up = 'unknown order' for v in seqit: if isinstance(up, bool): good = (v > run[-1]) if up else (v < run[-1]) else: up = v > run[-1] good = True if good: run.append(v) else: yield run if up else run[::-1] run = [v] up = 'unknown order' if run: yield runYours is more in line with PEP 20, but I also feel that we could get it even friendlier to beginners. I probably won't have time, but if I do, I may try my hand at this same problem!
Really nice write up for the day, great way for me to start Friday!
from itertools import groupby def mono_runs(seq): if len(seq) < 2: return [seq] def item_at(i): return seq[i] def increasing_to(i): if i == 0: return item_at(0) < item_at(1) return item_at(i - 1) < item_at(i) return [ sorted(map(item_at, index_run)) for _, index_run in groupby(range(len(seq)), increasing_to) ]def mono_runs_direction(a, b): if a > b: return -1 else: return 1 def mono_runs_pythonic(arr): runs = [] run = [arr[0]] dir = None for value in arr[1:]: cur_dir = mono_runs_direction(run[-1], value) if not dir: dir = cur_dir if dir == cur_dir: run.append(value) else: runs.append(run[::dir]) run = [value] dir = None if run: runs.append(run) return runsimport itertools import math TESTS = [ [1, 2, 3, 2, 1, 4, 5, 6, 7, 1, 2], [1, 2, 2, 1, 4, 5, 1, 7, 1, 2], [5, 4, 3, 2, 1], [], ] def mono(seq): acc = [] base = 0 z = -math.inf def taker(n): nonlocal z good = n > z z = n return good while base < len(seq): subseq = list(itertools.takewhile(taker, seq[base:])) if not subseq: z = -math.inf continue base += len(subseq) acc.append(subseq) return acc if __name__ == '__main__': for test in TESTS: print(mono(test))Prints:I have a simple minded solution to the problem, which handles the edge cases as well:
https://gist.github.com/babo/f93fd294a93cc9e4ccbb0723d7a5cb25
def mono(seq): if len(seq) == 1: yield seq elif len(seq) >= 2: up = seq[1] > seq[0] # whether the sequence starts out increasing for i in range(2, len(seq)): if (seq[i] > seq[i-1]) != up: # if we've switched directions yield seq[:i] if up else seq[i-1::-1] yield from mono(seq[i:]) break else: # if no break yield seq if up else seq[::-1]It assumes that the input will be a sequence (so its length can be determined and it can be indexed). It doesn't really handle consecutive equal numbers correctly, but there wasn't anything about that in the spec so I didn't bother. I used the for-else construct, which is admittedly not very widely known, but I find it extremely useful, and I think a simple inline comment can make up for the lack of clarity.def mono(seq): up = None for i, (first, second) in enumerate(zip(seq, seq[1:])): if up is None: # direction needs to be determined if second > first: up = True if second < first: up = False continue if (second > first and not up) or (second < first and up): yield seq[:i+1] if up else seq[i::-1] yield from mono(seq[i+1:]) break else: # if no break if seq: yield seq if up else seq[::-1]This uses the more general definition of monotonic, which is either non-increasing or non-decreasing. I also realized that I could drop the len == 1 clause here, since the way the for loop is structured means that it will just be entirely skipped for sequences of length zero and one, removing the possibility of an out-of-bounds index.Examples:
def mono_runs(seq):
...: keys = itertools.chain([True], map(operator.le, seq, seq[1:]))
...: return [list(group)[::1 if key else -1] for key, group in itertools.groupby(seq, lambda _: next(keys))]
```
I like the Numpy solution. If someone claims it's cheating, I'd reply with "Although practicality beats purity".
Numpy is often the best-scaling solution.
No imports, let's timsort handle the reversal (timsort is good at it), just some list comprehensions, flat, the conditions are not hidden, no edge cases, ...
def monotonics(iterable): l = list(iterable) extrema = [ a < b > c or a > b < c for a,b,c in zip(l,l[1:],l[2:])] extrema = [False] + extrema + [True] runs = [0] + [i+1 for i,extremum in enumerate(extrema) if extremum] monotonics = [sorted(l[a:b]) for a,b in zip(runs,runs[1:])] return monotonicsThis is particularly relevant because if we require working against values that carry information that doesn't factor into the comparison, then "reverse via sort" against a decreasing run will not reverse the order of elements that compare equal. So, if they're numeric values, then it's fine, but if there's some kind of "priority-but-FIFO-if-equal-priority" logic baked into a types comparison operations, then explicitly doing the reverse is necessary.
Why would anyone pass that kind of value into this function? I don't know, what's the use case for literally any of this?
But why is the second solution worse? Well, it just has way more conditionals, and way worse variable naming (any 1-2 letter variable should be a red flag for rushed-out code).
Sorry, not sorry. If you interview for a Python job you should have an idea of what's in the stdlib. Access to the python docs (just that) during interview seems like a fair compromise to me - can't reasonably expect anyone to know exactly if it's itertools.groupby or itertools.group_by.
To my understanding there must be at least two items in a run before we can determine whether it's increasing or decreasing. We end each run when the next input item either changes direction or matches the current input item.
I probably should return an iterator and make use of test tools to be more Pythonic, but I was focused on the logic. I don't claim to be a real coder.
Comments welcome, snide remarks encouraged!
def mono(seq): if len(seq) < 1: return [] result = [] run = [] up = True def end_run(): nonlocal run, result if not up: run.reverse() result.append(run) run = [] for i, n in enumerate(seq): run.append(n) try: if n == seq[i + 1]: end_run() elif (len(run) >= 2) and \ ((n < seq[i + 1] and not up) or \ (n > seq[i + 1] and up)): end_run() up = n < seq[i + 1] except IndexError: end_run() return result # Test cases and code seqs = [ ([1, 2, 3, 1, 2, 3, 1, 2, 3,], [[1, 2, 3], [1, 2, 3], [1, 2, 3]]), ([1, 2, 3, 3, 2, 1, 1, 2, 3,], [[1, 2, 3], [1, 2, 3], [1, 2, 3]]), ([1, 2, 3, 3, 2, 1, 2, 3,], [[1, 2, 3], [1, 2, 3], [2, 3]]), ([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]), ([3, 2, 1, 1, 2, 3, 3, 2, 1], [[1, 2, 3], [1, 2, 3], [1, 2, 3]]), ([3, 3, 3, 2, 2, 1, 1, 2, 3], [[3], [3], [2, 3], [1, 2], [1, 2, 3]]), ([1, 2, 3, 3, 3, 4, 5, 5, 6], [[1, 2, 3], [3], [3, 4, 5], [5, 6]]), ([2, 1], [[1,2]]), ([10], [[10]]), ([], []), (['a', 'b', 'c', 'c', 'b', 'a', 'b', 'c'], [['a', 'b', 'c'], ['a', 'b', 'c'], ['b', 'c']]), ] for seq in seqs: result = mono(seq[0]) print(f'Input: {seq[0]}') print(f'Result: {result}') print(f'Expected: {seq[1]} {result == seq[1]} \n')RESULTS:class Monotonic(UserList): @property def populated(self) -> bool: return len(self.data) >= 2 @property def increasing(self) -> bool: if not self.populated: return True first, *rest = self.data not_equals = (item for item in rest if item != first) to_compare = next(not_equals, None) return to_compare is None or first < to_compare def order_preserving(self, item: float) -> bool: if not self.populated: return True last = self.data and self.data[-1] or float('-inf') if item == last: return True if item > last if self.increasing else item < last: return True return False def split_into_monotonous(seq: Sequence[float]) -> List[List[float]]: def _split() -> Iterator[List[float]]: processing = [] for item in seq: if Monotonic(processing).order_preserving(item): processing.append(item) else: yield processing processing = [item] yield processing return [sorted(monotonic) for monotonic in _split()]import pytest class Grp(): def __init__(self): self.elements = [] self.direction = None def add(self, el): self.elements.append(el) def changeDirection(self, new_up): return not self.direction is None or self.direction == new_up def mono(input): if len(input) < 2: return [input] grps = list() prev = None g = Grp() grps.append(g) for el in input: new_direction = None if prev: new_direction = el >= prev if not g.changeDirection(new_direction): g.direction = new_direction else: g = Grp() grps.append(g) g.add(el) prev = el return [sorted(g.elements) for g in grps] class Test_mono(): @pytest.mark.parametrize("input,res", [ ([], [[]]), ([1], [[1]]), ([1, 2], [[1, 2]]), ([2, 1], [[1, 2]]), ([1, 2, 3, 2], [[1, 2, 3], [2]]), ([1, 2, 3, 1, 2, 3], [[1, 2, 3], [1, 2, 3]]), ([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]), ([1, 2, 3, 2, 1, 8, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 8], [5, 6, 7]]), ([1, 1, 2, 2, 1, 1, 2, 2, 1, 1], [[1, 1, 2, 2], [1, 1, 2, 2], [1, 1]]) ]) def test_test(self, input, res): assert mono(input) == resCan a sequence of zero elements be in the list? I am not certain that the direction of the sequences are strictly alternating.
Here are my assumptions:
from unittest import TestCase class Test(TestCase): def test(self): seqs = [ ([], []), ([10], [[10]]), ([2, 1], [[1, 2]]), ([1, 2, 3, 1, 2, 3, 1, 2, 3,], [[1, 2, 3], [1, 2, 3], [1, 2, 3]]), ([1, 2, 3, 3, 2, 1, 1, 2, 3,], [[1, 2, 3, 3], [1, 1, 2], [2, 3]]), ([1, 2, 3, 3, 2, 1, 2, 3,], [[1, 2, 3, 3], [1, 2], [2, 3]]), ([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]), ([3, 2, 1, 1, 2, 3, 3, 2, 1], [[1, 1, 2, 3], [2, 3, 3], [1, 2]]), ([3, 3, 3, 2, 2, 1, 1, 2, 3], [[1, 1, 2, 2, 3, 3, 3], [2, 3]]), ([1, 2, 3, 3, 3, 4, 5, 5, 6], [[1, 2, 3, 3, 3, 4, 5, 5, 6]]), # (['a', 'b', 'c', 'c', 'b', 'a', 'b', 'c'], [['a', 'b', 'c'], ['a', 'b', 'c'], ['b', 'c']]), ([1, 2, 3, 2, 1, 4, 5, 6], [[1, 2, 3], [1, 2], [4, 5, 6]]), ([6, 5, 5, 5, 4], [[4, 5, 5, 5, 6]]), ([5, 5, 5, 5, 6, 7, 6, 5, 5, 5], [[5, 5, 5, 5, 6, 7], [5, 5, 5, 6]]), ] for seq, expected in seqs: self.assertEqual( list(mono(seq)), expected, ) Test()Approaches with iter or generators requires comments as non-beginner friendly, or even for "future us".
This solution address as well the case of multiple mono-item groups like suggested in the first comment by jiamo:
def monotonic(sequence): # with 2 or less elements, the result is one group if len(sequence) < 3: return [sorted(sequence)] # First group starts with first number groups = [] group = [sequence[0]] previous = sequence[0] forward = None for number in sequence[1:]: # if the group has one item only, extend it if len(group) == 1: group.append(number) forward = group[0] < group[1] # if it's a monotonic group and the number # respects direction, append it elif (number > previous and forward) or (number < previous and not forward): group.append(number) # otherwise a change of direction happened, restart with a new group else: groups.append(sorted(group)) group = [number] forward = None previous = number # add the last group groups.append(sorted(group)) return groupsAdd a comment: