02
13
[Ruby] ジェムストリング問題を解きました
2014.02.13(21:59)
結城浩 @hyuki さんのツイートで知った
ジェムストリング問題
http://www.hyuki.com/codeiq/#c14
を解いてCodeIQへ投稿しました。
考えた過程と、解答を生成するプログラムを残しておきます。
ジェムストリング問題は、宝石の並んでいるパターンから並ぶ規則を見つけ、特定のパターンが出現する位置を求める問題。
順列組合せの問題ですが総当たりすると計算量が多いため、計算量を抑えながら求める手段を見つけなければなりません。
今回もたくさんの気づきを与えてくれる、すばらしい出題でした。結城浩さん、ありがとう。
実行結果から
プログラムの前半は、指定された文字列で始まる個数を数えることをやっていて
プログラムの後半は、何で始まる文字列を見つければ答えにたどりつくかを求めています。
プログラムは以下のとおり。ユニットテストもやっています。
ジェムストリング問題
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 さんの解説を待ちたい。