# Pythonic monotonic

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 itertoolsdef 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. mono_runs_simpler([1, 2, 3, 2, 1, 8, 4, 5, 6, 7])
got
[[1, 2, 3], [1, 2], , , [5, 6, 7]]
why not
[[1, 2, 3], [1, 2], , [4, 5, 6, 7]]
or
[[1, 2, 3], [1, 2], [4, 8], [ 5, 6, 7]] Yep, the bug is that is assumes that consecutive runs alternate between increasing and decreasing, when that can only be assessed by looking at two numbers. Best example to demonstrate this is multiple runs of the same increasing sequence:

[1, 2, 3, 1, 2, 3, 1, 2, 3] should yield [ [1, 2, 3], [1, 2, 3], [1, 2, 3] ] Proposal
```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 run
``` Wolfgang Richter 1:27 PM on 13 Aug 2021
Ned I think you should cite PEP 20. This feels like a PEP 20 violation, and to me that is what makes it not Pythonic.

Yours 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! My solution:
```one_liner = lambda l: [sorted(l[f:g]) for f,g in zip(*[[e[:-1],e[1:]] for e in [+[d for d in c if d-1 not in c or d-2 in c]+[len(l)] for c in [set([a for a,b in enumerate([0,0]+np.ediff1d(np.sign(np.ediff1d(l))).tolist()) if b!=0])]]])]

>>> one_liner([1, 2, 3, 2, 1, 8, 4, 5, 6, 7])
[[1, 2, 3], [1, 2], [4, 8], [5, 6, 7]]

>>> one_liner([1,2,3,1,2,3,1,2,3])
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]

>>> one_liner([1, 2, 3, 2, 1, 4, 5, 6, 7])
[[1, 2, 3], [1, 2], [4, 5, 6, 7]]
```
I've decided that anyone that asks a silly question in an interview should get a silly answer. Arnaud Delobelle 2:28 PM on 13 Aug 2021
Here is a differently unpythonic one:
```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)
]

``` Splitting the direction check into a separate function (not sure what to name it) cleans the logic up a lot and makes things a lot more readable (and possibly pythonic) in my opinion.
```def mono_runs_direction(a, b):
if a > b:
return -1
else:
return 1

def mono_runs_pythonic(arr):
runs = []
run = [arr]
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 runs
``` I love the phrase "reading with my eyebrows"! Is it assumed that the input sequence is non-empty? I think the first example will return an empty list in that case, while the second example will fail. First I'm not a coder. What struck me, was the question was part of an interview. And it seemed to me that the purpose of the interview problem, was not to demonstrate the interviewees capability. But rather for the interviewer to demonstrate how much smarter they were than the new guy. Perhaps the question could have been better, if it had been presented as, show me how you approach a problem like this. Not, show me this niche solution. @James - exactly! From my experience interviewing people for roles in data science, a question like this is a great way to spend 15-20 minutes trying to figure out what you could assess in a 2 minute question. That's how you end up with these 10-hour long leetcode interviews with a take home to finally get the answer "Wow this person really knows language X" when you could have asked a few quick targeted questions that would have highlighted bad vs good vs great candidates. But, of course, those types of targeted questions require solid domain knowledge on the part of the interviewer. "Solve this arbitrary problem I googled - it's pass/fail" is easy but also working harder, not smarter. Travis Mehlinger 5:10 PM on 13 Aug 2021
Use the itertools, Luke!
```import 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:
```[[1, 2, 3], , [1, 4, 5, 6, 7], [1, 2]]
[[1, 2], , [1, 4, 5], [1, 7], [1, 2]]
[, , , , ]
[]
``` Travis Mehlinger 5:28 PM on 13 Aug 2021
I missed reversing the decreasing runs, d'oh. Hmmm, for [5, 4, 3, 2 ] both versions return [, [4, 3, 2]] . An empty list is also challenging them, as well as inputs like [1, 1, 2].

I have a simple minded solution to the problem, which handles the edge cases as well:

https://gist.github.com/babo/f93fd294a93cc9e4ccbb0723d7a5cb25 Here's a recursive solution that doesn't import anything:
```def mono(seq):
if len(seq) == 1:
yield seq
elif len(seq) >= 2:
up = seq > seq # 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. And now a version that handles consecutive equal numbers:
```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:
```>>> mono([])
[]
>>> mono()
[]
>>> mono([1,2])
[[1, 2]]
>>> mono([1,1])
[[1, 1]]
>>> mono([2,1])
[[1, 2]]
>>> mono([1,2,3,2,1])
[[1, 2, 3], [1, 2]]
>>> mono([3,2,1,2,3])
[[1, 2, 3], [2, 3]]
>>> mono([1,1,2,2,1,1,2,2,1,1])
[[1, 1, 2, 2], [1, 1, 2, 2], [1, 1]]
``` Hmm... It seems that this comment system doesn't like it if my code uses the <= operator without escaping it, even within a <pre> block...
```
In : from itertools import chain, zip_longest
...: import numpy as np
...:
...: def f(l):
...:     a = np.array([-np.inf, *l])
...:     up = a[:-1] <= a[1:]
...:     pos = (up[1:] != up[:-1]).nonzero()
...:     pos = [0, *(1+pos), len(l)]
...:     up_runs = (l[x:y] for x,y in zip(pos[0::2], pos[1::2]))
...:     down_runs = (l[y-1:x-1:-1] for x,y in zip(pos[1::2], pos[2::2]))
...:     pairs = zip_longest(up_runs, down_runs)
...:     return [*filter(None, chain(*pairs))]
...: f([1, 2, 3, 2, 1, 4, 5, 6, 7])
...:
Out: [[1, 2, 3], [1, 2], [4, 5, 6, 7]]

