CodeIQ のジェムストリング問題を解いてみた

CodeIQ の結城浩氏出題のジェムストリング問題(王女様の宝石パターンを見つけよう！)に解答してみた.
解答中にコメントを書くと, それがフィードバックで紹介されてしまうことがあるとは知らなかった.
自分が書いたのは長くて目立つのに, 間違ったところがあるのが掲載されてしまった(汗).

以下は解答に書き込んだものを多少直したもの.

i 個の要素を持つ宝石の種類が 種類あるとする.
例えば, 使える宝石が a, b, b, b, b, c, d, d, d, d, e, e, f, g, g, g の16個なら, 1個の要素を持つ宝石の種類が a, c, f の 3種類なので , 2個の要素を持つ宝石の種類が e の 1種類で , 同様に .
これらの宝石(の全部または一部)を使った(長さ 0 のものを含む)パターンの数を とすると, 漸化式

が成立する.
ただし, がひとつでも負のときは とする.(←解答ではこれを書くのを忘れてた)

右辺の最初の 1 は長さ 0 のパターンのぶん.
あとは, 先頭の宝石を1個ずつ決めて, 残りの1個少なくなったパターンの総数から再帰的に計算している.
例えば, 上の16個の宝石を使ったときのパターンの総数 S(3,1,1,2) を計算するとき, 先頭の宝石が a のパターンの数は, 残りの b, b, b, b, c, d, d, d, d, e, e, f, g, g, g の15個を使ったパターンの総数 S(2,1,1,2) に等しい.
先頭が c と f のときも同様に, それぞれ S(2,1,1,2) 個のパターンがある.
結局, 先頭が a, c, f のパターンはまとめて 3S(2,1,1,2) 個と計算できる.
これが上の式の のところ.

特定の宝石パターンが何日目に現れるかは, この S を使えば計算できる.

例えば, 例題の a,a,a,b,c,c の6個の宝石が使用可能なときは, "baacc" の前には, "a" で始まるパターン, "baaa" で始まるパターン, "baaca" と ""(長さ 0 のパターン), "b", "ba", "baa", "baac" が存在する.
後ろの5個は "baacc" を切り縮めたパターンで, その数は "baacc" の長さ 5 に等しい.
"a" で始まるパターンは, "a" の後ろに, a 2個, b 1個, c 2個の宝石を使ったパターンを付け加えたものなので, その数は S(1,2,0) に等しい.
同様に "baaa", "baaca" で始まるパターンの数は S(0,1,0), S(1,0,0) に等しい.
結局

"baacc" の現れる日付
= "baacc" の前に現れる, 長さ 0 のものを含むパターンの数
= 5 + S(1,2,0) + S(0,1,0) + S(1,0,0)
= 5 + 90 + 3 + 2 = 100

となる.

以下提出したプログラム.
言語は Ruby.

上の S と [tex:k_i] はプログラムでは, それぞれ strings と kinds に対応.

@num_max の定義と使う場所が離れてて不恰好.
インスタンス変数はクラス定義内のどこからも見えてしまうから, num　をインスタンス変数にしたくなくてこういう書き方になったのだが, どうすれば良かったんだろう.

class Gemstring
  def initialize
    @h = {}
  end

  # 配列 kinds で個数を指定された宝石を使ったパターンの数(長さ 0 のものを含む)を返す
  # kinds[i] は i+1 個の要素を持つ宝石の種類の数
  def strings(kinds)
    return @h[kinds] if @h[kinds] # 計算済みならハッシュ h から引き出す
    s = 1
    kinds.each_with_index do |k, i|
      next if k == 0
      kinds_copy = kinds.dup
      kinds_copy[i] -= 1
      kinds_copy[i - 1] += 1 if i > 0
      s += k * strings(kinds_copy)
    end
    @h[kinds] = s
  end

  def num_to_kinds(num)
    kinds = Array.new(@num_max, 0)
    num.each_value {|n| kinds[n - 1] += 1 unless n == 0}
    kinds
  end

  # 配列 pattern で指定された宝石パターンが出現する日を返す
  # ハッシュ num はキーが宝石の種類で, 値がその宝石の数
  def order(num, pattern)
    @num_max = num.max_by {|g, n| n} [1]
    ord = pattern.size
    pattern.each do |gem|
      # gem を pattern の i 番目の宝石として, 以下を満たす宝石パターンの数を加算
      # ・長さが i 以上
      # ・pattern と i-1 番目まで一致している
      # ・i 番目の宝石 g が gem よりアルファベット順で若い
      (:a ... gem).each do |g|
        next if num[g] == 0
        num[g] -= 1
        ord += strings(num_to_kinds(num))
        num[g] += 1
      end
      num[gem] -= 1
    end
    ord
  end
end


# 確認用
def generate_patterns(pattern, num)
  puts Gemstring.new.order(Minis.dup, pattern).to_s +
    ":" + pattern.to_s.gsub(/[^\w]/, '')
  num.keys.sort.each do |gem|
    next if num[gem] == 0
    num[gem] -= 1
    generate_patterns(pattern + [gem], num)
    num[gem] += 1
  end
end

# minilist の日付が再現されることを確認
Minis = {:a=>3, :b=>1, :c=>2}
generate_patterns([], Minis.dup)
puts


# 王女の宝石パターン
Princess = [:e, :a, :g, :c, :d, :f, :b, :e]
Gems = {:a=>1, :b=>4, :c=>1, :d=>4, :e=>2, :f=>1, :g=>3}
# 解答
print Gemstring.new.order(Gems, Princess) # => 5578864439