mog project: Question for Ten Million Yen Annual Income

年俸1000万の会社の試験問題 (二番煎じ)

少し前に話題になっていた、年収1000万の会社の試験問題をScalaで解く、の二番煎じ。

問題

4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、
"AAG"という並びが含まれる文字列を全て列挙するプログラムを書きなさい。
ただし、nは3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものとし、
出力順序は問わないものとします。

コード

整数の累乗

これは自前で行った。
オーダーは悪い Θ(n) だが、n > 6 だとそもそも列挙する気が起きないのでコードの短さを優先。

import scala.math.BigInt

def pow(x: BigInt, y: Int): BigInt = if (y <= 0) 1 else x * pow(x, y - 1)

カウント

漸化式 + 無限Stream でカウント。
一度も "AAG" が出現しないパターンの場合の数を考える。

def count(n: Int): BigInt = {
  lazy val a: Stream[BigInt] = (0 to 2).map(pow(4, _)).toStream #:::
    (a zip a.drop(2) map { case (x, y) => 4 * y - x })
  pow(4, n) - a(n)
}

2013-04-05追記: n が小さいので、単純な再帰でも十分計算可能。

def count(n: Int): BigInt = if (n < 3) 0 else count(n - 1) * 4 - count(n - 3) + pow(4, n - 3)

列挙

1文字を2ビットに圧縮し、ビット演算で列挙してみた。

def getList(n: Int): List[String] = {
  def check(x: BigInt): Boolean = x match {
    case _ if x == 0 => false
    case _ if (x % 64) == 0x3e => true
    case _ => check(x / 4)
  }
  def decode(n: Int)(x: BigInt): String = {
    (n - 1 to 0 by -1).toList.map(i => "CTGA"(((x / pow(4, i)) & 3).toInt)).mkString("")
  }
  (BigInt(1) until pow(4, n)).toList.filter(check).map(decode(n))
}

実行例

// Count
(3 to 20) map count foreach println

// Enumerate
(3 to 6) map getList foreach println

実行結果

1
8
48
255
1268
6048
28033
127248
568480
2508031
10953452
47439632
204027713
872266264
3710060880
15709957631
66262531556
278519934528
List(AAG)
List(CAAG, TAAG, GAAG, AAGC, AAGT, AAGG, AAGA, AAAG)
List(CCAAG, CTAAG, CGAAG, CAAGC, CAAGT, CAAGG, CAAGA, CAAAG, TCAAG, TTAAG, TGAAG, TAAGC, TAAGT, TAAGG, TAAGA, TAAAG, GCAAG, GTAAG, GGAAG, GAAGC, GAAGT, GAAGG, GAAGA, GAAAG, ACAAG, ATAAG, AGAAG, AAGCC, AAGCT, AAGCG, AAGCA, AAGTC, AAGTT, AAGTG, AAGTA, AAGGC, AAGGT, AAGGG, AAGGA, AAGAC, AAGAT, AAGAG, AAGAA, AAAGC, AAAGT, AAAGG, AAAGA, AAAAG)
List(CCCAAG, CCTAAG, CCGAAG, CCAAGC, CCAAGT, CCAAGG, CCAAGA, CCAAAG, CTCAAG, CTTAAG, CTGAAG, CTAAGC, CTAAGT, CTAAGG, CTAAGA, CTAAAG, CGCAAG, CGTAAG, CGGAAG, CGAAGC, CGAAGT, CGAAGG, CGAAGA, CGAAAG, CACAAG, CATAAG, CAGAAG, CAAGCC, CAAGCT, CAAGCG, CAAGCA, CAAGTC, CAAGTT, CAAGTG, CAAGTA, CAAGGC, CAAGGT, CAAGGG, CAAGGA, CAAGAC, CAAGAT, CAAGAG, CAAGAA, CAAAGC, CAAAGT, CAAAGG, CAAAGA, CAAAAG, TCCAAG, TCTAAG, TCGAAG, TCAAGC, TCAAGT, TCAAGG, TCAAGA, TCAAAG, TTCAAG, TTTAAG, TTGAAG, TTAAGC, TTAAGT, TTAAGG, TTAAGA, TTAAAG, TGCAAG, TGTAAG, TGGAAG, TGAAGC, TGAAGT, TGAAGG, TGAAGA, TGAAAG, TACAAG, TATAAG, TAGAAG, TAAGCC, TAAGCT, TAAGCG, TAAGCA, TAAGTC, TAAGTT, TAAGTG, TAAGTA, TAAGGC, TAAGGT, TAAGGG, TAAGGA, TAAGAC, TAAGAT, TAAGAG, TAAGAA, TAAAGC, TAAAGT, TAAAGG, TAAAGA, TAAAAG, GCCAAG, GCTAAG, GCGAAG, GCAAGC, GCAAGT, GCAAGG, GCAAGA, GCAAAG, GTCAAG, GTTAAG, GTGAAG, GTAAGC, GTAAGT, GTAAGG, GTAAGA, GTAAAG, GGCAAG, GGTAAG, GGGAAG, GGAAGC, GGAAGT, GGAAGG, GGAAGA, GGAAAG, GACAAG, GATAAG, GAGAAG, GAAGCC, GAAGCT, GAAGCG, GAAGCA, GAAGTC, GAAGTT, GAAGTG, GAAGTA, GAAGGC, GAAGGT, GAAGGG, GAAGGA, GAAGAC, GAAGAT, GAAGAG, GAAGAA, GAAAGC, GAAAGT, GAAAGG, GAAAGA, GAAAAG, ACCAAG, ACTAAG, ACGAAG, ACAAGC, ACAAGT, ACAAGG, ACAAGA, ACAAAG, ATCAAG, ATTAAG, ATGAAG, ATAAGC, ATAAGT, ATAAGG, ATAAGA, ATAAAG, AGCAAG, AGTAAG, AGGAAG, AGAAGC, AGAAGT, AGAAGG, AGAAGA, AGAAAG, AACAAG, AATAAG, AAGCCC, AAGCCT, AAGCCG, AAGCCA, AAGCTC, AAGCTT, AAGCTG, AAGCTA, AAGCGC, AAGCGT, AAGCGG, AAGCGA, AAGCAC, AAGCAT, AAGCAG, AAGCAA, AAGTCC, AAGTCT, AAGTCG, AAGTCA, AAGTTC, AAGTTT, AAGTTG, AAGTTA, AAGTGC, AAGTGT, AAGTGG, AAGTGA, AAGTAC, AAGTAT, AAGTAG, AAGTAA, AAGGCC, AAGGCT, AAGGCG, AAGGCA, AAGGTC, AAGGTT, AAGGTG, AAGGTA, AAGGGC, AAGGGT, AAGGGG, AAGGGA, AAGGAC, AAGGAT, AAGGAG, AAGGAA, AAGACC, AAGACT, AAGACG, AAGACA, AAGATC, AAGATT, AAGATG, AAGATA, AAGAGC, AAGAGT, AAGAGG, AAGAGA, AAGAAC, AAGAAT, AAGAAG, AAGAAA, AAAGCC, AAAGCT, AAAGCG, AAAGCA, AAAGTC, AAAGTT, AAAGTG, AAAGTA, AAAGGC, AAAGGT, AAAGGG, AAAGGA, AAAGAC, AAAGAT, AAAGAG, AAAGAA, AAAAGC, AAAAGT, AAAAGG, AAAAGA, AAAAAG)