微風夕語

/**
 *  用 Scala 解很難死第三集裡的倒水問題！
 *
 *  程式碼是從 Functional Programming Principles in Scala 出來的，加上一些註解
 *  方便理解，免得自己忘記。XD
 *
 *  原始問題：
 *
 *    現在有一個５加倫的水桶和３加倫的水桶，一個水池可以讓你填滿水桶或倒空水桶，
 *    要如何才能量出４加倫的水來阻止炸彈？
 *
 *  擴充版：
 *
 *    現在有Ｎ個水桶，一個水池可以讓你填滿或倒空水桶，你如何透過一連串的行動在
 *    某個水桶中裝剛剛好的水量Ｘ？
 *
 *  程式演算法核心：
 *
 *    暴力法 BFS Search，假設今天有５加倫和３加倫的水桶，我們有以下六個動作可以選擇：
 *
 *      - 清空５加倫的水桶
 *      - 清空３加倫的水桶
 *      - 裝滿５加倫的水桶
 *      - 裝滿３加倫的水桶
 *      - 把５加倫的水桶裡的水倒到３加倫的水桶
 *      - 把３加倫的水桶裡的水倒到５加倫的水桶
 *
 *    列出第 N 個動作的時候的所有可能解，例如：
 *
 *      當只能做一動的時候，總共有六種狀態 (6 * 1)
 *      當只能做兩動的時候，總共有三十六種狀態 (6 * 6)
 *      當只能做三動的時候，總共有兩百一十六種狀態 (6 * 6 * 6)
 *
 *    每次增加一動，直到我們在這一動的所有狀態中找到符合我們要求的解為止
 *
 *  資料結構：
 *
 *    幾個水桶：用 Int 表示，0 代表第一個水桶，1 代表第二個水桶
 *    水桶的容量：Vector[Int]，Vector(0) 代表第一個水桶的最大容量
 *    狀態：Vector[Int]，Vector(0) 代表第一個水桶目前的水量
 *    動作路徑：List[Move]，最後一個動作在 List 的第一個元素（Stack）
 *
 *  @param  capacity  各水桶的最大容量，Vector 長度就是有幾個水桶
 *
 */
class Pouring(capacity: Vector[Int]) {

  // States
  type State = Vector[Int]                // 狀態用 Vector[Int] 表示

  val initialState = capacity.map(x => 0) // 初始狀態，每個水桶都沒有水
  val glasses = 0 until capacity.length   // 所有水桶的編號（0 ~ N-1）

  /**
   *  可以做的動作的父類別
   *
   *  有以下三個可能性：
   *
   *    - 清空某個水桶
   *    - 裝滿某個水桶
   *    - 把某個水桶裡的水倒到另一個水桶
   */
  trait Move {
    /**
     *  執行這個動作後，水桶裡的新水量
     *
     *  @param  state   還沒執行動作前各水桶的水量
     *  @return         執行動作後各水桶的水量
     */
    def change(state: State): State
  }

  /**
   *  清空某個水桶
   *
   *  @param  glass   要清空哪個水桶
   */
  case class Empty(glass: Int) extends Move {

    // 被清空的水桶的新容量是空的
    def change(state: State) = state.updated(glass, 0)
  }

  /**
   *  裝滿某個水桶
   *
   *  @param  glass   要裝滿哪個水桶
   */
  case class Fill(glass: Int) extends Move {

    // 被裝滿的水桶的新容量是該水桶的最大容量
    def change(state: State) = state.updated(glass, capacity(glass))
  }

  /**
   *  把某個水桶的水倒到另一個水桶
   *
   *  @param  from  從哪個水桶
   *  @param  to    倒到哪個水桶
   */
  case class Pour(from: Int, to: Int) extends Move {
    def change(state: State) = {

      // 有兩種可能：
      //
      //  1. 來源的水桶裡的水可以全部倒到另一個水桶（水不夠倒滿另一個水桶）
      //  2. 目的地的水桶被倒滿（目的地不能容納更多水）
      //
      //  選以上兩個可能性當中最小的
      val amount = state(from) min (capacity(to) - state(to))

      // 新的狀態當然是來源水桶扣掉倒的水量，目的地水桶加上倒的水量
      state.updated(from, state(from) - amount).
            updated(to, state(to) + amount)
    }
  }

  /**
   *  在目前的水桶數量下所有可能的動作
   */
  val moves = {
    (for (g <- glasses) yield Empty(g)) ++  // 清空第 0 ~ N 個水桶
    (for (g <- glasses) yield Fill(g)) ++   // 裝滿第 0 ~ N 個水桶
    (for {
      from <- glasses;                      // 從某個水桶
      to <- glasses if from != to           // 倒到另一個水桶，兩個水桶的編號不能一樣
    } yield Pour(from, to))
  }

  /**
   *  代表動作的順序
   *
   *  @param  目前的動作順序，第一個元素為最後一動，第二個元素為倒數第二動，依此類推
   *  @param  執行完這個順序的動作後，水桶的水量狀態
   */
  class Path(history: List[Move], val endState: State) {

    /**
     *  如果執行下一動會發出什麼事
     *
     *  @param  move  下一動
     *  @return       執行完後的動作順序以及狀態
     */
    def extend(move: Move) = new Path(move :: history, move.change(endState))

    override def toString = history.reverse.mkString(" ") + " -> " + endState
  }

  /**
   *  一開始的動作順序－－什麼都沒動，水桶是空的
   */
  val initialPath = new Path(Nil, initialState)

  /**
   *  BFS search 重點
   *
   *    from(0) = 一開始的水桶的狀態（全部是空的）
   *    from(1) = 執行一動時的 6 種可能行動
   *    from(2) = 執行二動時的 36 種可能行動
   *    from(3) = 執行三動時的 216 種可能行動
   *
   *  由於是 Lazy Stream，只有當真的存取到 from(1) 的時候才會開始
   *  從 from(0) 計算 from(1) 的 6 種可能性；只有當真的存取到 from(2)
   *  的時候才會從原本 from(1) 的結果計算 from(2) 的 36 種可能性，
   *  依此類推。
   *
   *  @param  paths     目前所有的可能行動路徑
   *  @param  explored  已經到達過的水桶狀態，避免一直 loop 到同樣的水桶狀態
   */

  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))

    }
  }

  /**
   *  BFS Search 的開頭：
   *
   *    - 行動：什麼都沒做
   *    - 狀態：水桶全是空的
   */
  val pathSets = from(Set(initialPath), Set(initialState))

  /**
   *  找出某個水量的解法
   *
   *  @param  target  要幾加侖的水
   *  @return         所有可能的解法
   */
  def solution(target: Int): Stream[Path] = {

    for {
      pathSet <- pathSets   // 檢視第０動～已經走遍所有狀態的所有可能動作順序
      path <- pathSet       // 檢查第Ｎ動裡的所有路徑
      if (path.endState.contains(target)) // 如果這個路徑有目標水量
    } yield path  // 加到可能解裡面

  }

}