DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Jonhnny has posted 4 posts at DZone. View Full User Profile

Escape From Zurg (in Scala)

08.26.2008
| 2635 views |
  • submit to reddit
        // http://jonhnny-weslley.blogspot.com/2008/08/escape-from-zurg.html

case class Toy(name: String, time: Int)

abstract class Direction
case object Left extends Direction
case object Right extends Direction

class Move(direction: Direction, toys: List[Toy]) {
  def cost = Iterable.max(toys.map{_.time})

  override def toString = "Move: " + direction + " " + toys.map{_.name}.mkString("[", ",", "]")
}

class State(direction: Direction, group: List[Toy]) {

  def done = group.isEmpty

  def next(f: (Move, State) => Unit) = direction match {
    case Left => for { tuple <- group.zipWithIndex
                       toy <- group drop (tuple._2 + 1)
                       toys = List(toy, tuple._1) }
                   f(new Move(Right, toys), new State(Right, group diff toys))

    case Right => for(toy <- (ToyStory.toys diff group))
                    f(new Move(Left, List(toy)), new State(Left, toy :: group))
  }

}

class SearchProblem(initial: State) {

  def foreach(f: List[Move] => Unit) {
    def solve(path: List[Move], state: State) {
      if (state.done) {
        f(path)
      } else {
        state next { (move, state) => solve(move :: path, state) }
      }
    }
    solve(Nil, initial)
  }

}

object ToyStory extends Application {

  val toys = Toy("Buzz", 5) :: Toy("Woody", 10) :: Toy("Rex", 20) :: Toy("Hamm", 25) :: Nil

  val problem = new SearchProblem(new State(Left, toys))
  for (path <- problem)
    if ((0 /: path) {(cost, move) => cost + move.cost} <= 60)
      println("Solution: " + path)

}