Water Pouring Problem

Coursera의 Functional Programming in Scala에서 설명한
the Water Pouring Problem의 코드 설명

/**
 * the Water Pouring Problem
 *   정해진 용량의 컵에 물을 따라서 원하는 용량의 물을 가지고 있는 glass 만들기.
 * 예를 들어 4와 7의 용량을 가질 수 있는 두개의 컵을 가지고
 * 6의 용량을 가지도록 하는 방법은?
 */
class Pouring(capacity: Vector[Int]) {
  // States
  type State = Vector[Int]
  val initialState = capacity map (x => 0)
  // Moves
  //   State를 변경한다.
  trait Move {
    def change(state: State): State
  }
  // 컵을 비운다.
  case class Empty(glass: Int) extends Move {
    def change(state: State) = state updated (glass, 0)
  }
  // 컵을 채운다.
  case class Fill(glass: Int) extends Move {
    def change(state: State) = state updated (glass, capacity(glass))
  }
  // 다른 컵에 따른다.
  case class Pour(from: Int, to: Int) extends Move {
    def change(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
  // 옮겨갈 수 있는 상태들
  // 예를 들어 아래와 같이 할 경우
  //   val problem = new Pouring(Vector(4, 7))
  //   problem.moves
  // 결과는 아래와 같이 된다.
  //   Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,1), Pour(1,0))
  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: sequences of moves
  // history: 최신 move가 앞에 오는 list.
  class Path(history: List[Move], val endState: State) {
    def extend(move: Move) = new Path(move :: history, move change endState)
    // move를 순서대로 보여준 후 --> state 변경에 따른 마지막 state 출력
    override def toString = (history.reverse mkString " ") + " --> " + endState
  }
  val initialPath = new Path(Nil, initialState)
  // explored를 통해 이미 방문한 state는 제거한다.
  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))
  // 예를들어
  //   val problem = new Pouring(Vector(4, 7))
  //   problem.solution(6)
  // 결과는
  //   Fill(1) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) --> Vector(4, 6)
  // state의 변화를 적어보면
  //   (0, 7) -> (4, 3) -> (0, 3) -> (3, 0) -> (3, 7) -> (4, 6)
  def solution(target: Int): Stream[Path] =
    for {
      pathSet <- pathSets
      path <- pathSet
      if path.endState contains target
    } yield path
}