Minimal Substring Satisfying a condition in scala

Question

I have a string, lets say val mystr = "abcde", and I want to find the minimal substring of mystr which satisfies a given condition. I have to send a string to an external system, so the only way to do this is to iterate through the length of the string and make requests to the external system, and break when the response from the external system returns true

eg.

callExtSystemWith("a") //Returns false
callExtSystemWith("ab") //Returns false
callExtSystemWith("abc") //Returns true

Then my method should return "abc". I read that breaks are not the scala way, so was wondering what is the scala way of achieving this?

Right now I have:

      for {end <- 1 to mystr.length)}{
        callExtSystemWith(mystr.substring(0,end))
        // I Want to break when this is true.
      }

Help much appreciated

dcastro · Answer 1 · 2015-09-03T15:10:20.033

You can use ~~inits.toStream.reverse.drop(1)~~ (1 to s.length).map(s.take).toStream to create a lazy stream with a, ab, abc, abcd.

Then filter those strings, so that only the ones for which callExtSystemWith returns true are left.

Then get the first string for which callExtSystemWith returns true. Because this is a lazy stream, no unecessary requests will be made to the server once the first match is found.

val s  = "abcdefgh"
val strs = (1 to s.length).map(s.take).toStream

strs.filter(callExtSystemWith).headOption match {
  case Some(s) => "found"
  case _ => "not found"
}

You can also use find instead of filter + headOption

score 1 · Answer 2 · answered Sep 03 '15 at 14:52

Quite often break can be replaced with find on some sequence

So here is another short solution for this problem:

def findSuitablePrefix(mystr: String): Option[String] = 
  (1 to mystr.length).view.map(mystr.substring(0, _)).find(callExtSystemWith)

.view makes the evaluation lazy to avoid creating extra substrings. .map transforms the sequence of indexes into a sequence of substrings. And .find "breaks" after the first element for which callExtSystemWith returns true is found.

score 0 · Answer 3 · answered Sep 03 '15 at 14:25

In Scala there are no normal breaks but there are other solutions. The one I like better is to create a function and force a return (instead of a normal break). Something like:

def callAndBreak(mystr:String) : Int = {

    for (end <- 1 to mystr.length) {
        if ( callExtSystemWith(mystr.substring(0,end)) ) return end
    }
    end
}

Here I return end but you can return anything

score 0 · Answer 4 · answered Sep 03 '15 at 14:32

If you want to avoid using return or breaks, you could also use foldLeft:

val finalResult = (1 to mystr.length).foldLeft(false) { (result, end) => 
    if(!result) callExtSystemWith(mystr.substring(0, end)) else result
}

However, it is a bit hard to read, and will walk the entire length of the string.

Simple recursion might be a better way:

def go(s: String, end: Int): Boolean = {
  if(end >= s.length) false
  else {
    callExtSystemWith(s.substring(0, end)) || go(s, end + 1)
  }
}

go(mystr, 1)

Minimal Substring Satisfying a condition in scala

4 Answers4