SegmentalSearch.rb

class SegmentPatternSearch
   attr_accessor :patternCache

   def initialize()
      @segPattern = Array.new(10)
      @segPattern[0] = '1111110'
      @segPattern[1] = '0110000'
      @segPattern[2] = '1101101'
      @segPattern[3] = '1111001'
      @segPattern[4] = '0110011'
      @segPattern[5] = '1011011'
      @segPattern[6] = '1011111'
      @segPattern[7] = '1110000'
      @segPattern[8] = '1111111'
      @segPattern[9] = '1111011'
      
      @patternCache = Hash.new
      @minPattern
      @minCost = 100
   end

   def search(pattern,cost)
      #探索位置の基点を設定
      index = pattern.index(nil)
      return 0 if index.nil?

      (0..9).each{|i|
         tmpCost = cost
         if(!(pattern.index(i).nil?)) then
            next
         end
         p Time.now if index == 0
         tmpCost = cost + (index == 0 ? 0 : calc(@segPattern[pattern[index - 1]].split(//),@segPattern[i].split(//)))
         pattern[index] = i
         
         #最小コストパターン比較
         if @minCost >= tmpCost && index == pattern.length-1 then
            puts "#{tmpCost} : #{pattern}"
            @minCost = tmpCost
            @minPattern = pattern.to_s
         end
         
         #現地点が同じ且つこれまでの経路が順不同で同じ場合ならば計算不要 or 低ければ、コストの更新
         keyPattern = index == 0 ? "#{i}" : "#{pattern[0..index-1].sort.join}#{i}"
         if @patternCache.key?(keyPattern) && tmpCost > @patternCache[keyPattern] then
            next
         else
            @patternCache[keyPattern] = tmpCost
         end

         search(pattern,tmpCost)
      }
      pattern[index] = nil
      return 0
   end

   def calc(prevNum,nextNum)
      ret = 0
      (0..7).each{|i|
         ret += 1 if prevNum[i] != nextNum[i]
      }
      return ret
   end 

   def getResult
      return [@minCost,@minPattern]
   end

end

sps = SegmentPatternSearch.new
sps.search(Array.new(10,nil),0)
p sps.getResult