Dijkstra.scala

object Dijkstra extends App {

  def mul(x: Int, y: Int): Int = Vector(
    Vector(1, 2, 3, 4),
    Vector(2, -1, 4, -3),
    Vector(3, -4, -1, 2),
    Vector(4, 3, -2, -1))(x.abs - 1)(y.abs - 1) * (x.signum * y.signum)

  def equalMinusOne(toInts: Seq[Int], x: Long): Boolean = {
    Seq.fill((x%4).toInt)(toInts).flatten.fold(1)(mul) == -1
  }

  def isStartWithIJ(toInts: Seq[Int], x: Long): Boolean = {
    
    val seq = List.fill((if (8 < x) (x - 8) % 4 + 8 else x).toInt)(toInts).flatten
    
    def loop(target: Int, last: Int, list: List[Int]): Boolean = {
      if (last == target) 
        target == 3 || ((list.nonEmpty) && loop(3, list.head, list.tail))
      else if (list.isEmpty) 
        false
      else 
        loop(target, mul(last, list.head), list.tail)
      
    }
    
    loop(2, seq.head, seq.tail)
  }

  def isijk(s: String, x: Long): Boolean = {
    val toInts = s map (_ - 'i' + 2)
    equalMinusOne(toInts, x) && isStartWithIJ(toInts, x)
  } 

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val x = lineIn.next().split(' ').last.toLong
      lineOut(s"Case #$i: ${if (isijk(lineIn.next(), x)) "YES" else "NO"}")
    }

  val filename = "C-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")
  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }

}

DijkstraTest.scala

import org.scalatest._

import Dijkstra._

class DijkstraTest extends FunSuite {

  test("sample #1") {
    assert(isijk("ik", 1) === false)
  }
  
  test("sample #2") {
    assert(isijk("ijk", 1) === true)
  }
  
  test("sample #3") {
    assert(isijk("kji", 1) === false)
  }
  
  test("sample #4") {
    assert(isijk("ji", 6) === true)
  }
  
  test("sample #5") {
    assert(isijk("i", 10000) === false)
  }
  
  test("sample case") {
    val input = """5
2 1
ik
3 1
ijk
3 1
kji
2 6
ji
1 10000
i""".lines

    val expected = """Case #1: NO
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: NO""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("C-small-practice.in").getLines()
    val expected = io.Source.fromFile("C-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  ignore("full large case") {
    val input = io.Source.fromFile("B-large-practice.in").getLines()
    val expected = io.Source.fromFile("B-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}