GoogolString.scala

object GoogolString extends App {

  @annotation.tailrec
  def kthChar(k: BigInt, isReversed: Boolean = false): Boolean =
    if (k.bitCount == 1) isReversed
    else kthChar((BigInt(1) << k.bitLength) - k, !isReversed)

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) 
      lineOut(s"Case #$i: ${if(kthChar(BigInt(lineIn.next()))) "1" else "0"}")
    
  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()
  }
}

GoogolStringTest.scala

import org.scalatest._

import GoogolString._

class GoogolStringTest  extends FunSuite {

  test("sample #1") {
    assert(kthChar(1) === false)
  }

  test("sample #2") {
    assert(kthChar(2) === false)
  }

  test("sample #3") {
    assert(kthChar(3) === true)
  }

  test("sample #4") {
    assert(kthChar(10) === false)
  }

  test("sample case") {
    val input = """4
1
2
3
10""".lines

    val expected = """Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0""".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.")
  }

}