gemAlgorithm.rb

class GemBox
   attr_accessor :filPattern
   def initialize(boxSize, gemPattern, targetPattern)
      @boxSize = boxSize
      @gemPattern = gemPattern
      @filPattern = Hash.new
      @targetPattern = targetPattern
      @dayNum = 0
   end

   def start()
      initPattern = Array.new(@boxSize,nil)
      puts "gemBox    : #{replaceToChar(@gemPattern.join)}"
      puts "target    : #{replaceToChar(@targetPattern)}"

      t1 = Time.now 
      puts "final day : #{resolve(initPattern,1)}"
      t2 = Time.now
      
      puts "answer    : #{@dayNum}"
      p "#{t2 - t1} sec"
   end

   #再帰的に計算、最後のsumは探索用にしか使われない
   def resolve(pattern,sum)
      #ポインタの基点を設定
      index = pattern.index(nil)

      return 0 if index.nil?
      prev = -1

      num = 0
      ([email protected]).each{|i|
         #既に使われている宝石　or 前回探索済のものと同じ宝石であれば次へ
         if  !(pattern.index(i).nil?) || prev == @gemPattern[i] then
            next
         end

         pattern[index] = i

         #現在patternに含まれているポインタ以外の残りものをキャッシュ
         remainsPattern = retRemainsPattern(pattern)
         #探索用の変数、一歩手前までキャッシュした計算結果を取得するために、計算済みであっても敢えて計算する。
         compString = retStringPattern(pattern[0..index])
         #残りのパターンがすでに計算済みであればそれを返す、さもなければ再帰的に計算
         if [email protected]?(remainsPattern) || compString == @targetPattern[0..compString.length-1] then
            if(compString == @targetPattern) then
               @dayNum = sum + num;
            end
            @filPattern[remainsPattern] = resolve(pattern,num+sum+1)
         end
         num += 1 + filPattern[remainsPattern]
         prev = @gemPattern[i]
      }
      pattern[index] = nil
      return num
   end

   #与えられたgemPattern内ポインタから該当する位置の文字をつなげて文字列を返却
   def retStringPattern(pArray)
      string = ''
      pArray.each{|i|
         string << @gemPattern[i].to_s if !i.nil?
      }
      return string
   end

   #現在ポインタとして使用されているもの以外の@gemPattern内の数字を返却
   def retRemainsPattern(pArray)
      string = ''
      ([email protected]).each{|i|
         string << @gemPattern[i].to_s if pArray.index(i).nil?
      }
      return string
   end

   #数字をArray内で他に存在するものがないように進める
   def pointerAdd(array,num)
      tmpNum = num 
      while !array.index(tmpNum).nil?
         tmpNum += 1
      end
      return tmpNum
   end

   def replaceToChar(string)
      charArray = ('a'..'z').to_a
      tmp = ''
      string.split(//).each{|c|
         tmp << charArray[c.to_i - 1]
      }
      return tmp
   end

end

gemBox = GemBox.new(16,[1,2,2,2,2,3,4,4,4,4,5,5,6,7,7,7],'51734625')
gemBox.start()