AlbocedeDna.scala

object AlbocedeDna extends App {

  case class DNA(dna: String) {
    private val MOD: Int = 1000000007
    private val memo = collection.mutable.Map.empty[BigInt, Int]
    def f(i: Int, j: Int, k: Int, ch: Char): Int =
      if (i <= 0 || j < 0 || k < 0) 0
      else memo.getOrElseUpdate(hash(i, j, k, ch), {
        (f(i - 1, j, k, ch) + {
          if (ch == dna(i - 1)) (ch match {
            case 'd' => f(i - 1, j, k + 1, 'd') + f(i - 1, j, k + 1, 'c')
            case 'c' => f(i - 1, j + 1, k, 'c') + f(i - 1, j + 1, k, 'b')
            case 'b' => f(i - 1, j, k - 1, 'b') + f(i - 1, j, k - 1, 'a')
            case 'a' => f(i - 1, j - 1, k, 'a') + (if (j == 1 && k == 0) count(i - 1) + 1 else 0)
          }) % MOD
          else 0
        }) % MOD
      })
    def count(i: Int) = f(i, 0, 0, 'd')

    def hash(i: Int, j: Int, k: Int, ch: Int): BigInt = {
      val s = dna.size
      ((((BigInt(i) * s) + j) * s) + k) * 4 + (ch - 'a')
    }

    def bottomUp(dp: Map[(Int, Int, Char), Int], acid: Char): Map[(Int, Int, Char), Int] = {
      (dp /: (for (j <- 0 until dna.size; k <- 0 until dna.size; ch <- 'a' to 'd') yield (j, k, ch))) {
        case (dp, (j, k, ch)) =>

          dp
      }
    }
  }

  def count(dna: String): Int = DNA(dna).count(dna.size)

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      lineOut(s"Case #$i: ${count(lineIn.next())}")
    }

  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()
  }
}

AlbocedeDnaTest.scala

import org.scalatest._

import AlbocedeDna._

class AlbocedeDnaTest extends FunSuite with Matchers {

  test("sample #5") {
    assert(count("d") === 0)
  }

  test("sample #1") {
    assert(count("abcd") === 1)
  }

  test("sample #2") {
    assert(count("aaaabcd") === 4)
  }

  ignore("f") {
    assert(DNA("aaaabbccd").f(2, 1, 0, 'a') === 2)
  }

  test("sample #3") {
    assert(count("aaaabbccd") === 28)
  }

  ignore("case #4 f") {
    assert(DNA("abcdabcdaabccd").f(10, 2, 0, 'a') === 14)
  }

  test("sample #4") {
    assert(count("abcdabcdaabccd") === 71)
  }

  ignore("large #1") {
    val dna = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd"
    assert(count(dna) === 163482408)
  }

  test("sample case") {
    val input = """5
abcd
aaaabcd
aaaabbccd
abcdabcdaabccd
b""".lines

    val expected = """Case #1: 1
Case #2: 4
Case #3: 28
Case #4: 71
Case #5: 0""".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.ref").getLines()

    lineComparison(input, expected)
  }

  ignore("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.")
  }

}