Algorithm for searching the coordinates of a black box in a 2D image

searchBlackBox.scala

object Solution extends App {

  // Scala
  val image = Array(
    Array(1, 1, 1, 1, 1, 1, 1),
    Array(1, 1, 1, 1, 1, 1, 1),
    Array(1, 1, 1, 0, 0, 0, 1),
    Array(1, 1, 1, 0, 0, 0, 1),
    Array(1, 1, 1, 0, 0, 0, 1),    
    Array(1, 1, 1, 1, 1, 1, 1)
  )
  
  /*
    This algorithm look the first corner by starting from the first postion on the top.
    And it looks the oposite corner of diagonal by starting from the last position on the bottom
  
  */
  
  def time[R](block: => R): R = {  
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
    result
  }
  
  val TO_LOOK = 0
  
  def searchBlackBox(a: Array[Array[Int]]): ((Int, Int), (Int, Int)) = {

    def _searchFirstCorner(): (Int, Int) = {

      val loop = for (i <- 0 until a.length
      ) yield { (i, a(i).indexOf(TO_LOOK)) }

      loop.find(x => x._2 > -1).head
    }

    def _searchLastCorner(): (Int, Int) = {

      val loop = for (i <- a.length - 1 until 0 by -1
      ) yield { (i, a(i).lastIndexOf(TO_LOOK)) }
      
      loop.find(x => x._2 > -1).head
    }

    (_searchFirstCorner(), _searchLastCorner())
  }

  println(time { findBlackBox(image) })
  println(time { findBlackBox(image) })
  println(time { findBlackBox(image) })
  
//Elapsed time: 1514946ns
//((2,3),(4,5))
//Elapsed time: 46787ns > ~ 32 times faster
//((2,3),(4,5))
//Elapsed time: 126242ns > 12 times faster
//((2,3),(4,5))
  
}

Implementation by using finite state machine pattern

// Scala
val image = Array(
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),    
  Array(1, 1, 1, 1, 1, 1, 1)
)

val TO_LOOK = 0

case class Point(x: Int, y: Int)

object Point {
  val Null: Point = Point(-1, -1)
}

trait StateSearch {

  def found: (Point, Point)

  def find(a: Array[Array[Int]], offset: Int = 0): StateSearch = {
    print(offset + "...")
    println(a(offset).mkString(","))
    StateNull()
  }
}

object StateSearch {
  val Null: StateSearch = StateNull()
}

case class StateNull(found: (Point, Point) = (Point.Null, Point.Null)) extends StateSearch

case class SearchingBlackBox(found: (Point, Point) = (Point.Null, Point.Null)) extends StateSearch {
  override def find(a: Array[Array[Int]], offset: Int): StateSearch = {
    a(offset).indexOf(TO_LOOK) match {
        case pos if pos > -1 => BlackBox((Point(offset, pos), Point.Null))
        case _ => SearchingBlackBox(found)
      }
  }
}

case class BlackBox(found: (Point, Point)) extends StateSearch {
  override def find(a: Array[Array[Int]], offset: Int): StateSearch = {
      a(offset).lastIndexOf(TO_LOOK) match {
        case pos if pos > -1 => BlackBox((found._1, Point(offset, pos)))
        case _ => Done(found)
      }
  }
}

case class Done(found: (Point, Point)) extends StateSearch

@tailrec
def findBlackBox(a: Array[Array[Int]], offset: Int = 0,
       state: StateSearch = SearchingBlackBox()): (Point, Point) = {
  state match {
    case SearchingBlackBox(_) => findBlackBox(a, offset + 1, state.find(a, offset))
    case BlackBox(_) => findBlackBox(a, offset + 1, state.find(a, offset))
    case Done(t) => t
  }
}

println(time {
  findBlackBox(image)
})

// Elapsed time: 3107484ns > ~ 2 times slower than above implementation BUT,
// (Point(2,3),Point(4,5))
// Elapsed time: 27899ns > ~111 times faster
// (Point(2,3),Point(4,5))
// Elapsed time: 18939ns > ¡¡¡¡ ~164 times faster !!!!
// (Point(2,3),Point(4,5))

// =============================
// Multiple runnings with different images
// =============================

// Scala
val image = Array(
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 1, 1, 1, 1)
)

val image2 = Array(
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 0, 0, 0, 1, 1, 1),
  Array(1, 0, 0, 0, 1, 1, 1),
  Array(1, 0, 0, 0, 1, 1, 1),
  Array(1, 1, 1, 1, 1, 1, 1)
)

val image3 = Array(
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 0, 0, 0, 1),
  Array(1, 1, 1, 1, 1, 1, 1),
  Array(1, 1, 1, 1, 1, 1, 1)
)

// =====================
// Finite state machine pattern
// =====================

println(time { findBlackBox(image) })
println(time { findBlackBox(image2) })
println(time { findBlackBox(image3) })

// Elapsed time: 2820457ns
// (Point(2,3),Point(4,5))
// Elapsed time: 20251ns > ~ 139 times faster
// (Point(2,1),Point(4,3))
// Elapsed time: 19758ns > ~ 142 times faster
// (Point(1,3),Point(3,5))

// ================
// Loop implementation
// ================

println(time { searchBlackBox(image) })
println(time { searchBlackBox(image2) })
println(time { searchBlackBox(image3) })

// Elapsed time: 1660991ns > ~ 1.69 times faster than first running of above implementation
// ((2,3),(4,5))
// Elapsed time: 207990ns > ~ 8 times faster
// ((2,1),(4,3))
// Elapsed time: 54294ns > ~ 30 times faster
// ((1,3),(3,5))