DynamicGrid.scala

object DynamicGrid extends App {
  @annotation.tailrec
  def countConnected(ones: Set[(Int, Int)], count: Int = 0): Int =
    if (ones.isEmpty) count
    else countConnected(removeClusterFrom(ones, ones.head), count + 1)

  def removeClusterFrom(ones: Set[(Int, Int)], from: (Int, Int)): Set[(Int, Int)] = {
    val neighbors = for {
      dr <- -1 to 1
      dc <- -1 to 1 if dr.abs + dc.abs == 1
      (r, c) = from
      neighbor = (r + dr, c + dc) if ones contains neighbor
    } yield neighbor
    ((ones - from) /: neighbors)(removeClusterFrom)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(r, c) = lineIn.next().split(' ').map(_.toInt)
      lineOut(s"Case #$i:")
      ((for {
        (line, r) <- Seq.tabulate(r) { (lineIn.next(), _) }
        (digit, c) <- line.zipWithIndex if digit == '1'
      } yield (r, c)).toSet /: (1 to lineIn.next().toInt)) {
        (ones, _) =>
          val chars = lineIn.next().split(' ')
          chars.head match {
            case "Q" =>
              lineOut(countConnected(ones).toString)
              ones
            case "M" =>
              val Array(x, y, z) = chars.tail.map(_.toInt)
              z match {
                case 0 => ones - ((x, y))
                case 1 => ones + ((x, y))
              }
          }
      }
    }

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

DynamicGridTest.scala

import org.scalatest._

import DynamicGrid._

class DynamicGridTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(countConnected(Set((0,1), (0,3), (1,2), (2,1), (3,0), (3,1), (3,2), (3,3))) === 4)
  }

  test("removeCluster") {
    assert(removeClusterFrom(Set((0,1), (0,3), (1,2), (2,1), (3,0), (3,1), (3,2), (3,3)), (3, 3)) === Set((0,1), (0,3), (1,2)))
  }

  test("sample case") {
    val input = """1
4 4
0101
0010
0100
1111
7
Q
M 0 2 1
Q
M 2 2 0
Q
M 2 1 0
Q""".lines

    val expected = """Case #1:
4
2
2
2""".lines

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

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

}