Finding the number of "monotonicity flips" in a Seq[Int] in Scala

gistfile1.scala

// Finds the monotonicity breaks in a numerical sequence.
def findMonotonicityBreaks(items: Seq[Int]): Int = {
  def comp(op: Symbol, a: Int, b: Int) = if (op == '<=) a <= b else a >= b
  def flip(op: Symbol) = if (op == '<=) '>= else '<=
  
  @tailrec
  def detect(pairs: Seq[(Int, Int)], op: Symbol, breaks: Int): Int = {
    pairs match {
      case Seq() => breaks
      case Seq((a, b), rest @ _*) if comp(op, a, b) => detect(rest, op, breaks)
      case _ => detect(pairs, flip(op), breaks + 1)
    }
  }
  
  if (items.isEmpty) 0
  else {
    val pairs = items.zip(items.tail)
    pairs.collectFirst {
      case (a, b) if a < b => '<=
      case (a, b) if a > b => '>=
    }.map { op => detect(pairs, op, 0)
    }.getOrElse(0)
  }
}

// Usage:

scala> findMonotonicityBreaks(Seq.empty[Int])
res21: Int = 0

scala> findMonotonicityBreaks(Seq(0,1,2,3,4,4,4,4,5,6))
res22: Int = 0

scala> findMonotonicityBreaks(Seq(0,1,2,3,3,3,2,1))
res23: Int = 1

scala> findMonotonicityBreaks(Seq(1,2,3,4,5,6,5,4,5,6,7))
res24: Int = 2

scala> findMonotonicityBreaks(Seq(5,4,3,2,1,0))
res25: Int = 0

scala> findMonotonicityBreaks(Seq(7,6,5,4,5,6,5,4,3,2,1))
res26: Int = 2

scala> findMonotonicityBreaks(Seq(1,2,3,3,3,2,1,0))
res27: Int = 1

scala> findMonotonicityBreaks(Seq(1,2,3,4,5,6,5,4,5,6,7,6,5,4,3))
res28: Int = 3

scala> findMonotonicityBreaks(scala.util.Random.shuffle(Vector.range(1, 100000)))
res29: Int = 66498

scala> findMonotonicityBreaks(Seq(5,5,5,4,3,2,1,0))
res30: Int = 0

scala> findMonotonicityBreaks(Seq(5,5,5,4,3,2,1,0,2,3,4,5))
res31: Int = 1

scala> findMonotonicityBreaks(Seq(1,1,1,1,2))
res32: Int = 0

scala> findMonotonicityBreaks(Seq(1,1,1,1,2,1))
res33: Int = 1

I think this is easier to understand, and possibly faster:

scala> case class Tonicity(op: Symbol, count: Int, last: Int) {
     |   def +(n: Int) = {
     |     if ((op == '<= && n < last) || (op == '>= && n > last))
     |       Tonicity(if (op == '<=) '>= else '<=, count + 1, n)
     |     else
     |       Tonicity(op, count, n)
     |   }
     | }
defined class Tonicity

scala> def findMonotonicityBreaks(items: Seq[Int]): Int = {
     |   val rest = items.tail
     |   val seed = if (items.head <= rest.head) Tonicity('<=, 0, rest.head) else Tonicity('>=, 0, rest.head)
     |   val tones = rest.foldLeft(seed) { case (acc, i) => acc + i }
     |   tones.count
     | }
findMonotonicityBreaks: (items: Seq[Int])Int

Would be a great interview question btw.

Nice, @velvia!

How about this?

def findMonotonicityBreaks(items: Seq[Int]): Int = 
  items.sliding(2).
  map{p => if (p(0) > p(1)) '<= else '=>}.
  sliding(2).
  count{p => p(0) != p(1)}

Your version fails on empty sequences, by the way.

@velvia, oops, I think your solution may not work for all cases, e.g.:

scala> velvia.findMonotonicityBreaks(Seq(5,5,5,5,5,4,3,2,1,0))
res2: Int = 1

That's a really nice, succinct, and fast solution @willf!!! I like it. I also updated mine to handle empty sequences.

Although I think your solution also reports a break when it shouldn't, @willf:

scala> willf.findMonotonicityBreaks(Seq(5,5,5,5,5,4,3,2,1,0))
res5: Int = 1

heh. And it breaks on Seq(5,4). So, not correct. Must remember that sliding(n) can return fewer than n items!

Try this!

def findMonotonicityBreaks(items: Seq[Int]): Int = 
  items.sliding(2). // two items at a time
  filter(p => p.size == 2 && p(0) != p(1)). // remove any equalities
  map{p => p(1).compare(p(0))}. // get -1 and 1 values; must have 2 values
  sliding(2). // take *these* two at a time
  count(p => p.size == 2 && p(0) != p(1)) // count when the differ

This could the a start of another approach... I think it could be made less verbose, but it should be pretty fast, just integer ops and a tailrec traversal of the list

def  findMonotonicityBreaks(items:Seq[Int]):Int={
    @tailrec
    def breaksRec(itms:Seq[Int],currMono:Int, count:Int):Int=itms match {
      case x::y::ys=> {
        val newMono=x.compare(y)
        val c=if (newMono != 0 && newMono != currMono) 1 else 0
        breaksRec(y::ys,newMono,count+c )
      }
      case _ => count
    }
    items match {
      case x::y::xs =>breaksRec(items,0,0)-1
      case _=>0
    }
  }

Need to figure out a better way of discard the first monotonicity "change" (maybe use a Option) instead of doing total-1 at the end :)

Like this:
https://gist.github.com/gclaramunt/6021242

def  findMonotonicityBreaks(items:Seq[Int]):Int={
    @tailrec
    def breaksRec(itms:Seq[Int],currMono:Option[Int], count:Int):Int=itms match {
      case x::y::ys=> {
        val newMono=x.compare(y)
        val c=currMono.map(cm=>if (newMono != 0 && newMono != cm) 1 else 0).getOrElse(0)
        breaksRec(y::ys,Some(newMono),count+c )
      }
      case _ => count
    }
    breaksRec(items,None,0)
  }

Great solutions, guys! Aren't Scala collections fun?