# Pouring water problem

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

We have $k$ containers, where $3 ≤ k ≤ 10$. Container $i$ has a certain integer capacity $c_i > 0$ (of liters of water). Initially, container $i$ contains an integer amount $a_i ≥ 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 $a_i = 0$ or $a_j = c_j$).

Is it 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$, $c_1 = 10$, $c_2 = 7$, $c_3 = 4$, $a_1 = 0$, $a_2 = 7$, and $a_3 = 4$. The question is: Is it possible to reach $a_3 = 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.

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
assert (filled + toAdd <= capacity, { println("Too much water in container")})
}

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 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.
• This could probably be done using iterators, but I don't know much about that yet.
-
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

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.

-
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

The algorithm is more important than code style. I haven't given it much thought, but it seems that this might be solvable with dynamical programming, or some more efficient method than brute force search. Also, the brute force search algorithm will run for ever if there is no solution. I implemented below a slightly modified version of your algorithm, where I keep track of visited states. It increases performance and it does terminate.

As mentioned in another answer, it's better to use List or Stream rather than arrays. Your loops over array indices are very un-functional.

You did use immutable data structures, except ArraySeq.

Instead of your main while-loop, I am using a recursive function. It's always possible to get rid of loops (for/while) using recursive functions. It's not wrong at all to use a while-loop; it's just more "functional" to use a recursive function. Even more "functional" than using recursive functions is to use the collection operations such as list.map, list.foreach, list.foldLeft, list.filter, etc.

Here is my solution (using the same brute force search algorithm, but keeping track of visited states):

object PourSolution extends App {

case class Container(id: String, capacity: Int)
type State = Map[Container, Int]
type Move = (Container, Container) // (from, to)

// Only moves where source is non-empty and destination is non-full.
def possibleMoves(state: State): List[Move] = {
val containers = state.keys.toList
for {
s <- containers
t <- containers
if (s != t && state(s) != 0 && state(t) != t.capacity)
} yield (s, t)
}

def applyMove(state: State, move: Move): State = {
val from = move._1
val to = move._2
val remainingCapacity = to.capacity - state(to)
val transfer = math.min(state(from), remainingCapacity)
if (transfer == 0) state
else state ++ List(from -> (state(from) - transfer), to -> (state(to) + transfer))
}

// Warning: the moves in the returned list are in reversed order.
def solve(initState: State, targetState: State): Option[List[Move]] = {
require(!doesMatch(initState))
require(targetState.nonEmpty)

lazy val targetStateAsSet = targetState.toSet
def doesMatch(state: State): Boolean = (state.toSet & targetStateAsSet) == targetStateAsSet

@tailrec
def loop(states: List[(State, List[Move])], statesNextDepth: List[(State, List[Move])], visitedStates: Set[State]): Option[List[Move]] =
(states, statesNextDepth) match {
case (Nil, Nil) => None
case (Nil, statesNextDepth) => loop(statesNextDepth, Nil, visitedStates)
case ((state, moves) :: tail, statesNextDepth) =>
val nextMoves = possibleMoves(state)
val nextStates: List[(State, List[Move])] = nextMoves.map(move => (applyMove(state, move), move :: moves))
val newNextStates = nextStates.filter(p => !visitedStates.contains(p._1))
val exactSolution = newNextStates.find { case ((s, _)) => doesMatch(s) }
if (exactSolution.isDefined)
exactSolution.map(_._2)
else
loop(tail, newNextStates ::: statesNextDepth, visitedStates ++ newNextStates.map(_._1))
}
loop(List((initState, Nil)), Nil, Set(initState))
}

val c0 = Container("c0", 10)
val c1 = Container("c1", 7)
val c2 = Container("c2", 4)
val initialState = Map(c0 -> 0, c1 -> 7, c2 -> 4)
val targetState = Map(c2 -> 2)

val solution = solve(initialState, targetState)

solution match {
case None => println("No solution")
case Some(reversedMoves) =>
val moves = reversedMoves.reverse
moves.foreach(println)
val movesWithState = moves.scanLeft(initialState)(applyMove(_, _))
movesWithState.foreach(println)
}
}


Note that I use one list of the states at the current depth and another list for the states at the next depth. I did this because otherwise one would need a FIFO queue (all the states of the current depth are at the head of the queue), but I'm not sure that there is an efficient immutable implementation of such a queue.

-