Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pythonic monotonic

nedbatchelder.com

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Pythonic monotonic

#51

Post by mlochbaum »

eesmith wrote: post #50
mlochbaum wrote: post #47

Earlier quoted context omitted.

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

Re: Pythonic monotonic

#52

Post by xorcist »

alecst wrote: post #42
xorcist wrote: post #35

Earlier quoted context omitted.

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…

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]]

Re: Pythonic monotonic

#53

Post by xorcist »

wmanley wrote: post #46

Here's my solution: def monotonic(it): run = [] for this in it: if not run: pass elif run[0] 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 ap…

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

Re: Pythonic monotonic

#54

Post by comex »

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

Re: Pythonic monotonic

#55

Post by eesmith »

mlochbaum wrote: post #51
eesmith wrote: post #50

Earlier quoted context omitted.

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!

Re: Pythonic monotonic

#56

Post by mrtranscendence »

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

Re: Pythonic monotonic

#57

Post by mrtranscendence »

mrtranscendence wrote: post #56

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] This assumes you're operating on lists and that monotonicity is strict. It's reasonably…

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]

Re: Pythonic monotonic

#58

Post by mlochbaum »

eesmith wrote: post #55
mlochbaum wrote: post #51

Earlier quoted context omitted.

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.

Re: Pythonic monotonic

#59

Post by klyrs »

eesmith wrote: post #31
pierrebai wrote: post #25

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 in…

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…

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[::-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]

Re: Pythonic monotonic

#60

Post by alecst »

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

Post reply on HN