CODEWITHSUNDEEP
scala
kromastorm
kromastorm

Reputation: 164

Better way to search character in vector of vectors in scala

I have a requirement where I have to search a character in vector of vectors. I have written a method which is very crude. What is a better way to search an element in vector of vectors.

Here is my code: 

def search( xs: Vector[Vector[Char]], char: Char, rowIndex: Int): Pos = xs.headOption match {
  case None =>  Pos(-1, -1)
  case Some(row) => {
    val tuple = searchHelper(row, char, 0)
    if(tuple._1)
      Pos(rowIndex, tuple._2)
    else
      search(xs.tail, char, rowIndex +1)
  }
}

def searchHelper(xs: Vector[Char], char: Char, colIndex: Int): (Boolean, Int) = xs.headOption match {
  case None => (false, colIndex)
  case Some(col) =>
    if(col == char)
      (true, colIndex)
    else
      searchHelper(xs.tail, char, colIndex +1)
}

search(vector, c, 0)

Here is the input:

val input =
  """ooo-------
    |oSoooo----
    |ooooooooo-
    |-ooooooooo
    |-----ooToo
    |------ooo-""".stripMargin

val vector =
  Vector(input.split("\n").map(str => Vector(str: _*)): _*)

val c = 'S'

Upvotes: 0

Views: 624

Answers (3)

Arnaud
Arnaud

Reputation: 417

Simplest way of doing it :

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = 
    val x = levelVector.indexWhere(_.contains(c))
    val y = levelVector(x).indexWhere(_ == c)
    Pos(x,y)

Indeed you have to assume there is only one correct answer. Main idea :

  1. First search for the row that have the character c
  2. Then find the column in this row that has this character c

Upvotes: 0

Dima
Dima

Reputation: 40500

Something like this, perhaps?

xs
 .iterator
 .zipWithIndex
 .map { case (chars, idx) => (idx, chars.indexOf(c)) }
 .collectFirst {
    case (outer, inner) if(inner >= 0) => Pos(outer, inner)
 }.getOrElse(Pos(-1, 1))

To address a concern from the comments: this is not iterating through the entire list multiple times (not even once completely, as long as it finds a match earlier). Scala iterators are wonderful that way: you can write a chain of calls, that conceptually looks like a bunch of sequential transformations to the entire list, but is really executed lazily, element by element: the first element is is extracted from list, converted to a tuple (chars, 0), fed to the map, then the result of that is sent to collectFirst, if the condition matches there, it stops and returns right away, otherwise, next element is taken from list, made into a tuple (chars, 1), fed to the .map, etc ...

Upvotes: 3

thwiegan
thwiegan

Reputation: 2173

If, with better, you mean more concise, you could try leveraging the methods on Scalas collections:

def search( xs: Vector[Vector[Char]], c: Char ): (Int, Int) = {
    var innerIndex = -1
    val outerIndex = xs.indexWhere { inner =>
        innerIndex = inner.indexOf(c)
        innerIndex > -1
    }
    (outerIndex, innerIndex)
}

This assumes that you only need the first occurence of that character.

indexWhere terminates as soon as the innerIndex is larger than -1.

Maybe another possibility, which goes more in your recursive direction (and without a mutable var), but also with minimal iterations:

@tailrec
def search(xs: Vector[Vector[Char]], c: Char, n: Int = 0): (Int, Int) = {
  if (n > xs.size - 1) (-1, -1)
  else
    xs(n).indexOf(c) match {
      case -1 => search(xs, c, n + 1)
      case i => (n, i)
    }
}

Upvotes: 2

Related Questions