Hacker News new | past | comments | ask | show | jobs | submit login
Pythonic monotonic (nedbatchelder.com)
64 points by ingve 10 months ago | hide | past | favorite | 57 comments



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.


Here's my solution:

    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.


The one where the logic is the most clear, in straightforward imperative style, is also the one with the fewest bugs. Nice one!


Nice! It passes all of my tests, including cross-comparison with my code on random sequences. And it's delightfully clear.


IMO either would be simpler if they used comments to explain _why_ the code is doing what it's doing


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:

  >>> monotonic([2, 1, 1, 1, 1, 2])
  [[1, 2], [1, 1], [1, 1], [1, 2]]
Otherwise a readable and straightforward implementation of a somewhat underspecified problem.


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:

  >>> monotonic([2, 2, 1])
  [[2, 2], [1]]

  >>> monotonic([1, 1, 2])
  [[1, 1, 2]]
As a separate detail, zeros are regarded false in Python:

  >>> monotonic([1, 2, 1, 0])
  [[1, 2], [1]]


Fails for

  [1, 1, 2, 3, 3, 2, 1, 1] -> [[1, 1, 2, 3, 3], [1, 2], [1, 2], [1]]


Thanks. I was inconsistent in my use of >= and >. Making them consistent has fixed this edge case.


Also fails for

  [3, 3, 2, 2, 1, 1] -> [[3, 3], [2, 2], [1, 1]]
Here's my solution https://news.ycombinator.com/item?id=28170735


And for [1]; the "return sorted(arr)" needs to be "return [sorted(arr)]".


I couldn't resist.

    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.


Oops, it doesn't reverse decreasing runs. Make that:

    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)
                if cmp == op.gt:
                    run = list(reversed(run))
                yield run
        if len(lst) == 1:
            yield lst


If-statements are for the weak :-)

This uses numpy, but it's the shortest answer presented thus far.

    In [1]: 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()[0]
       ...:     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]: [[1, 2, 3], [1, 2], [4, 5, 6, 7]]


Gave it another shot:

    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.

You can continue to pare it down.


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!


self documenting code ;-)

  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!

  >>> print(list(monotonic([1, 1, 2, 3, 3, 2, 1, 1])))
  [[1], [1], [2, 3], [1, 1, 2, 3]]
  >>> list(mono_runs_simpler([1, 1, 2, 3, 3, 2, 1, 1]))
  [[1], [1], [2, 3], [1, 2, 3], [1]]
That should be (IMO):

  [[1, 1, 2, 3, 3], [2, 1, 1]]
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:

  >>> list(monotonic_direct([10, 9, 8]))
  [[10], [9, 8]]
As such, the original reference "Monotonic" implementation is wrong, as well as Ned's version!

  >>> list(mono_runs_simpler([10, 9, 8]))
  [[10], [9, 8]]
It should be [[10, 9, 8]].


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.


Yes, the -inf approach gives the wrong answer. It's seems clever at first, but induces an invalid mental assumption.


Great breakdown.

I find myself running into the same limitation sometimes-- functools/itertools are only so flexible.


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.


So this only works for numbers right?


Only some numbers.

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.

This is left as an exercise for the reader. ;)


If they use math.inf then yeah probably.

You might be able to create an object that always compares as less than something, using something like:

    class Bottom:
        def __le__(self, other):
            return True

        def __lt__(self, other):
            return True
though use this with care.


The first case is clearer to me than the second, by quite away.

Iter, next? Opaque testing of [-1] values?

Adjusting a few identifier names, the first actually describes what's going on.

Eg., rename `Monotonic()` to `CurrentLtLast()`


It's really hard to do anything in python without `iter` and `next` - understanding iterators and `iter` in particular is table stakes with python.


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.


`iter` seems more approachable than `__call__` to me FWIW.


What's wrong with iter and next?


I’m not a python dev. Can anyone brrakdown the first code? I’m a bit confused


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".


i think thats the point the article is making? don't just use a tool or lib, but understand how generators work. that is more pythonic. am i right?


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.


And the author's solution does not work with empty sequences.


How now APL?


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
    }
Run online: https://mlochbaum.github.io/BQN/try.html#code=TW9ub1J1bnMg4o...

https://mlochbaum.github.io/BQN/doc/shift.html

https://mlochbaum.github.io/BQN/doc/group.html


Neat link to working code!

"⟨3, 2, 1⟩" generates "⟨ 2 1 3 ⟩". I expected "⟨1, 2, 3⟩".


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).


⟨1, 1, 2⟩ goes to ⟨ ⟨ 1 1 ⟩ ⟨ 2 ⟩ ⟩. I expected ⟨ ⟨1, 1, 2⟩ ⟩

This task is surprisingly tricky!


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.


Choosing either implementation as "more Pythonic" than the other feels to me like choosing tabs over spaces, or vice versa:

https://www.youtube.com/watch?v=V7PLxL8jIl8

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.




LOL. That cartoon is particularly funny because it is rather insightful about the nature of such disagreements.


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.


No. Once you've internalized the idioms of the language, it becomes obvious that TFA's preferred solution is in the Python style and the other is not.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: