CodeIQ「ジェムストリング問題」の回答

gemstring.txt

5578864439
ENV: Scala
POINT: 目的のパターンに至るまでの組み合わせの数を再帰的に求める。一度求めた値は再利用して計算量を抑える。

■POINTの補足
種類毎の宝石数をベクトルa、その時の全パターン数をf(a)であらわすと、
aが１次元の時、f(a)はaの絶対値となる。また、aから各種類の宝石のうちひとつを選んで取り去った
ベクトルの集合Bに対して、f(a)=Σ(f(b)+1) | b<-B
例えば、宝石"aaabcc"が与えられた時、全ての組み合わせは
=f([3,1,2])
=(f([2,1,2])+1)+(f([3,2])+1)+(f([3,1,1])+1)
=...
=188

■注意点
・順列を全て求めようとするとメモリが足りなくなる
・頭から目的のパターンまでを数え上げると計算量が膨大になる
・パターン数を求める方法を採用して一度計算した値を再利用すると大幅に計算量を抑えられる
・答えは32ビットでは足りないためLong型が必要
・minilist.txtで自動テストを行うと安心感が得られる

■ベンチマーク
101[ms]

■コードゴルフ(Scala, 512 bytes, 153[ms])
object J{type G=Map[Char,Int];type S=String
val h=collection.mutable.Map[Any,Long]()
def y(g:G):Long=h.getOrElseUpdate(g.map(_._2),if(g.size<1)0 else(for{(c,i)<-g}yield(g+(c->(i-1)))filter(_._2>0))map(y(_)+1)sum)
def d(c:Char,s:G)=s.get(c)map{i=>if(i>1)s+(c->(i-1))else s-c}
def i(s:G,t:S):Long=t.headOption.map{h=>(for{(a,_)<-s;if a<h;b<-d(a,s)map(y(_)+1)}yield b).sum+i(d(h,s)get,t.tail)+1}getOrElse 0
def main(args:Array[S])=println(i("abbbbcddddeefggg"groupBy(a=>a)map(a=>(a._1,a._2.size)),"eagcdfbe"))}

■感想
ナムドット問題に比べて随分簡単だなーと思ってプログラムを実行してみたら、処理が返ってこなくて泣きました。
いつも面白い問題ありがとうございます。