Scala : add 14-waterpouring to sandbox

2 files changed, 82 insertions, 0 deletions

diff --git a/Scala/sandbox/0-main.scala b/Scala/sandbox/0-main.scala
index 297fab9..0a69d07 100644
--- a/Scala/sandbox/0-main.scala
+++ b/Scala/sandbox/0-main.scala
@@ -16,5 +16,6 @@ object Main  extends App {
     Pack.run
     NQueens.run
     Polynomials.run
+    WaterPouring.run
 
 }
diff --git a/Scala/sandbox/14-waterpouring.scala b/Scala/sandbox/14-waterpouring.scala
new file mode 100644
index 0000000..3420fe5
--- /dev/null
+++ b/Scala/sandbox/14-waterpouring.scala
@@ -0,0 +1,81 @@
+object WaterPouring
+{
+  class Pouring(capacity: Vector[Int]) {
+
+    // States
+
+    type State = Vector[Int]
+    val initialState = capacity map ( x => 0)   // empty glasses
+
+    // Moves
+
+    trait Move {
+      def change(state: State): State
+    }
+    case class Empty(glass: Int) extends Move {
+      def change(state: State): State = state updated (glass, 0)
+    }
+    case class Fill(glass: Int) extends Move {
+      def change(state: State): State = state updated (glass, capacity(glass))
+    }
+    case class Pour(from: Int, to: Int) extends Move {
+      def change(state: State): State = {
+        val amount = state(from) min (capacity(to) - state(to))
+        state updated (from, state(from) - amount) updated (to, state(to) + amount)
+      }
+    }
+
+    val glasses = 0 until capacity.length       // range
+
+    val moves =
+      (for (g <- glasses) yield Empty(g)) ++
+      (for (g <- glasses) yield Fill(g)) ++
+      (for (from <- glasses; to <- glasses if from != to ) yield Pour(from, to))
+
+    // Paths
+
+    class Path(history: List[Move], val endState: State) {
+      // to be simplified…
+      /* def endState: State = trackState(history) */
+      /* private def trackState(xs: List[Move]): State = xs match { */
+      /*   case Nil => initialState */
+      /*   case move :: xs1 => move change trackState(xs1) */
+      /* } */
+      // recomputed over complete history
+      /* def endState: State = (history foldRight initialState) (_ change _) */
+      /* def extend(move: Move) = new Path(move :: history) */ 
+      def extend(move: Move) = new Path(move :: history, move change endState)
+      override def toString() = (history.reverse mkString " ") + "--> " + endState
+      }
+
+    val initialPath = new Path(Nil, initialState)
+
+    def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] =
+      if (paths.isEmpty) Stream.empty
+      else {
+        val more = for {
+          path <- paths
+          next <- moves map path.extend
+          if !(explored contains next.endState)
+        } yield next
+        paths #:: from(more, explored ++ (more map (_.endState)))
+      }
+
+    val pathSets = from(Set(initialPath), Set(initialState))
+
+    def solutions(target: Int): Stream[Path] =
+      for {
+        pathSet <- pathSets
+        path <- pathSet
+        if path.endState contains target
+      } yield path
+  }
+
+  def run = {
+    println("WaterPouring")
+    val problem = new Pouring(Vector(4, 7, 19))
+    problem.moves
+
+    println(problem.solutions(13))
+  }
+}