``` ```
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))]
``` @Coady nice use of multi-argument map(). BTW, chain() is unnecessary:
```keys = [True, *map(operator.le, seq, seq[1:])]
``` @Stuart

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. Kyle lahnakoski 3:16 PM on 14 Aug 2021
I wanted a bumpy solution, but runs of identical values made it difficult. The proposed numpy solution gives strange output on [6,5,5,5,4]. Wow, thanks for all the alternatives! It's going to take me a bit to sift through these and see what people have come up with. Also, the Hacker News thread has plenty of code also: https://news.ycombinator.com/item?id=28167300 This feels pythonic to me:
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 =  + [i+1 for i,extremum in enumerate(extrema) if extremum]
monotonics = [sorted(l[a:b]) for a,b in zip(runs,runs[1:])]
return monotonics
``` It also occurred to me just now that the problem statement says "values", and many of the solutions assume to some extent that these are numeric values.

This 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? Sorry if it sounds harsh but I skipped to reading Ned's solution and it was so tick and complex I gave up. The first solution is really easy to understand - the only prerequisite is knowing what groupby does - I doubt that is a little known corner of stdlib. And if it is, it shouldn't be.

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. I tried many of the offered solutions and they seem to fail with several general cases, but maybe I'm missing something fundamental.

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.

```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],   [, , [2, 3], [1, 2], [1, 2, 3]]),
([1, 2, 3, 3, 3, 4, 5, 5, 6],   [[1, 2, 3], , [3, 4, 5], [5, 6]]),
([2, 1],                        [[1,2]]),
(,                          []),
([],                            []),
(['a', 'b', 'c', 'c', 'b', 'a', 'b', 'c'],
[['a', 'b', 'c'], ['a', 'b', 'c'], ['b', 'c']]),
]

for seq in seqs:
result = mono(seq)
print(f'Input:    {seq}')
print(f'Result:   {result}')
print(f'Expected: {seq} {result == seq} \n')
```
RESULTS:
```Input:    [1, 2, 3, 1, 2, 3, 1, 2, 3]
Result:   [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Expected: [[1, 2, 3], [1, 2, 3], [1, 2, 3]] True

Input:    [1, 2, 3, 3, 2, 1, 1, 2, 3]
Result:   [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Expected: [[1, 2, 3], [1, 2, 3], [1, 2, 3]] True

Input:    [1, 2, 3, 3, 2, 1, 2, 3]
Result:   [[1, 2, 3], [1, 2, 3], [2, 3]]
Expected: [[1, 2, 3], [1, 2, 3], [2, 3]] True

Input:    [1, 2, 3, 2, 1, 4, 5, 6, 7]
Result:   [[1, 2, 3], [1, 2], [4, 5, 6, 7]]
Expected: [[1, 2, 3], [1, 2], [4, 5, 6, 7]] True

Input:    [3, 2, 1, 1, 2, 3, 3, 2, 1]
Result:   [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Expected: [[1, 2, 3], [1, 2, 3], [1, 2, 3]] True

Input:    [3, 3, 3, 2, 2, 1, 1, 2, 3]
Result:   [, , [2, 3], [1, 2], [1, 2, 3]]
Expected: [, , [2, 3], [1, 2], [1, 2, 3]] True

Input:    [1, 2, 3, 3, 3, 4, 5, 5, 6]
Result:   [[1, 2, 3], , [3, 4, 5], [5, 6]]
Expected: [[1, 2, 3], , [3, 4, 5], [5, 6]] True

Input:    [2, 1]
Result:   [[1, 2]]
Expected: [[1, 2]] True

Input:    
Result:   []
Expected: [] True

Input:    []
Result:   []
Expected: [] True

Input:    ['a', 'b', 'c', 'c', 'b', 'a', 'b', 'c']
Result:   [['a', 'b', 'c'], ['a', 'b', 'c'], ['b', 'c']]
Expected: [['a', 'b', 'c'], ['a', 'b', 'c'], ['b', 'c']] True
``` Hi. Very interesting topic about readability. But my reaction to examples I see in posts, and comments are that no example describes the domain of the problem that is solved. So I give it a try and describe my reflections on it here. And my code is like this
```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)

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()]
``` Love this problem. I had a few goes but so far I'm not happy with any of my solutions. I agree that the original solution cannot be considered "pythonic" as it is really hard to read. Actually to be quite frank none of the solutions in the comments is readable. Not knowing the problem we are trying to solve it is hard to figure it out by simply reading the solutions. There are a lot of clever solutions but none of them would impress me if I was the interviewer. For me the readability of the code is the most important quality. ```import pytest

class Grp():

def __init__(self):
self.elements = []
self.direction = None

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)

prev = el

return [sorted(g.elements) for g in grps]

class Test_mono():
@pytest.mark.parametrize("input,res", [
([], [[]]),
(, []),
([1, 2], [[1, 2]]),
([2, 1], [[1, 2]]),
([1, 2, 3, 2], [[1, 2, 3], ]),
([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) == res

``` @Pawel

Can 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 = [
([], []),
(, []),
([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()
``` For me, a pythonic code is something anyone can read without unnecessary complications.
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]
previous = sequence
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 < group
# 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

groups.append(sorted(group))

return groups
```