読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【HELP】【Ruby】【アルゴリズム】8パズル dehashしないVer

 
■topic summary
coding without dehash function
dehash function is here


だめだ。
高橋さんのコードはdehashしていないから早いのかなー
と思ってまねしてみたけど大して早くならなかった。

 

変更点

・クラスプロパティ
・hash関数をPatternクラスのインスタンスメソッドに。
・dehashを使わない

 

処理時間

2回ずつ計測。

■前のコード
    user     system      total        real
5.024000   0.000000   5.024000 (  5.025287)
    user     system      total        real
5.382000   0.015000   5.397000 (  5.404309)

■今のコード
    user     system      total        real
5.086000   0.000000   5.086000 (  5.085291)
    user     system      total        real
4.976000   0.016000   4.992000 (  5.002286)

とくに変わってないよ!
なんでだろう。
 

変更したコード

require 'set'
require 'benchmark'

#表示用
def show(now_pattern)
  state = now_pattern
  while state
    #puts state.hash_code.to_s[0..3]
    #puts state.hash_code.to_s[4..7]
    #puts "------"
    state = state.parent
  end
end

class Pattern
  attr_accessor :nums, :parent
  def initialize (nums, parent)
    @nums = nums
    @parent = parent
  end
  def hash_code
    @nums.join("").to_i
  end
end

class PatternQue < Array
  def add_next_pattern(now_pattern, checked_set)
    blank = now_pattern.nums.index(9)
    if blank < 4
      copy_nums = now_pattern.nums.dup
      copy_nums[blank], copy_nums[blank+4] = copy_nums[blank+4], copy_nums[blank]
      checkdone_and_add(checked_set, Pattern.new(copy_nums, now_pattern))
    elsif
      copy_nums = now_pattern.nums.dup
      copy_nums[blank], copy_nums[blank-4] = copy_nums[blank-4], copy_nums[blank]
      checkdone_and_add(checked_set, Pattern.new(copy_nums, now_pattern))
    end
    if blank != 3 && blank != 7
      copy_nums = now_pattern.nums.dup
      copy_nums[blank], copy_nums[blank+1] = copy_nums[blank+1], copy_nums[blank]
      checkdone_and_add(checked_set, Pattern.new(copy_nums, now_pattern))
    end
    if blank != 0 && blank != 4
      copy_nums = now_pattern.nums.dup
      copy_nums[blank], copy_nums[blank-1] = copy_nums[blank-1], copy_nums[blank]
      checkdone_and_add(checked_set, Pattern.new(copy_nums, now_pattern))
    end
  end
  def checkdone_and_add(checked_set, candidate)
    return if checked_set.index(candidate.hash_code)
    checked_set << candidate.hash_code
    self << candidate
  end
end

def solve(nums)
  que = PatternQue.new
  first_pattern = Pattern.new(nums, nil)
  que << first_pattern
  checked_set = []
  checked_set << first_pattern.hash_code
  _solve(que, checked_set)
end

def _solve(que, checked_set)
  while now_pattern = que.shift
    return show(now_pattern) if now_pattern.hash_code == 91234567
    que.add_next_pattern(now_pattern, checked_set)
  end
  puts "not solve"
end
Benchmark.bm do |x|
  x.report { solve([2, 7, 4, 1, 5, 9, 3, 6]) }
end

ふむむむ。
こんど師匠に聞いてみよう。