Dijkstra.scala

import java.io.FileOutputStream

import scala.io.Source

/**
 * Created by teddy on 2015. 5. 1..
 */
object Dijkstra {
  val INPUT = "test.in"
  val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"

  def main(args: Array[String]): Unit = {
    val itr = Source.fromFile(INPUT).getLines()
    val sets = itr.next().toInt

//    val writer = new FileOutputStream(OUTPUT)
            val writer = Console.out
    try {
      Console.withOut(writer) {
        for (set <- 1 to sets) {
          val Array(leng, cntStr) = itr.next().split(' ')
          println(s"Case #${set}: ${solve(itr.next().toList, cntStr.toInt)}")
        }
      }
    } finally {
      writer.flush()
      writer.close()
    }
  }

  def table(x:Char, y:Char):(Boolean, Char) = (x, y) match {
    case ('1', y) => (true, y)
    case (x, '1') => (true, x)
    case (x,y) if x == y => (false, '1')
    case ('i','j') => (true, 'k')
    case ('i','k') => (false, 'j')
    case ('j','i') => (false, 'k')
    case ('j','k') => (true, 'i')
    case ('k','i') => (true, 'j')
    case ('k','j') => (false, 'i')
  }

  def solve(origin:List[Char], cnt:Int):Boolean = {

    def find(target:Char, rest:List[Char],  accr:Char, sign:Boolean, cnt:Int):Option[(Boolean, List[Char], Int)] = rest match {
      case Nil if cnt == 0  => None
      case Nil => find(target, origin, accr, sign, cnt -1)
      case y :: ys =>
        val (bool, c) = table(accr, y)
        if (c == target) Some((sign && bool, ys, cnt))
        else find(target, ys, c, sign && bool, cnt)
    }

    def calc(rest:List[Char], accr:Char, sign:Boolean):(Boolean, Char) = rest match {
      case Nil => (sign, accr)
      case y::ys =>
        val (bool, c) = table(accr, y)
        calc(ys, c, sign && bool)
    }

    find('i', origin, '1', true, cnt -1) match {
      case None => false
      case Some((bool, rest, cnt)) =>
        val rr = find('j', rest, '1', bool, cnt)
        println(rr)
        rr match {
          case None => false
          case Some((bool, rest, cnt)) =>
            val mod = cnt % 4
            val newBool = if(mod > 1) !bool else bool
            val res = cnt % 2
            val newList = if(res == 1) origin else Nil
            println(rest ++ newList,'1',newBool)
            val kk = calc(rest ++ newList,'1',newBool)
            println(kk)
            kk match {
              case (true, 'k') => true
              case _ => false
            }
        }
    }
  }
}