Note: 本文中的程序来自Martin Ordersky在www.coursea.org上所开设课程中的样例代码,文章主要目的是讲述我对此类问题解法及scala lazy evluation的理解。

问题描述

给你一个容量为9升的杯子和一个容量为4升的杯子,水不限使用,要求精确得到6升水。这就是“倒水问题”。我这里会讲述一个试用scala穷举法实现的一个例子。

建模

首先我们对这个问题进行建模。这个问题可以泛化为如下形式:

两个容量固定的杯子,可选的动作有:

  • 加满
  • 倒空
  • 从一个杯子倒入另一个杯子

初始状态为两个杯子都空,结束状态为其中一个杯子中的水量为所期望的结果。 从上面的描述中我们可以得到如下几个概念状态动作路径

状态用于表述各个杯子中当前的水量,动作用来改变各个杯子中水量,路径用于表示到达某一状态的动作序列。

状态

我们可以用一个Vector[Int]来表述杯子的状态,下标为杯子编号,元素值为当前杯子中的水量,另外,我们还需要一个Vector[Int]表示杯子的容量,下标为杯子编号,元素值为杯子的容量。于是我们得到如下代码:

class Pouring(capacity: Vector[Int]) {
  //States
  val initialState = capacity map (x => 0)
}

capacity为杯子容量, intialState为问题初始状态。

动作

由上可知,解决这个问题可以有三种动作, Empty, Fill, Pour,每个动作都会导致状态发生变化,于是我们得到如下代码:

//Moves
trait Move {
  def change(state: Vector[Int]): Vector[Int] 
}
case class Empty(glass: Int) extends Move {
  def change(state: Vector[Int]): Vector[Int] = state updated (glass, 0)
}
case class Fill(glass: Int) extends Move {
    def change(state: Vector[Int]): Vector[Int] = state updated (glass, capacity(glass))
}
case class Pour(from: Int, to: Int) extends Move {
  def change(state: Vector[Int]): Vector[Int] = {
      val amount = state(from) min (capacity(to) - state(to))
      state updated (from, state(from) - amount) updated (to, state(to) + amount)
  }
}

注意因为要考虑杯子的容量和杯子中剩余的水量,Pour中的change方法稍微复杂了些。

路径

接下来到了最重要的路径部分了,路径是到达某一状态的动作序列,我们需要一个List[Move]表述动作序列,一个Vector[Int]表述结束状态。 还需要一个extend方法来扩展当前的动作序列,即在当前路径上,应用一个动作(Fill, Empty, Pour),得到一个新的路径。于是我们得到如下代码:

//Paths
class Path(history: List[Move], val endState: Vector[Int]) {
  def extend(move: Move) = new Path(move :: history, move change endState)
  override def toString = (history.reverse mkString " ") + " -->" + endState
}

算法

这里我们要采用的是穷举法:

穷举从初始状态出发所有可能的动作,以及可能达到的状态,再穷举从这些状态出发所有可能的动作以及可能达到的状态,如此反复,直到找到一个可能达到的状态满足期望,则到达这个状态所经历的所有动作组成的路径即为问题的解。

首先我们来穷举给定一组杯子可能的动作:

val glasses = 0 until capacity.length
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))

其次,在不进行任何动作时,动作列表为空,所达到的状态为初始状态,则:

val initialPath = new Path(List(), initialState)

接下来到最关键的部分了,穷举从初始状态出发的所有可能扩展出来的路径及其所达到的状态,由于从任何状态开始穷举,都会得到一个一组路径,而不是一个,于是我们首先定义一个从给定一组路径,穷举其可能扩展出来的的路径的方法:

def from(paths: Set[Path], explored: Set[Vector[Int]]): 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)))
  }
}

paths为此次穷举的初始路径集合, explored用于记录已经穷举过的状态,以避免找出多条达到相同状态的路径,此方法通过穷举初始路径集合,在各个路径上扩展所有的动作,去掉那些达到状态已经被穷举过的路径,得到一组新的路径。

那么,从初始路径出发,其可能扩展出来的路径极其可能达到的状态如下:

val pathSets = from(Set(initialPath), Set(initialState))

对于给定的目标水量,遍历上述穷举结果路径找出endState包含目标水量的路径,如下:

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

总结

我们知道,穷举是一个无穷无尽的过程,上面的程序是如何运行的呢?其实是scala中强大的lazy load发挥了作用。我们再来看from方法的返回值类型,是Stream[Set[Path]], Stream 用于表述元素序列,它的一个重要特点是,只有需要使用到其中的某个元素时,程序才会去计算这个元素。于是,在程序运行时,scala并不会一下子把所有可能的路径都计算出来。对于solutions方法,也是一样。因此,scala只有在从solutions的计算结果中获取满足条件的路径时,pathSet才会穷举可能的路径,并且在找到满足条件的路径后,计算会立即结束,不会再列举其余的可能。

Terraform Tips: Multiple Environments

Terraform Tips: Multiple EnvironmentsIn [last post](https://nicholas.ren/2021/10/02/terraform-tips-layered-infrastrucutre.html), we explo...… Continue reading

Terraform Tips: Layered Infrastructure

Published on October 02, 2021