CodeIQ の アルゴリズム問題「ジェムストリング問題」（ https://codeiq.jp/ace/yuki_hiroshi/q684 ）の解答出力プログラム。提出したのは answer_q684.py 、同じ処理を Ruby でも書いたのが answer_q684.rb 。

answer_q684.py

# -*- coding: utf-8 -*-
# answer_q684.py

# ===== DEFINITIONS =====

# メモ化再帰のためのキャッシュ
cache = {}

# 与えられた数値のリストから、各文字がその数だけある場合の全パターン総数を計算（メモ化再帰）
def calc_count(num_list):
  num_list = [n for n in num_list if n > 0] # num_list.select{|n|n > 0} in Ruby
  num_list.sort()
  key = ','.join(map(str, num_list))
  count = 0
  if key in cache:
    # その数値の並びに対する答えが既に計算済ならその値を返す
    count = cache[key]

  else:
    if len(num_list) == 1:
      # リストの長さが 1 ならその数値そのもの
      count = num_list[0]

    else:
      # それ以外 → （ある文字の数を１つ減らした場合のパターン総数 + 1）の総和
      for i in range(len(num_list)):
        sub_list = list(num_list)
        if sub_list[i] == 1:
          del sub_list[i]

        else:
          sub_list[i] -= 1

        count += calc_count(sub_list) + 1

    # 計算結果をキャッシュに登録
    cache[key] = count

  return count

# 全宝石に対して、指定したパターンが何番目に来るか（1-origin）を検索
def find_index(gems, pattern):
  # 各宝石がいくつあるか計算
  gem_hash = {}
  for c in gems:
    gem_hash[c] = gem_hash.get(c, 0) + 1

  # 結果格納変数初期化
  idx = 0
  # ※ pattern に指定された宝石を左から順に見て、辞書式順序でそれより前にあるパターン数を算出して合計していく。
  for c in pattern:
    for k in gem_hash.keys():
      if k < c:
        # 辞書式順序でターゲットの宝石より前の宝石を1つ減らし、残りの宝石で得られるパターン総数 + 1 を算出し加算
        gem_hash[k] -= 1
        num_list = [n for n in gem_hash.values() if n > 0]
        idx += calc_count(num_list) + 1
        gem_hash[k] += 1

    # ターゲットの宝石を1つ減らす。
    if gem_hash[c] == 1:
      # ターゲットの宝石が 0 になるときはハッシュから除去する
      del gem_hash[c]

    else:
      gem_hash[c] -= 1

    # 1（＝その宝石1つだけからなるパターン数に相当）を加算
    idx += 1

  # 結果返却
  return idx

# ===== MAIN =====
if __name__ == '__main__':
  # 全宝石（gems.txt より）
  gems = "abbbbcddddeefggg"
  # 王女様が求めているパターン（princess.txt より）
  pattern = "eagcdfbe"

  print(find_index(gems, pattern))
  # => 5578864439

answer_q684.rb

# -*- coding: utf-8 -*-
# answer_q684.rb

# ===== DEFINITIONS =====

# メモ化再帰を実現するハッシュ
h = Hash.new do |h, ptn|
  h[ptn] = if ptn.size < 1
    0
  elsif ptn.size == 1
    ptn[0]
  else
    (0...ptn.size).map {|i|
      next_ptn = ptn.dup
      next_ptn[i] -= 1
      next_ptn = next_ptn.reject(&:zero?).sort
      h[next_ptn] + 1
    }.inject(:+)
  end
end

# 全宝石に対して、指定したパターンが何番目に来るか（1-origin）を検索
find_index = ->(gems, pattern) do
  gems = gems.split('') if gems.is_a? String
  pattern = pattern.split('') if pattern.is_a? String
  gem_hash = Hash[*gems.group_by{|c|c}.flat_map{|c,a|[c,a.size]}]
  idx = 0
  pattern.each do |c|
    gem_hash.each_key do |k|
      next if k >= c
      gem_hash[k] -= 1
      idx += h[gem_hash.values.reject(&:zero?).sort] + 1
      gem_hash[k] += 1
    end
    if gem_hash[c] == 1
      gem_hash.delete(c)
    else
      gem_hash[c] -= 1
    end
    idx += 1
  end
  idx
end

# ===== MAIN =====
if $0 == __FILE__
  p find_index["abbbbcddddeefggg", "eagcdfbe"]
  # => 5578864439
end