Jumping Frogs 퍼즐

요즘 scala 언어를 배우고 있는 중입니다. Functional language가 어떤건지 관심이 있던 중 기회가 닿아 배우게 되었는데 상당히 재미있습니다. Scala는 JVM상에서 돌아가는 언어라서 java의 여러 라이브러리를 사용할 수 있는 장점이 있는데 scala에서 JavaFX를 사용하기 위한 ScalaFx의 예제로 Jumping Frogs 퍼즐이 있습니다. 소스는 여기에서 살펴볼 수 있고 퍼즐은 여기에서 풀어볼 수 있습니다.

며칠 전 풀어보다 잘 안풀려서 scala에서 한번 풀어보자고 프로그램을 짜기 시작했는데 아직 초보라 그런지 며칠간 고민하다 겨우 작성할 수 있었답니다. 잘 작성한 소스는 아니지만 Functional Language와 Scala의 느낌이 어느 정도 살아있는것 같아 올려놓았습니다. 결과를 보고 한번 풀어보니 이렇게 간단한걸 왜 못 풀었나 싶더군요.

object frogs {
  type State = List[Int]
  type Sets = List[State]
  type History = List[State]
 
  val setSize = 7                           //> setSize  : Int = 7
  def frogs(n:Int, code:Int) = ((0 until n) map (_ => code)).toList
                                                  //> frogs: (n: Int, code: Int)List[Int]
  val leftFrogs = frogs(setSize/2, 1)       //> leftFrogs  : List[Int] = List(1, 1, 1)
  val rightFrogs = frogs(setSize/2, 2)      //> rightFrogs  : List[Int] = List(2, 2, 2)
  val set = leftFrogs ++ List(0) ++ rightFrogs
                                                  //> set  : List[Int] = List(1, 1, 1, 0, 2, 2, 2)
  val target = rightFrogs ++ List(0) ++ leftFrogs
                                                  //> target  : List[Int] = List(2, 2, 2, 0, 1, 1, 1)

  def jump3(set:State, history:History, ans:List[History]):List[History] = {
    def possibleJumps(set:State): Sets = {
      val size = set length
      val zero = set indexOf 0
      val jump1 = if (zero > 0 && set(zero-1) == 1) set.updated(zero, 1).updated(zero-1, 0) else Nil
      val jump2 = if (zero > 1 && set(zero-2) == 1) set.updated(zero, 1).updated(zero-2, 0) else Nil
      val jump3 = if (zero < (size-1) && set(zero+1) == 2) set.updated(zero,2).updated(zero+1,0) else Nil
      val jump4 = if (zero < (size-2) && set(zero+2) == 2) set.updated(zero,2).updated(zero+2,0) else Nil
      List(jump1, jump2, jump3, jump4) filter (j => j!=Nil)
    }
    if (set == target) history.reverse::ans
    else possibleJumps(set).flatMap(s => jump3(s, s::history, ans))
  }                                         //> jump3: (set: week6.frogs.State, history: week6.frogs.History, ans: List[wee
                                                  //| k6.frogs.History])List[week6.frogs.History]
 
  jump3(set, List(), List()) map (s => s mkString "\n")
                                   //> res0: List[String] = List(List(1, 1, 0, 1, 2, 2, 2)
                                   //| List(1, 1, 2, 1, 0, 2, 2)
                                   //| List(1, 1, 2, 1, 2, 0, 2)
                                   //| List(1, 1, 2, 0, 2, 1, 2)
                                   //| List(1, 0, 2, 1, 2, 1, 2)
                                   //| List(0, 1, 2, 1, 2, 1, 2)
                                   //| List(2, 1, 0, 1, 2, 1, 2)
                                   //| List(2, 1, 2, 1, 0, 1, 2)
                                   //| List(2, 1, 2, 1, 2, 1, 0)
                                   //| List(2, 1, 2, 1, 2, 0, 1)
                                   //| List(2, 1, 2, 0, 2, 1, 1)
                                   //| List(2, 0, 2, 1, 2, 1, 1)
                                   //| List(2, 2, 0, 1, 2, 1, 1)
                                   //| List(2, 2, 2, 1, 0, 1, 1)
                                   //| List(2, 2, 2, 0, 1, 1, 1), List(1, 1, 1, 2, 0, 2, 2)
                                   //| List(1, 1, 0, 2, 1, 2, 2)
                                   //| List(1, 0, 1, 2, 1, 2, 2)
                                   //| List(1, 2, 1, 0, 1, 2, 2)
                                   //| List(1, 2, 1, 2, 1, 0, 2)
                                   //| List(1, 2, 1, 2, 1, 2, 0)
                                   //| List(1, 2, 1, 2, 0, 2, 1)
                                   //| List(1, 2, 0, 2, 1, 2, 1)
                                   //| List(0, 2, 1, 2, 1, 2, 1)
                                   //| List(2, 0, 1, 2, 1, 2, 1)
                                   //| List(2, 2, 1, 0, 1, 2, 1)
                                   //| List(2, 2, 1, 2, 1, 0, 1)
                                   //| List(2, 2, 1, 2, 0, 1, 1)
                                   //| List(2, 2, 0, 2, 1, 1, 1)
                                   //| List(2, 2, 2, 0, 1, 1, 1))
}