object WaterPouringProblem {


  def main(args: Array[String]) = println (new Pouring(Vector(2,9,3)).solution(8))
  class Pouring(capac: Vector[Int]) {
    type State = Vector[Int]
    val initialState = capac map (_ => 0)
    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, capac(glass))
    }
    case class Pour(from: Int, to: Int) extends Move {
      def change(state: State): State = {
        val amount = state(from) min (capac(to) - state(to))
        state updated (from, state(from) - amount) updated (to, state(to) + amount)
      }
    }

    val glasses = 0 until capac.length


    val moves =
      (for (g <- glasses) yield Empty(g)) ++
        (for (g <- glasses) yield Fill(g)) ++
        (for (g1 <- glasses; g2 <- glasses if (g2 != g1)) yield Pour(g1, g2));

    class Path(history: List[Move], val finalState: State) {
      def extend(move: Move) = new Path(move :: history, move.change(finalState))
      override def toString =
        (history.reverse mkString " -> ") + " => " + finalState
    }
    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.finalState)
        } yield next
        paths #:: from(more, explored ++ more.map(_.finalState))
      }
    }

    val pathSets: Stream[Set[Path]] = from(Set(initialPath), Set(initialState));

    def solution(target: Int): Stream[Path] = {
      for {
        pathSet <- pathSets
        path <- pathSet
        if (path.finalState contains target)
      } yield path
    }
  }
}