[Ruby] ジェムストリング問題を解きました

結城浩 @hyuki さんのツイートで知った
ジェムストリング問題
http://www.hyuki.com/codeiq/#c14
を解いてCodeIQへ投稿しました。
考えた過程と、解答を生成するプログラムを残しておきます。

ジェムストリング問題は、宝石の並んでいるパターンから並ぶ規則を見つけ、特定のパターンが出現する位置を求める問題。
順列組合せの問題ですが総当たりすると計算量が多いため、計算量を抑えながら求める手段を見つけなければなりません。
今回もたくさんの気づきを与えてくれる、すばらしい出題でした。結城浩さん、ありがとう。

実行結果から

princess("abbbbcddddeefggg","eagcdfbe")
a 558834981
b 2198286197
c 558834981
d 2198286197
eab 21310301
eac 5452981
ead 21310301
eae 5452981
eaf 5452981
eagb 4914235
eagcb 416928
eagcdb 148912
eagcdd 113546
eagcde 38847
eagcdfbb 5023
eagcdfbd 5023
answer = 5578864439

総当たりはやらずにaで始まるものの個数を数え、bで始まるものの数を数え、全部を合計して求める作戦です。
プログラムの前半は、指定された文字列で始まる個数を数えることをやっていて
プログラムの後半は、何で始まる文字列を見つければ答えにたどりつくかを求めています。
プログラムは以下のとおり。ユニットテストもやっています。

# encoding: Shift_JIS
# 王女様の宝石パターンを見つけよう！
# @version 1.0 - 2014/02/08
# @author @saltheads
# @see https://codeiq.jp/ace/yuki_hiroshi/q684
# @note 

require 'test/unit'

#---------------------------------------------------------------
# 宝石の種類ごとの配列から全組み合わせの数を求める
# @param [Array] 各宝石の数の配列 [aの数,bの数,..]
#                処理の都合上、各要素の数は9個まで
# @param [Hash] すでに求めた結果
# @return [Int] 全部で何通りあるか。
def recursive_days(a1, h = Hash.new)
  a1.delete(0)                    # 0は削除
  return 0     if a1.size < 1     # 配列のサイズが0なら0
  return a1[0] if a1.size == 1    # 配列の要素が1つならその値そのもの
  key = a1.map{|n| n.to_s}.join   # 残った配列の要素を連結したkeyが
  val = h[key]                    # ハッシュに残っていれば、それを返す
  if val == nil
	  s = 0
	  plus = 0
	  a1.each_with_index{ |n,idx|
	    a2 = a1.dup
	    a2[idx] -= 1
	    s += recursive_days(a2, h)  # 再帰
	    plus += 1
	  }
	  val = (s + plus)
	  h[key] = val
  end
  val
end

# 宝石名から宝石の種類ごとの数をカウントした配列を作る
# 'abb'から[1,2]
# 'aaabbc'から[3,2,1]
def char_count(gems)
	count_array = Array.new
	gems_array = gems.split(//).sort
	gems_array.uniq.each { |c|
	  count_array << gems_array.select{|elem| elem == c}.size
	}
	count_array
end

class GemTest1 < Test::Unit::TestCase
  def test_char_count
    assert_equal(char_count(''),[])
    assert_equal(char_count('abb'),[1,2])
    assert_equal(char_count('aaabcc'),[3,1,2])
  end
end

# 宝石名から全組み合わせの数を求める
# @param [String] 全宝石名 'abc'
# @return [Int] 全部で何通りあるか。
def day_count(gems)
  count_array = char_count(gems)
  recursive_days(count_array)
end

class GemTest2 < Test::Unit::TestCase
  def test_day_count
    assert_equal(day_count(''),0)
    assert_equal(day_count('abb'),8)
    assert_equal(day_count('aaabcc'),188)
    assert_equal(day_count('abbbcddddeefggg'),2198286197)
  end
end

#---------------------------------------------------------------
# 宝石名の引き算をする
# @param [String] 'aaabcc' から
# @param [String] 'ac' を引くと
# @return [String] 'aabc' が返る
def gems_subtract(gems_from,gems_to)
	gems_from_array = gems_from.split(//).sort
	gems_to_array = gems_to.split(//).sort
  gems_to_array.each { |c|
  	index = gems_from_array.find_index(c)
  	gems_from_array.delete_at(index) if index != nil
  }
  gems_from_array.join
end

class GemTest3 < Test::Unit::TestCase
  def test_gems_subtract
    assert_equal(gems_subtract('abc', 'a'),"bc")
    assert_equal(gems_subtract('aaabcc', 'ac'),"aabc")
  end
end

# 宝石名全体からn個選んだ部分宝石名を作ったもののうち、比較対象より小さいものを求める
# @param [String] 全宝石名 'aaabcc'
# @param [String] 比較対象 'acbc'
# @return [Array] 部分宝石名を入れた配列   ["aa", "ab", "aca", "acba"]
def milestones(gems,target)
  array = Array.new
  key = ''
  target.split(//).each { |c|
	  smaller = gems.split(//).sort.uniq.select{|elem| elem < c}
	  array << smaller.map { |elem| key + elem}
	  key += c
	  gems = gems_subtract(gems, c)
	  printf "#{gems} #{key} #{c} #{smaller} #{array}\n" if false
  }
  array.flatten
end

class GemTest4 < Test::Unit::TestCase
  def test_milestones
    assert_equal(milestones('aaabcc','acbc'),["aa", "ab", "aca", "acba"])
    assert_equal(milestones('aaabcc','bcac'),["a", "ba", "bcaa"])
    assert_equal(milestones('aaabcc','c'),["a", "b"])
    assert_equal(milestones('aaabcc','cc'),["a", "b", "ca", "cb"])
    assert_equal(milestones('aaabcc','ccaa'),["a", "b", "ca", "cb"])
  end
end

# 王女様のパターンが何日目に見つかるか求める
# @param [String] 全宝石名 'aaabcc'
# @param [String] 見つけたいパターン 'acbc'
# @return [Int] 79
def princess(gems, target)
  print "--------------------------\n"
  print "princess(\"#{gems}\",\"#{target}\")\n"
	sum = target.size
	milestones(gems, target).each { |elem|
	  subs = gems_subtract(gems, elem)
	  count = day_count(subs)
	  print "#{elem} #{count}\n" if true
	  sum += (1 + count)
	}
  print "answer = #{sum}\n" if true
  sum
end

class GemTest6 < Test::Unit::TestCase
  def test_queen
    assert_equal(1,1)
    assert_equal(princess('aaabcc', 'a'), 1)
    assert_equal(princess('aaabcc', 'acab'), 63)
    assert_equal(princess('aaabcc', 'acbc'), 79)
    assert_equal(princess('aaabcc', 'b'), 91)
    assert_equal(princess('aaabcc', 'baa'), 93)
    assert_equal(princess('aaabcc', 'cc'), 175)
    assert_equal(princess('aaabcc', 'ccaba'), 183)
    assert_equal(princess('aaabcc', 'ccbaaa'), 188)
    assert_equal(princess('abbbbcddddeefggg', 'eagcdfbe'), 5578864439)
  end
end

おそらく、もっときれいなアルゴリズムがあるのだと思う。@hyuki さんの解説を待ちたい。