written by jooyunghan and me

waterpouring.scala

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