Skip to content

Instantly share code, notes, and snippets.

@zlqhem
Last active December 27, 2015 23:49
Show Gist options
  • Save zlqhem/7408471 to your computer and use it in GitHub Desktop.
Save zlqhem/7408471 to your computer and use it in GitHub Desktop.
written by jooyunghan and me
object waterpouring {
type State = (Int, Int)
val initState = (0, 0)
val target = 6
val limit = (4, 9)
abstract class Action {
def apply(current:State):State
}
case class Fill(jug:Int) extends Action {
def apply(current:State) : State = this match {
case Fill(0) => (limit._1, current._2)
case Fill(1) => (current._1, limit._2)
}
}
case class Empty(jug:Int) extends Action {
def apply(current:State) : State = this match {
case Empty(0) => (0, current._2)
case Empty(1) => (current._1, 0)
}
}
case class Pour(from:Int, to:Int) extends Action {
def apply(current:State) : State = this match {
case Pour(0, 1) => {
val cap = Math.min(current._1, limit._2 - current._2)
(current._1 - cap, current._2 + cap)
}
case Pour(1, 0) => {
val cap = Math.min(current._2, limit._1 - current._1)
(current._1 + cap, current._2 - cap)
}
}
}
val actions = List(Fill(0), Fill(1), Empty(0), Empty(1), Pour(0, 1), Pour(1, 0))
def nextState(current:State, history:List[Action]) : List[(State, List[Action])] = {
for (action <- actions) yield {
(action(current), action::history)
}
}
def nextLegalStates (states:List[(State, List[Action])], visited:Set[State]): List[(State, List[Action])] = {
states filterNot (visited contains _._1)
}
def find(paths:List[(State, List[Action])], visited:Set[State]):(State, List[Action]) = {
val next = paths.flatMap { case (s, history) => nextLegalStates(nextState(s, history), visited) }
val result = next find { case (s,history) => s._1 == target || s._2 == target }
result match {
case Some(found) => found
case _ => find(next, visited ++ (next map (_._1)))
}
}
def main(args: Array[String]) = {
val (s, history) = find(List((initState, Nil)), Set(initState))
var state = initState
for (a <- history.reverse) {
state = a(state)
println(a, state)
}
}
}
/* 출력 결과
(Fill(1),(0,9))
(Pour(1,0),(4,5))
(Empty(0),(0,5))
(Pour(1,0),(4,1))
(Empty(0),(0,1))
(Pour(1,0),(1,0))
(Fill(1),(1,9))
(Pour(1,0),(4,6))
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment