【HELP】【Ruby】【アルゴリズム】8パズル dehashしないVer
■topic summary
coding without dehash function
dehash function is here
だめだ。
高橋さんのコードは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
ふむむむ。
こんど師匠に聞いてみよう。