Pythonic monotonic

Re:Pythonic monotonic by mlochbaum on Friday August 13, 2021 @01:13PM (#28171669)

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

[ Parent | on HN ]

Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @01:21PM (#28171776)

Neat link to working code!

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

[ Parent | on HN ]

Re:Pythonic monotonic by mlochbaum on Friday August 13, 2021 @01:30PM (#28171865)

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

[ Parent | on HN ]

Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @02:57PM (#28172915)

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

This task is surprisingly tricky!

[ Parent | on HN ]

Re:Pythonic monotonic by mlochbaum on Friday August 13, 2021 @03:25PM (#28173375)

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.

[ Parent | on HN ]