Pouring Water = My first scala code

Question

This is my first time in CodeReview, I'd hope like something like that existed and voila, a fellow StackExchange site has already been done.

I just began to study Scala (coming from Python I had quite a few problems with types :) ) and I want to know if my first code to solve a real problem is nicely done or if there is some points that need to be redone.

The problem I had to solve is for an homework but my code is already working, I just want to know if it be more Scalish:

Problem description

The problem is the following: We have k containers, where 3 ≤ k ≤ 10. Container i has a certain integer capacity ci > 0 (of liters of water). Initially, container i contains an integer amount ai ≥ 0 of water. We are allowed to perform only one kind of operations: Take one container i, and pour its contents into a different container j. Pouring stops when either i becomes empty, or j becomes full (so after the operation either ai = 0 or aj = cj). The question is if it is possible to achieve a certain target configuration, and, if so, how.

For instance, let's assume we have three containers with capacities 10l, 7l, and 4l. Initially, the 7l and 4l container are full, while the 10l container is empty. The question is if we can achieve that the 4l container contains exactly 2l of water.

With our notation, we have k = 3, c1 = 10, c2 = 7, c3 = 4, a1 = 0, a2 = 7, and a3 = 4. The question is: Is it possible to reach a3 = 2?

The answer is yes, and here is a possible sequence of moves (displayed in reverse order):

2 7 2

2 5 4

6 5 0

6 1 4

10 1 0

4 7 0

0 7 4

I solved the problem using BFS on a graph I'm building at every step.

Code :

import collection.mutable.HashSet
import collection.mutable.Queue
import collection.mutable.ArraySeq
import scala.io.Source
import java.io.File

case class Container(capacity: Int, filled: Int) {

    // overload + and - methods
    def +(toAdd: Int) = {
        assert (filled + toAdd <= capacity, { println("Too much water in container")})
        new Container(capacity, filled + toAdd)
    }

    def -(toSub: Int) = { 
        assert (filled - toSub >= 0, { println("Not enough water in container")})
        new Container(capacity, filled - toSub)
    }

    // how much can we pour into an other container ?
    def howMuchToPour(other: Container) = 
        math.min(filled, other.capacity - other.filled)

    // just print the filling level when printing a Container
    override def toString(): String = filled.toString;
}

case class State(containers : ArraySeq[Container]) {
    var parent:State = _

    // returns all the ancesters of a State
    def ancesters() : List[State] = 
        if (Option(parent) != None) parent :: parent.ancesters
        else                        List[State]()

    // returns a new State with i-th container poured into j-th container
    // no check if it's possible or not
    def pour(i: Int, j: Int, q: Int) = {
        val new_containers = containers.slice(0, containers.length) // make a copy
        new_containers(i) = containers(i) - q
        new_containers(j) = containers(j) + q
        val ns = State(new_containers)
        ns.parent = this
        ns
    }

    override def toString(): String = containers map{_ toString} mkString "\t"

    def next_states() = 
        for { i <- (0 until containers.length);
              j <- (0 until containers.length)
              q = containers(i) howMuchToPour containers(j)
              if (i !=j) && q > 0 }
            yield pour(i, j, q)
}

object Pouring {
    def _bfs(start: State, condition: (State) => Boolean) : List[State]  = {
        val q = Queue[State]()
        val seen =  HashSet[State]()
        q    += start    
        seen += start

        while (q.length > 0) {
            val s = q.dequeue()

            if (condition(s)) 
                return s :: s.ancesters

            s.next_states().foreach(ns => {
                if (!seen.contains(ns)) {
                    q    += ns
                    seen += ns
                }
            })
        }
        List[State]()
    }

    def solve(problem:Seq[Array[Int]]) {        
        val state = State(problem(1).zip(problem(2)).map(x => Container(x._1, x._2)))

        val cond_funcs = for { (filled, index) <- problem(3).zipWithIndex
                                                            .filter(x => x._1 != 0) } 
                            yield (x:State) => x.containers(index).filled == filled

        _bfs(state, (x) => cond_funcs.forall(_(x)))
            .reverse
            .foreach(s => println(s))
    }

    def main (args: Array[String]) = {
        solve(Array(Array(3), Array(10, 7, 4), Array(0, 7, 4), Array(0, 0, 2)))
    }
}

The points that I think can be improved but don't know how :

• The parent member of State which is a var, would it be possible to instantiate an object State with a parent member ? I tried but I couldn't since the first State has no parent.
• Maybe using Iterators but I don't know much about that yet, I need to study more.

Thank to everyone who can tell me how to improve my Scala skills :)

Answer 1

It seems pretty reasonable, actually. I'm confused by the ArraySeq. Also, I'd rewrite this:

   if (Option(parent) != None) parent :: parent.ancesters
    else                        List[State]()

As

   Option(parent).map(parent => parent :: parent.ancesters).getOrElse(List[State]())

That is, if used parent as you did. I'd make it an Option instead, and initialize it at creation.

I'm not sure Iterator would help you here, but Stream might. I just don't think it is a particular good fit for BFS, but it might just be ignorance on my part.