Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
pouring water scala
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))
}
// convenient way to ask user for input
def askForInput(question: String) = {
println(question)
Console.readLine
}
// parse a line into an array of int
def line_to_int(line: String) = line.split(" ").map(_.toInt)
// is a valid problem ? nb_container, capacities, start, goal
def isProblem(problem: Seq[Array[Int]]) =
problem.length == 4 &&
problem(0)(0) > 0 &&
problem(1).length == problem(0)(0) &&
problem(2).length == problem(0)(0) &&
problem(3).length == problem(0)(0)
def usage() =
println("usage : scala Pouring [filename]. you can use input.txt as an input. Or you can just run 'scala Pouring' and enter custom values")
def main (args: Array[String]) = {
if (args.length == 1) {
val filename = args(0)
val f = new File(filename)
if (!f.exists()) {
println(filename + "doesn't exists")
System.exit(-1)
}
val cur = System.currentTimeMillis
println("Running all problems from " + filename)
Source.fromFile(filename)
.getLines
.map(line_to_int(_))
.grouped(4)
.filter(isProblem(_))
.foreach(x=> { println(); solve(x) })
println("Runned all the problems from " + filename + " in " + (System.currentTimeMillis - cur) + "ms")
System.exit(0)
}
else if(args.length == 0) {
solve(Array("how many containers ?",
"capacities ? (space separated)",
"starting values ?",
"goal ? (zeros will be discarded)")
.map(q => line_to_int(askForInput(q))))
System.exit(0)
}
else {
usage()
System.exit(-1)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.