単調非減少と単調非増加で配列（Enumerator）を切断する

要するにこれです。
atcoder.jp

配列 A が与えられます。 A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。

コード

Enumerable にこんなメソッドupdown_cutを生やしてみました。

module Enumerable
  def updown_cut
    e = to_enum
    updown = 0
    
    calc = ->(compare) {
      case updown
      when 0 then [compare, false]
      when -1
        case compare
        when -1, 0 then [-1, false]
        else [0, true]
        end
      else
        case compare
        when 1, 0 then [1, false]
        else [0, true]
        end
      end
    }
    
    begin
      a = e.next
    rescue StopIteration
      return self
    end
    
    pool = [a]
    loop do
      b = e.next
      updown, f = calc.(a <=> b)
      a = b
      if f
        yield pool
        pool = [a]
      else
        pool << a
      end
    end
    yield pool
    self
  end
end

使い方

配列（あるいは Enumerator）を単調非減少、あるいは単調非増加な配列になるよう切ってくれます。切られた配列はブロック変数に入ります。

[1, 2, 3, 2, 2, 1].updown_cut { p _1 }
#=>
#[1, 2, 3]
#[2, 2, 1]

ary = ([*1..7] * 2).shuffle
#=>[3, 1, 2, 7, 6, 7, 6, 5, 1, 5, 4, 4, 3, 2]
ary.enum_for(:updown_cut).to_a
#=>[[3, 1], [2, 7], [6, 7], [6, 5, 1], [5, 4, 4, 3, 2]]

str = ("abcdef" * 4).chars.shuffle.join
#=>"ecfdedcfecbabbbadfadcaef"
str.each_char.enum_for(:updown_cut).map(&:join)
#=>["ec", "fd", "edc", "fecba", "bbba", "df", "ad", "ca", "ef"]

　
いやあ、苦労しました。