GSnake.scala

object GSnake extends App {

  def snakeLength(R: Int, C: Int, actions: Seq[(Int, String)]): Int = {

    import collection.immutable.Queue

    type Cell = (Int, Int)

    case class Body(queue: Queue[Cell], set: Set[Cell]) {
      def :+(head: Cell): Body = Body(queue :+ head, set + head)
      def removeLast: Body = Body(queue.tail, set - queue.head)
      def contains(head: Cell): Boolean = set contains head
      def size = queue.size
    }
    val emptyBody = Body(Queue.empty, Set.empty)

    case class Board(head: Cell, body: Body, direction: Int, foodsEaten: Set[Cell]) {
      def forward: Board = {
        val (r, c) = head
        val (foodsEaten1, body1) =
          if (((r + c) % 2 == 1) && !(foodsEaten contains head))
            (foodsEaten + head, body :+ head)
          else (foodsEaten, (body :+ head).removeLast)
        val head1 = {
          def cycle(x: Int, X: Int) = (x - 1 + X) % X + 1
          val (dr, dc) = Vector((-1, 0), (0, +1), (+1, 0), (0, -1))(direction)
          (cycle(r + dr, R), cycle(c + dc, C))
        }
        Board(head1, body1, direction, foodsEaten1)
      }

      def turnRight(n: Int): Board = Board(head, body, (direction + n) % 4, foodsEaten)

      def isSnakeDead: Boolean = body contains head
    }

    val limit = actions.last._1 + (R max C)

    @annotation.tailrec
    def loop(time: Int)(state: (Board, List[(Int, String)])): Int = {
      val (board, turnings) = state
      if (board.isSnakeDead || time > limit) board.body.size + 1
      else loop(time + 1)(turnings match {
        case (t, d) :: tail if t == time =>
          (board.turnRight(d match { case "R" => 1; case "L" => 3 }).forward, tail)
        case _ => (board.forward, turnings)
      })
    }
    loop(0)(Board((1, 1), emptyBody, 1, Set.empty), actions.toList)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(s, r, c) = lineIn.next().split(' ').map(_.toInt)
      val actions = List.fill(s) {
        val Array(x, a) = lineIn.next().split(' ')
        (x.toInt, a)
      }
      lineOut(s"Case #$i: ${snakeLength(r, c, actions)}")
    }

  val filename = "D-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()
  }
}

GSnakeTest.scala

import org.scalatest._

import GSnake._

class GSnakeTest extends FunSuite with Matchers {

  test("sample #1") {
    /*
     3 x 3 //  Seq((1,"R"),(2,"L"),(3, "R")))

     0: (1, 1)                > 1
     1: (1, 2)                v 2
     2: (2, 2) (1, 2)         > 1
     3: (2, 3) (2, 2)         v 2
     4: (3, 3) (2, 3) (2, 2)  v 2
     
     */

    assert(snakeLength(3, 3, Seq((1,"R"),(2,"L"),(3, "R"))) === 3)
  }

  test("sample #2") {         
    assert(snakeLength(3, 3, Seq((2, "R"),(4, "R"), (6, "R"), (7, "R"), (8, "R"))) === 5)
  }

  test("sample case") {
    val input = """2
3 3 3
1 R
2 L
3 R
5 3 3
2 R
4 R
6 R
7 R
8 R""".lines

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

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

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("D-large-practice.in").getLines()
    val expected = io.Source.fromFile("D-large-practice.out.ref").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.")
  }

}