Case Study: the Water Pouring Problem

pouring.scala

/**
 * Case Study: the Water Pouring Problem
 * https://www.coursera.org/learn/progfun2/lecture/EkEqR/lecture-2-5-case-study-the-water-pouring-problem
 *
 * @param capacity defines how many glasses the problem is and their capacity
 *                 index = glass Id
 *                 value = capacity of the glass in ml
 */
class Pouring(capacity: Vector[Int]) {

  /**
   * State models the current state of the glasses
   * index = glass Id
   * value = amount of liquid in the glass
   */
  type State = Vector[Int]
  val initialState: State = capacity.map(_ => 0)

  /**
   * Move models the turn that leads to state change
   * The are three possible moves that could changes
   * the state of corresponding glass / glasses:
   *    - Empty - just pour out (waste) the contents of the glass
   *    - Fill - fill the glass full of liquid
   *    - Pour - move the liquid from one glass to another in amount to make target glass full
   */
  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 moves: List[Move] = (
      (for (g <- capacity.indices) yield Empty(g)) ++
      (for (g <- capacity.indices) yield Fill(g)) ++
      (for (from <- capacity.indices;
            to <- capacity.indices if from != to) yield Pour(from, to))
    ).toList

  /**
   * Path models the track of moves that leads to endState
   * @param history reverse history of Moves
   *                The last Move is first in the List
   */
  class Path(history: List[Move], val endState: State) {
    // first move change initialState then this applies to second move etcetera
    // def endState: State = history.foldRight(initialState)(_.change(_))
    def extend(move: Move) = new Path(move :: history, move.change(endState))

    override def toString: String = s"[${history.reverse.mkString(" ")}]-->$endState"
  }

  val initialPath = new Path(Nil, initialState)

  /**
   * Finds all possible paths started from initial set
   * @param paths initial set of paths to start the exploration
   * @param explored set of already explored endStates to shorten the search
   * @return Stream with sets of path
   */
  def from(paths: Set[Path], explored: Set[State]): LazyList[Set[Path]] =
    if (paths.isEmpty) LazyList.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: LazyList[Set[Path]] = from(Set(initialPath), Set(initialState))

  /**
   * Finds the solution of the water pouring problem
   * @param target amount of liquid that should be collected in one of the glasses
   * @return Stream with paths of possible solutions
   */
  def solutions(target: Int): LazyList[Path] =
    for {
      pathSet <- pathSets
      path <- pathSet
      if path.endState.contains(target)
    } yield path
}

test.sc

object test {

  val problem = new Pouring(Vector(4, 9))

  problem.moves

  problem.pathSets.take(3).toList

  problem.solutions(6).take(1).toList

}