Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
    
new Container(capacity, filled + toAdd) -> no new needed for case classes. –  Landei Mar 22 '12 at 12:23
    
Trying to learn from the code that's presented here. What's the purpose of the following line val state = State(problem(1).zip(problem(2)).map(x => Container(x._1, x._2))). I understand the zip but I am confused about the map and how it applies over the State class? –  sc_ray May 16 '12 at 3:23
    
nevermind..I read the statement wrong. The zip and the corresponding map is passed as an argument in the State. I missed the params enclosing the operation. –  sc_ray May 16 '12 at 4:23
add comment

1 Answer

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.

share|improve this answer
    
OK. I looked up for Option and I think this is actually what I wanted. I've put : case class State(containers : ArraySeq[Container], parent: Option[State] = None) { def ancesters() : List[State] = this.parent match { case Some(parent) => parent :: parent.ancesters case None => List[State]() } Now my first state is created without "parent" parameter and when I create a new State when pouring: State(new_containers, Option(this)) I think this is good right ? Thank you very much for the advice :) –  Patrick Browne Mar 22 '12 at 5:33
    
I had also to redefine hashCode and equals in order not take account of member "parent". –  Patrick Browne Mar 22 '12 at 6:18
    
@PatrickBrowne Instead of modifying hashCode and equals, you could have parent on a second parameter list. IIRC, only stuff in the first parameter list is taken into account on the auto-generated methods. –  Daniel C. Sobral Mar 22 '12 at 13:13
    
I don't see how I can put parent in a second parameter list. As I understood, in Scala when you want to add another constructor, it has to call the first constructor and this is why you have to put the most generic constructor first. In my case, the most generic constructor is the one with parent so I can't put it as the second one. Am I wrong ? By the way, I used ArraySeq because one ArraySeq is considered equal with another if they have the same content. This is not true for Array. –  Patrick Browne Mar 24 '12 at 14:28
    
@PatrickBrowne case class State(containers : ArraySeq[Container])(parent: Option[State] = None) –  Daniel C. Sobral Mar 24 '12 at 14:39
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.