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)

}