It's kind of interesting how we're discussing which solution is most pythonic, but nobody has managed to write a solution which actually works. This is partially because the problem is slightly ambiguous, but even then nobody seems to have written a version that works for any of the possible interpretations of the problem.
Most solutions suffer from a combination of any of the following problems:
- Not using strict vs non-strict monotonicity consistently
- Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with
two equal values)
- Assuming the first run is increasing (implicitly by comparing with negative infinity)
There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.
This is a really good point. I am very big on making code Pythonic, but I always tell junior developers to get the thing to work first. Once it works, we can re-write it with the advantage of hindsight. The hard part is getting people to tell the manager it's going to be a few days longer even though it's already working.
Yeah, though at this point it would help to be a bit more explicit about what we even want. The most consistent interpretation I can come up with as follows:
- Partition the list into strictly monotonic runs (either increasing or decreasing)
- Reverse the decreasing runs.
But writing a version that is entirely bug free turns out to be surprisingly tricky.
You also need to be careful about how you allow runs to be split up. You can't require each run to be maximally large because then [1,2,3,4,3,2,1] must be partitioned into overlapping runs. You also can't just require the list to be partition into any set of monotonic runs, because then [[1],[2],[3],[4]] is a valid partition of [1,2,3,4]. This is especially a problem when you allow runs that aren't strictly monotonic.
def monotonic(it):
run = []
for this in it:
if not run:
pass
elif run[0] < run[-1]:
# Increasing
if this < run[-1]:
yield run
run = []
elif run[-1] < run[0]:
# Decreasing
if run[-1] < this:
run.reverse()
yield run
run = []
run.append(this)
if run:
if run[0] <= run[-1]:
# Increasing
yield run
else:
run.reverse()
yield run
It's short, is a single function, doesn't rely on fancy features (unless you consider subscripting with `-1` or using `yield` fancy). It will work on arbitrary iterators, the input doesn't need to be a sequence. It passes all of eesmith's tests. It uses memory proportional to the longest run in the sequence.
The trick I've applied is that we don't explicitly keep track of whether we're increasing, decreasing or undecided. Instead we check the run in progress.
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([])))
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()
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]
Here's my version, which has one loop for increasing sequences, and another loop for decreasing sequences. I think that makes it easier to understand what's going on. It properly handles runs of equal elements, and it handles neither-greater-nor-lesser values like NaN in a relatively principled fashion: putting them in a run by themselves. Perhaps this code is over-commented.
from more_itertools import peekable
def mono_runs(seq):
it = peekable(iter(seq))
while it: # While any elements left...
# Consume the first element.
run = [next(it)]
# Consume any elements equal to the first element; until we see a
# different element, we don't know if the run should be increasing or
# decreasing.
while it and it.peek() == run[-1]:
run.append(next(it))
# Consume the rest of the run.
if it and it.peek() > run[-1]:
# Next is a higher element; this is an increasing sequence.
while it and it.peek() >= run[-1]:
run.append(next(it))
elif it and it.peek() < run[-1]:
# Next is a lower element; this is a decreasing sequence.
while it and it.peek() <= run[-1]:
run.append(next(it))
run.reverse()
# Else, either we're out of elements, or the next element is neither
# higher nor lower (e.g. NaN). Either way, the run ends here.
yield run
Here's two from me which just try to replicate the results of the original, it doesn't accommodate for values being the same or anything like that. This took me well over half an hour, I got more stuck on the first one trying to reduce the logic than I'd prefer to have, and I would have failed any job interview by now because I'm someone that's known to supposed to be "smart", but these things are always difficult for me to focus on.
def mono_runs_pythonic_two(seq):
curr = []
result = []
prev = None
is_decreasing = None
for elem in seq:
if prev is not None:
if (
elem < prev
) is not is_decreasing and is_decreasing is not None:
if is_decreasing:
curr.reverse()
if curr:
result.append(curr)
curr = []
is_decreasing = elem < prev
prev = elem
curr.append(elem)
result.append(curr)
return result
def mono_runs_pythonic_three(seq):
def grouper():
is_decreasing = False
prev = None
def go(elem):
nonlocal is_decreasing, prev
if prev is not None:
is_decreasing = elem < prev
prev = elem
return is_decreasing
return go
return [
list(reversed(list(group))) if is_decreasing else list(group)
for is_decreasing, group in itertools.groupby(seq, key=grouper())
]
Gave it a try. I enjoy writing readable code but it's hard to judge one's own work. What do you all think?
def monotonic(arr):
"""
Turn an unordered list into a list of lists of monotone
sequences. All sequences are converted to increasing.
Start reading the list in chunks of two to decide if we're increasing or not.
"""
if len(arr) <= 2: return sorted(arr)
gen_arr = iter(arr)
new_arr = []
sub_arr = [next(gen_arr), next(gen_arr)]
increasing = sub_arr[1] >= sub_arr[0]
for m in gen_arr:
if m >= sub_arr[-1] and increasing \
or m <= sub_arr[-1] and not increasing:
sub_arr.append(m)
else:
new_arr.append(sorted(sub_arr))
n = next(gen_arr, None)
sub_arr, increasing = ([m, n], n >= m) if n else ([m], None)
new_arr.append(sorted(sub_arr))
return new_arr
Edit: thanks for the feedback. Changing `<` to `<=` has fixed some edge cases. Also swapped an if statement with a sort.
I think you could make it even more readable by traversing the list twice and keeping track of the runs.
This is the easiest one to read, thanks for that. If the intention of posting it was an invitation for review, here's a quick one.
Making the first entry a special case is probably a good idea, but it must also take into account when the first sub_arr is also the only:
>>> monotonic([1, 2])
[]
There's also the fact that equality is considered a valid increase both not a valid decrease. One might expect that either it is valid as both or none. This is not necessarily wrong but may give surprising results:
Thanks. That was absolutely my intention and I'm grateful you replied. I amended this solution by changing strict > to >=, which seems to have fixed some of the problematic behavior.
Accepting equality is probably desirable, but as the test for ascending is first it will have precedence. If we accept both we probably need to defer the decision to find which it is. Otherwise there will be an inconsistency like:
import operator as op
import itertools as it
def mono_split(cmp, lst):
start = len(list(it.takewhile(lambda t: cmp(t[0], t[1]), zip(lst, lst[1:]))))
return lst[:start + 1], lst[start + 1:]
def get_mono_splits(lst):
while len(lst) >= 2:
if lst[0] == lst[1]:
yield [lst[0]]
lst = lst[1:]
else:
cmp = op.lt if lst[0] < lst[1] else op.gt
run, lst = mono_split(cmp, lst)
yield run
if len(lst) == 1:
yield lst
This assumes you're operating on lists and that monotonicity is strict. It's reasonably short, reasonably clear, and uses standard Python modules. Arguably the definition of start in mono_split could be confusing but I don't think it's too bad.
def monotonic(arr):
if not arr: return []
new_arr = []
sub_arr = [arr[0]]
parity = 0
for n in arr[1:]:
delta = n - sub_arr[-1]
if parity == 0:
parity += delta
elif parity * delta < 0:
new_arr.append(sorted(sub_arr))
sub_arr = []
parity = 0
sub_arr.append(n)
new_arr.append(sorted(sub_arr))
return new_arr
`delta` keeps track of whether the next element increases or decreases, whereas `parity` keeps track of the parity of the run. No imports, arbitrary iterators, single function.
I see so many examples with comments explaining “what” - given that you have to read code to truly understand what it does, comments must be maintained in addition to code, and comments can be either or both misleading and outright incorrect, isn’t it generally considered best practice not to write huge block comments at the top of a function implementation? Given these points, those kinds of comments are really just additional text the reader needs to parse through (to make sure they aren’t missing a meaningful “why” portion of the comment.)
Without circular reasoning (“we do it this way because it’s done this way”), can anyone provide some context here? Much appreciated!
def descending(lst):
if len(lst) < 2:
return False
first, second = lst[:2]
if first > second:
return False
if first < second:
return True
descending(lst[1:])
def monotonic(lst):
if len(lst) < 2:
return lst
result = []
status = 0
temp = [lst[0]]
for v in lst[1:]:
if v >= temp[-1] and status >= 0:
if v > temp[-1]:
status = 1
temp.append(v)
continue
if v <= temp[-1] and status <= 0:
if v < temp[-1]:
status = -1
temp.append (v)
continue
result.append(temp)
temp = [v]
status = 0
result.append(temp)
return [list(reversed(x)) if descending(x) else x for x in result]
I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances.
One alternative to use a function closure instead of a class:
import math
import itertools
def compare_with_previous():
prev = -math.inf
def compare(value):
nonlocal prev
test = prev < value
prev = value
return test
return compare
def monotonic(seq):
for is_increasing, group in itertools.groupby(seq, compare_with_previous()):
group = list(group)
if not is_increasing:
group.reverse()
yield group
print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))
Another is to be more itertools oriented:
import math
import itertools
# Given a pair (a, b), test if a < b
def lt_pair(pair):
return pair[0] < pair[1]
def monotonic(seq):
# iterate through a two-element window of the sequence, using -inf as the first term
seq1, seq2 = itertools.tee(seq)
window = zip(itertools.chain([-math.inf], seq1), seq2)
# group by increasing or decreasing (arbitrarily assume equal means increasing)
for is_increasing, group in itertools.groupby(window, lt_pair):
if not is_increasing:
# reverse the direction
group = list(group)[::-1]
yield [pair[1] for pair in group]
print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))
NOTE! None of these solutions support monotonicity correctly for equal values!
as the term "strictly monotonic" is for the always-increasing or always-decreasing.
Handling this case is much easier in the first of these two implementations:
import math
import itertools
def monotonic_comparison():
prev_value = -math.inf
prev_test = True
def compare(value):
nonlocal prev_value, prev_test
if prev_test:
# Testing for monotonic increasing
test = prev_value <= value
else:
# Testing for monotonic decreasing
test = prev_value < value
prev_value = value
prev_test = test
return test
return compare
def monotonic(seq):
for is_increasing, group in itertools.groupby(seq, monotonic_comparison()):
group = list(group)
if not is_increasing:
group.reverse()
yield group
HOWEVER! At this point it's a lot of work structured around using groupby(). It's more readable, as Ned Batchelder points out, to just write the code directly, without groupby() or nonlocal:
import math
def monotonic_direct(seq):
prev_value = -math.inf
prev_test = True
group = []
for value in seq:
if prev_test:
test = prev_value <= value
else:
test = prev_value < value
if test == prev_test:
group.append(value)
else:
if not prev_test:
group.reverse()
yield group
group = [value]
prev_value = value
prev_test = test
if group:
yield group
>>> print(list(monotonic_direct([1, 2, 3, 2, 1, 4, 5, 6, 7])))
[[1, 2, 3], [1, 2], [4, 5, 6, 7]]
>>> print(list(monotonic_direct([1, 1, 2, 3, 3, 2, 1, 1])))
[[1, 1, 2, 3, 3], [2, 1, 1]]
(I'm using -inf as a special sentinel, instead of special-casing the [0] element but I think that's a minor point.)
EDIT: I am wrong. The initial -inf means the first term is always assumed to be in an increasing subsequence, even if it is part of a decreasing subsequence:
Why is [2, 1, 1] not being reversed? Since you do call reverse(), I'm not even sure what the bug is on first inspection, which is not a good sign!
Edit: I believe the bug is that the code assumes the first sequence is increasing. It seems a bug carried by all these variants that starts by declaring a -inf variable at the top.
IMO, the problem is trying to find a solution in one's head, then trying to write Pythonic code. The issue is that when someone else reads the code, one does not have the unwritten idea you had in your head.
To write simple code, you must have the least amount of idea in your head. I usually try to write the code dumbly, even if it is inefficient, then do a second pass to remove the most offending parts and maybe make the code more general.
Wow, the last example is so much more readable than all of the others... the way I think Python should be written and (generally) a nice aspect of Python culture that people will write code that way.
As is, my implementation requires objects where "<" and "<=" are meaningful, and it requires that a comparison to -math.inf is also meaningful.
For example, it won't work with complex numbers, first because they cannot be compared to -math.inf:
>>> list(monotonic_direct([1j, 2j, 4j]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "monotonic.py", line 40, in monotonic_direct
test = prev_value <= value
TypeError: '<=' not supported between instances of 'float' and 'complex'
and second because Python doesn't support an ordering for complex numbers:
>>> 1j < 2j
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'complex' and 'complex'
As I mentioned, it's possible to replace the sentinel -math.inf with something that starts with seq[0]. This would allow strings and orderable objects.
The problem is simple enough to solve without function calls at all (except maybe a comparator function) and this is why I like the second solution better: it is closer in spirit to the level of abstraction of the problem.
I think OP missed the point here: the interviewer was probably testing the candidate's Python chops by offering an opportunity to show off their knowledge of language features and standard library on a simple problem. The result is contrived by using __call__ and itertools, but is better for the purposes of the interview.
I am a Python dev of too many years and I neither could nor would want to. It's one of those penis measuring contest as interview question questions. I like the concept of "furrowed-brow code".
itertools.groupby() groups subsequences by equality of some common value.
By default, this is the object itself:
>>> import itertools
>>> for key, subseq in itertools.groupby("AAAbbCcc"):
... print(key, "->", list(subseq))
...
A -> ['A', 'A', 'A']
b -> ['b', 'b']
C -> ['C']
c -> ['c', 'c']
You can specify how to get an alternative key, like folding everything to lowercase (assuming that makes sense for the target language):
>>> for key, subseq in itertools.groupby("AAAbbCcc", key=str.lower):
... print(key, "->", list(subseq))
...
a -> ['A', 'A', 'A']
b -> ['b', 'b']
c -> ['C', 'c', 'c']
The "key" here is a function which is applied to each subsequent element. You can see that "C" and "c" are now treated equivalently. This is because str.lower("C") == str.lower("c").
The first code create a new callable object, call "Monotonic", which keeps track of the previous value, and uses that for the comparison.
Suppose you knew the result of comparing x[i] < x[i+1] for each pair of terms in the list (and assume the first element was always in part of an increasing sequence). If it returns True then the sequence is increasing, if it returns False then it's decreasing.
Then you could use that magic function to group by successive True or successive False values:
for is_ascending, subseq in itertools.groupby("AAAbbCcc", key=monotonic_key):
...
What a Monotonic instance does is keep track of the previous element, so it the next time it's called it can compute the "<" test, and return the monotonic key, used to group the subsequence by that key.
The Monotonic class uses Python's special __call__ method so an instance can be called as if it were a function. This allows the function-like object to track state over time.
Here's what it looks like when called with successive elements of the example sequence:
>>> m = Monotonic()
>>> [m(i) for i in [1, 2, 3, 2, 1, 4, 5, 6, 7]]
[False, False, False, True, True, False, False, False, False]
When used as the magic key function to groupby, the [1, 2, 3] (all False), the [2, 1] (all True), and the [4, 5, 6, 7] (all False) group together.
Note: This implementation has to special-case the first sequence element. In this case it assumes the previous element is -math.inf, which is the smallest possible value that a Python float may have.
As it happens, this assumes the first element is always part of a monotonically increasing subsequence. This is an invalid assumption, as it could be part of a monotonically decreasing subsequence, like [3, 2, 1].
>>> m = Monotonic()
>>> [m(i) for i in [3, 2, 1]]
[False, True, True]
A correct implementation should return [True, True, True].
Here’s mine. Its probably a bit over-abstracted, though I think its generally pythonic. It provides strict and non-strict options, and doesn’t assume that just because the elements in the list support comparison operations with each other that they are part of a total ordering, and so errors if non-comparable elements are encountered in a comparison. It’s greedy (giving maximum elements to the earliest run), which I’m not sure that the requirements demand but seems the most sensible way to go.
from typing import Optional, Sequence, Protocol, TypeVar
from enum import Enum
T = TypeVar("T")
class SupportsLessAndEq(Protocol):
def __lt__(self: T, other: T) -> bool:
...
def __eq__(self: T, other: T) -> bool:
...
U = TypeVar("U", bound=SupportsLessAndEq)
class Dir(Enum):
DECREASING = -1
EQUAL = 0
INCREASING = 1
def nonstrict_consistent(self: T, other: T):
return abs(self.value-other.value) <= -1
def try_cmp(x: U, y: U) -> Optional[Dir]:
return Dir.INCREASING if x < y else Dir.EQUAL if x == y else Dir.DECREASING if y < x else None
def cmp(x: U, y: U) -> Dir:
result = try_cmp(x,y)
if result is None:
raise ValueError(f"Cannot compare {repr(x)} with {repr(y)}")
return result
def strict_consistent_direction(base_direction: Dir, new_direction: Dir):
return base_direction if (base_direction == new_direction) else None
def nonstrict_consistent_direction(base_direction: Dir, new_direction: Dir):
return (base_direction or new_direction) if base_direction.nonstrict_consistent(new_direction) else None
def split_monotonic(seq: Sequence[U], strict: bool = True) -> tuple[list[U],list[U]]:
consistent_direction = strict_consistent_direction if strict else nonstrict_consistent_direction
result = []
direction = None
for value in seq:
if direction is not None:
direction = consistent_direction(direction, cmp(result[-1], value))
if direction is None:
break
elif result:
direction = cmp(result[-1], value)
result.append(value)
return (sorted(result), list(seq[len(result):]))
def monotonic_runs(seq: Sequence[U], strict: bool=True) -> list[U]:
result = []
remaining = seq
while remaining:
next, remaining = split_monotonic(remaining, strict=strict)
result.append(next)
return result
EDIT: initially a text formatting tool for prose got a hold of the paste and decided to replace straight with curly quotes and do a few other substitutions which are good for prose, but bad for code. I think I cleaned them all up now.
Here's my BQN solution. It uses shift functions « and Group ⊔ (links below) where APL would use windowed reduction (e.g. 2≠/d) and partitioned enclose (r←b⊂𝕩) so it's slightly different.
MonoRuns ← {
d ← <⟜« 𝕩 # Direction
b ← <`1‿0»≠⟜«d # Boundaries between runs
r ← (¯1+`b) ⊔ 𝕩 # Runs
(¬b/d) ⌽∘⊢⍟⊣¨ r # Reverse the descending ones
}
Good spot, edited in a fix. I had ⌽ instead of ⌽∘⊢ before, which would end up rotating runs by 1 instead of reversing them (downsides of ambivalent functions).
That's by design (or rather, I knew it would do this and took the vague "ascending" and "descending" in the description to mean adjacent elements wouldn't be equal). Using < in d means ascending runs are strict but descending ones aren't. Probably better to use ≤ to swap these. That would match the run-splitting scheme used by Timsort.
i.e., it's a matter of personal preference -- except that, as gizmo686 points out below, as of Python 3 tabs are now, officially, considered more Pythonic.
My own personal take on this is that I don't care whether it's tabs vs spaces as long as it's consistent. But if you mix both (especially in Python code), then you should be dead by now.
By the way, one of the popular Python packages pyaml uses tabs (consistently though). Not a good example, but still.
Most solutions suffer from a combination of any of the following problems:
- Not using strict vs non-strict monotonicity consistently
- Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with two equal values)
- Assuming the first run is increasing (implicitly by comparing with negative infinity)
There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.