Albocede DNA.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.collection.mutable.HashMap
import scala.io.StdIn


object Main extends App {
  Console.setIn(new FileInputStream("example.in"))

  Console.setIn(new FileInputStream("D-large-practice.in"))
  Console.setOut(new FileOutputStream("D-large-practice.out"))

  case class Node(l:Int, a_diff_c:Int, b_diff_d:Int, last:Char)

  def solve(s:String):BigInt = {
    @tailrec
    def _solve(s:String, nodes:HashMap[Node, BigInt]):BigInt = {
      if (0 == s.length) {
        nodes.filter{case (x, v) => x.a_diff_c == 0 && x.b_diff_d == 0 && x.last == 'd'}.map{case (x, v) => v}.sum
      } else {
        val newNodes = s.head match {
          case 'a' => nodes.toList.par.filter { case (x, v) => (x.last == 'd' && x.a_diff_c == 0 && x.b_diff_d == 0) || x.last == 'a' || x.last == ' ' }.map { case (x, v) => (Node(x.l + 1, x.a_diff_c + 1, x.b_diff_d, 'a'), v) }
          case 'b' => nodes.toList.par.filter { case (x, v) => x.last == 'a' || x.last == 'b' }.map { case (x, v) => (Node(x.l + 1, x.a_diff_c, x.b_diff_d + 1, 'b'), v) }
          case 'c' => nodes.toList.par.filter { case (x, v) => x.last == 'b' || x.last == 'c' }.map { case (x, v) => (Node(x.l + 1, x.a_diff_c - 1, x.b_diff_d, 'c'), v) }
          case 'd' => nodes.toList.par.filter { case (x, v) => x.last == 'c' || x.last == 'd' }.map { case (x, v) => (Node(x.l + 1, x.a_diff_c, x.b_diff_d - 1, 'd'), v) }
        }
        _solve(s.tail, (nodes /: newNodes){case ((acc, (key, count))) =>
          acc += ((key, acc.get(key).map(_ + count).getOrElse(count)))
        })
      }
    }
    _solve(s, HashMap(Node(0, 0, 0, ' ') -> 1)) % 1000000007
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { n =>
    val s = StdIn.readLine()

    println(s"Case #$n: ${solve(s)}")
  }
}