Break out of loop in scala while iterating on list

Question

I am trying to solve a problem.

Problem : You are given a sequence of N balls in 4 colors: red, green, yellow and blue. The sequence is full of colors if and only if all of the following conditions are true:

There are as many red balls as green balls. There are as many yellow balls as blue balls. Difference between the number of red balls and green balls in every prefix of the sequence is at most 1. Difference between the number of yellow balls and blue balls in every prefix of the sequence is at most 1. Your task is to write a program, which for a given sequence prints True if it is full of colors, otherwise it prints False.

My solution : for each string, i am generating all possible prefixes and suffixes to validate the condition number 3 and 4. But it is taking more time.

instead of generating prefix and validating conditions every time, we can iterate over the string and validate the condition. I want to break out of loop when condition is not met. I am not able to get that in functional style. Can someone help me how to achieve it.

My solution :

object Test {

    def main(args: Array[String]) {

      def isValidSequence(str: String) = {
        def isValidCondition(ch1:Char, ch2:Char, m:Map[Char, Int]):Boolean = m.getOrElse(ch1, 0) - m.getOrElse(ch2, 0) > 1
        def groupByChars(s:String) = s.groupBy(ch => ch).map(x => (x._1, x._2.length))
        def isValidPrefix(s:String):Boolean = (1 to s.length).exists(x => isValidCondition('R', 'G', groupByChars(s.take(x))))

        val x = groupByChars(str)
        lazy val cond1 = x.get('R') == x.get('G')
        lazy val cond2 = x.get('B') == x.get('Y')
        lazy val cond3 = isValidPrefix(str)
        lazy val cond4 = isValidPrefix(str.reverse)

        cond1 && cond2 && !cond3 && !cond4
      }
      def printBoolValue(b:Boolean) = if(b) println("True") else println("False")

      val in = io.Source.stdin.getLines()
      val inSize = in.take(1).next().toInt
      val strs = in.take(inSize)
      strs.map(isValidSequence(_)).foreach(printBoolValue)
    }
}

Answer 1

Here is a solution using streams if you need.

code :-

object RGYB extends App {

val validPattern = List(
        "RG","RYBG","RYGB","RBGY",
        "GR","GYBR","GYRB","GBRY",
        "YB","YRGB","YRBG","YGRB",
        "BY","BRGY","BRYG","BGYR"
        )

        val pattern ="RGRG"
        pattern.sliding(4).foreach { x1 =>
        val count = validPattern.filter { p1 => {
            x1.equalsIgnoreCase(p1)
        } 
        }.size
        if(count<1)
        {
            x1.sliding(2).foreach {
                x2=>
                val counter  = validPattern.filter { p2 => {
                    x2.equalsIgnoreCase(p2)
                } 
                }.size
                if(counter<1)
                {
                    println("false !! not valid due to "+x2);
                    System.exit(0)
                }
            }
            println("false !! not valid due to "+x1);
            System.exit(0)
        }
}

println("True !!"+pattern+" Is a valid string pattern")
}

Answer 2

As another answer, here's a more straightforward solution, that does short-circuit the differences check.

val valid = List("RGYBRGYB")      
val invalid = List("RGYBR", "RGYBY", "RGYBY", "RGYYB")

def checkBalls(s:String) = {
def differences(s:String, a:Char, b:Char) = {
  def differenceHelp(s:String, a:Char, b:Char, current:Int):Boolean = {
      if (current < -1 || current > 1) false
      else if (s.length == 0) true
      else differenceHelp(s.tail, a, b,
           if (s.head == a) current + 1 else if (s.head == b) current - 1 else current)
    }

  differenceHelp(s, a, b, 0)
}

lazy val cond1 = s.count('R'==) == s.count('G'==)
lazy val cond2 = s.count('Y'==) == s.count('B'==)
lazy val cond3 = differences(s, 'R', 'G')
lazy val cond4 = differences(s, 'Y', 'B')
cond1 && cond2 && cond3 && cond4
} 
valid.forall(checkBalls(_))                       //> res0: Boolean = true
invalid.forall(!checkBalls(_))                    //> res1: Boolean = true

EDIT: as an optimisation, we can do cond1 as part of cond3 (and cond2 as part of cond4). There are equal numbers of each if and only if the count is 0 at the end of the string. We can check that in differences and return true only if that's the case. So that gives

def checkBalls(s:String) = {
def differences(s:String, a:Char, b:Char) = {
  def differenceHelp(s:String, a:Char, b:Char, current:Int):Boolean = {
      if (current < -1 || current > 1) false
      else if (s.length == 0) (count == 0) // <- this line changed
      else differenceHelp(s.tail, a, b,
           if (s.head == a) current + 1 else if (s.head == b) current - 1 else current)
    }

  differenceHelp(s, a, b, 0)
}

lazy val cond3 = differences(s, 'R', 'G')
lazy val cond4 = differences(s, 'Y', 'B')
cond3 && cond4
} 

which passes the tests just like the previous version. It could be made slightly faster by doing the R/G and Y/B checks in one call to differences, but that's looking a bit overspecialised.

Answer 3

So, the trick is to check the longest prefix first. If that fails, we're done. Otherwise, we take the next longest prefix and recurse. If we get to the empty string, it passed for all prefixes, and therefore it's valid.

def isValidPrefix(s: String): Boolean = 
if (s.length == 0)
  true
else if (!isValidCondition('R', 'G', groupByChars(s)))
  false
else isValidPrefix(s.init)