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)
    }
}

Just an aside, you probably want s.inits to return all your prefixes in isValidPrefix. — The Archetypal Paul
– The Archetypal Paul, Commented Jul 2, 2015 at 11:10
If you use .par you're doing several iterations at once anyway, so it's really not clear what "break out of the loop" means. — The Archetypal Paul
– The Archetypal Paul, Commented Jul 2, 2015 at 11:11
to make it faster, i used .par. Not intended to use. will remove it — Rajeev
– Rajeev, Commented Jul 2, 2015 at 11:12
There are other issues with your code. For condition 4, you seem to be checking suffixes, rather than prefixes with Yellow/Blue. For isValidCondition, you're checking the # of first colour isn't more than 1 more than the second colour, but the condition is that the difference is at most one (in other words, the check needs to be symmetrical). The repeated groupByChars is a bit overkill, just s.count('R'==) would do. And so on. — The Archetypal Paul
– The Archetypal Paul, Commented Jul 2, 2015 at 11:43

The Archetypal Paul · Accepted Answer · 2015-07-02 15:17:06Z

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.

Puneeth Reddy V · Accepted Answer · 2015-07-02 20:35:26Z

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")
}

The Archetypal Paul · Accepted Answer · 2015-07-02 11:17:38Z

0

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)

answered Jul 2, 2015 at 11:17

The Archetypal Paul

41.9k20 gold badges107 silver badges136 bronze badges

1 Comment

The Archetypal Paul Over a year ago

Although a quicker way of doing it is to iterate through the string (just once) counting 1 for every Red, -1 for every Green, and ensuring the absolute value of the total is never more than 1.

Collectives™ on Stack Overflow

Break out of loop in scala while iterating on list

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related