Scala筆記 28 - 用Streams解決Search Problem，以倒水問題為例

Search Problem

所謂search problem就是在一個問題的可能解決地圖中，找到一條解決路徑，最好也是optimal的解決路徑，Scala課程中以倒水問題為例，而功課則要學生找出Bloxorz這個遊戲的解決路徑。

倒水問題如下：
有n個已知容量的空杯子，試求最少步驟能裝出x容量的水？我們能對杯子做的動作有:
1. 倒滿
2. 清空
3. 從a杯倒到b杯

Modeling States

這個跟我之前上Berkely AI課程的小精靈問題一樣，我們先把n個空杯子用一個Vector[Int]來代表，任何Vector[Int]可能的值就是一個state，並且先列出所有可以走的actions組合，因為待會就要在search space中利用這些actions來建立search path:

class Pouring(capacity: Vector[Int]) { //各種容量的杯子
  //states  
  type State = Vector[Int]
  val initalState = capacity map (_ => 0) //一開始所有杯子是空的
  
  //move types  
  trait Move
  case class Empty(glass: Int) extends Move
  case class Fill(glass: Int) extends Move
  case class Pour(from: Int, to: Int) extends Move

  //all indices  
  val glasses = 0 until capacity.length

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

}

Modeling Moves

我們會從initial state開始長出三個可能的move path，分別是Empty, Fill, Pour，所以我們還需要知道從某個state經過一個move之後，會變成哪一個state? 我們在trait Move中加入一個change method：(這邊的邏輯比較不直覺，我會寫成State有一個change(move:Move)的方法，而不是在Move class中寫一個change(state:State))

//move types
trait Move {
  def change(state:State):State
}

case class Empty(glass: Int) extends Move {
  override def change(state: State): State = state updated(glass, 0)
}

case class Fill(glass: Int) extends Move {
  override def change(state: State): State = state updated(glass, capacity(glass))
}

case class Pour(from: Int, to: Int) extends Move{
  override def change(state: State): State = {
    val amount = math.min( state(from), capacity(to) - state(to) )
    (state updated(from, state(from)-amount)) updated (to, state(to) + amount)
  }
}

collection的updated method是一個immutable method，會產生一個新的collection，但是在某個index的value不同而已。

Modeling Paths

我們接著要來model path，某一條path其實就是每次move的歷史，我們把最新的move放在list head，有了這個history，我們可以利用每個move間的change來計算出最後的end state:

//Pathsclass Path(history:List[Move]) {
  def extend(move:Move) = (new Path(move::history))
  override def toString = (history.reverse mkString(" ")) + "-->" + endState

def endState: State = trackState(history)

  private def trackState(xs: List[Move]): State = xs match {
    case Nil => initalState    case move::xs1 => move change trackState(xs1)
  }

}

val initialPath = new Path(Nil)

上面trackState會先recursively抵達Nil，然後把initialState當作參數傳給第一個move的change method:

(lastMove change ...... (move2 chage (move1 change initialState)))

所以這是一個foldRight operation，我們可以把endState改寫成：

def endState: State = history.foldRight(initalState)( _ change _ )

Search space exploration

我們有了所有的models，現在可以開始做Breadth-first search。BFS search的過程類似從洋蔥的核心(initalState)，一層層往外extend出同樣長度的path，對洋蔥中的某一層來說，已經長出了一些paths，接下來要長出下一層，這邊就要用到Streams：

def from(paths:Set[Path]): Stream[Set[Path]] =
  if (paths.isEmpty) Stream.empty  
  else {
    val more:Set[Path] = for {
      path:Path <- paths
      extendedPath:Path <- moves map(x => path.extend(x))
    } yield extendedPath

    paths #:: from(more) //union the extended paths  }

val pathSets = from(Set(initialPath))

用set的原因是，重複的path對我們來說沒有意義。用stream的原因則是要控制exploration深度，如果用list的話，必須要加上搜尋深度的限制才行，否則變成無窮迴圈。

開始搜尋解答

假設有兩個容量為4和6的空瓶：

val problem = new Pouring(Vector(4,6))
problem.moves

所有的可能moves如下：

res0: IndexedSeq[problem.Move] = Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,1), Pour(1,0))

搜尋一層可能的paths，problem.pathSets.take(1).toList
res1: List[Set[problem.Path]] = List(Set(-->Vector(0, 0)))

搜尋二層可能的paths，problem.pathSets.take(2).toList
res1: List[Set[problem.Path]] = List(
Set(-->Vector(0, 0)),
Set(
Pour(0,1)-->Vector(0, 0),
Fill(0)-->Vector(4, 0),
Empty(1)-->Vector(0, 0),
Empty(0)-->Vector(0, 0),
Pour(1,0)-->Vector(0, 0),
Fill(1)-->Vector(0, 6))
)

我們現在可以寫這個倒水問題的solution method:

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

這個邏輯就是stream神奇的地方，pathSets是一個Stream[Set[Path]] type，本來應該是不會evaluate，但是由於stream的head是strict evaluation，所以head一定會evaluate，直到遇到第一個滿足if條件為止，此時stream就不會在evaluate下去。

深度不能確定是多少，要看滿足第一個if的path何時出現。This is not an optimized solution, might be very slow and not optimal!

total source code for now:

class Pouring(capacity: Vector[Int]) { //各種容量的杯子
  //states  type State = Vector[Int]
  val initalState = capacity map (_ => 0) //一開始所有杯子是空的
  //move types  trait Move {
    def change(state:State):State  }
  case class Empty(glass: Int) extends Move {
    override def change(state: State): State = state updated(glass, 0)
  }
  case class Fill(glass: Int) extends Move {
    override def change(state: State): State = state updated(glass, capacity(glass))
  }
  case class Pour(from: Int, to: Int) extends Move{
    override def change(state: State): State = {
      val amount = math.min( state(from), capacity(to) - state(to) )
      (state updated(from, state(from)-amount)) updated (to, state(to) + amount)
    }
  }

  //all indices  
  val glasses = 0 until capacity.length

  //all possible moves/actions  
  val moves:IndexedSeq[Move] =
    (for(g <- glasses) yield Empty(g)) ++    
    (for(g <- glasses) yield Fill(g)) ++      
    (for(g1 <- glasses; g2 <- glasses; if g1 != g2)        

      yield Pour(g1,g2))


  //Paths (我們記錄所有的moves，List head是最後的move)  
  class Path(history:List[Move]) {
    def extend(move:Move) = (new Path(move::history))
    def endState: State = history.foldRight(initalState)( _ change _ )
    override def toString = (history.reverse mkString(" ")) + "-->" + endState
  }

  val initialPath = new Path(Nil)

  def from(paths:Set[Path]): Stream[Set[Path]] =
    if (paths.isEmpty) Stream.empty    

    else {
      val more:Set[Path] = for {
        path:Path <- paths
        extendedPath:Path <- moves map(x => path.extend(x))
      } yield extendedPath

      paths #:: from(more) //union the extended paths    
    }

  val pathSets = from(Set(initialPath))

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


}