Skip to content

Instantly share code, notes, and snippets.

@japaz
Forked from yankov/gist:5538283
Last active December 17, 2015 05:49
Show Gist options
  • Save japaz/5560642 to your computer and use it in GitHub Desktop.
Save japaz/5560642 to your computer and use it in GitHub Desktop.
package week7
object test {
val problem = new Pouring(Vector(4, 9)) //> problem : week7.Pouring = week7.Pouring@4bbd7848
problem.moves //> res0: scala.collection.immutable.IndexedSeq[Product with Serializable with we
//| ek7.test.problem.Move] = Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,
//| 1), Pour(1,0))
problem.solutions(6).take(3).toList //> res1: List[week7.test.problem.Path] = List(Fill(1) Pour(1,0) Empty(0) Pour(1
//| ,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0)-->Vector(4, 6), Fill(1) Pour(1,0) E
//| mpty(0) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) Empty(0)-->Vector(0,
//| 6))
}
package week7
class Pouring(capacity: Vector[Int]) {
// States
type State = Vector[Int]
val initialState = capacity map (x => 0)
// Moves
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 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
class Path(history: List[Move], val endState: State) {
def extend(move: Move) = new Path(move :: history, move change endState)
override def toString = (history.reverse mkString " ") + "-->" + endState
}
val initialPath = new Path(Nil, initialState)
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))
def solutions(target: Int): Stream[Path] = {
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment