Ruby勉強
以下のエントリで面白いことをやっていたので試しにやってみた。
「人生を書き換える者すらいた。」 -- 「人材獲得作戦・4 試験問題ほか」
結構時間掛かったのでLv4かどうかは不明だけど勉強のため。
汚いコードだな……キューやリストは使ってないけど計算時間が発散しなければいいのかな?
#http://okajima.air-nifty.com/b/2010/01/post-abc6.html class Maze @@directions = [{'x'=>-1,'y'=>0},{'x'=>1,'y'=>0},{'x'=>0,'y'=>-1},{'x'=>0,'y'=>1}] def run load_map solve_map(@s['y'],@s['x'], 0) if select_route(@g['y'],@g['x']) then @map.each{|line| print line.to_s + "\n" } else print "fail!" end end def load_map @map = [] DATA.read.each_line {|line| @map.push line.chomp.split(//) } @cmap = [] @map.each{|m| @cmap.push Array.new(m.size, 65535)} @map.each_with_index{|line,i| line.each_with_index{|c,j| @s = {'x'=>j, 'y'=>i} if c == 'S' }} @map.each_with_index{|line,i| line.each_with_index{|c,j| @g = {'x'=>j, 'y'=>i} if c == 'G' }} end def solve_map(y,x,c) @cmap[y][x] = c if (@cmap[y][x] > c && @map[y][x] == ' ') @@directions.each{|d| solve_map(y+d['y'],x+d['x'],c+1) if (@cmap[y+d['y']][x+d['x']] > c+1 && @map[y+d['y']][x+d['x']] == ' ')} end def select_route(y,x) @map[y][x] = '$' if @map[y][x] == ' ' @@directions.each{|d| return true if @map[y+d['y']][x+d['x']] == 'S'} min_c = @cmap[y][x]; @@directions.each{|d| min_c = @cmap[y+d['y']][x+d['x']] if (@cmap[y+d['y']][x+d['x']] < min_c && @map[y+d['y']][x+d['x']] == ' ')} @@directions.each{|d| return select_route(y+d['y'],x+d['x']) if (@cmap[y+d['y']][x+d['x']] == min_c && @map[y+d['y']][x+d['x']] == ' ')} return false end end Maze.new.run __END__ ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************
処理時間は0.094秒
で、A*アルゴリズムを使って書いてみたものは以下。
論文自体は読んでないがウィキペディアで概要を見たままに記述。
長ったらしいのはノードデータの持ち方の問題だけど目を瞑る。
#!/usr/local/bin/ruby # http://okajima.air-nifty.com/b/2010/01/post-abc6.html # # using A-star # Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). # "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". # IEEE Transactions on Systems Science and Cybernetics SSC4 (2): pp. 100–107. # class Maze def initialize @map = [] @x_size = 0 @y_size = 0 # start point @s = {} # goal point @g = {} # A-star lists @open_list = Array.new @close_list = Array.new end def run load_map optimal_node = solve_map if optimal_node != nil then print_map(optimal_node) else print "fail!" end end def load_map data = DATA.read data.each_line {|line| @map.push line.chomp.split(//) } @map.each_with_index{|line,i| line.each_with_index{|c,j| @s = {'x'=>j, 'y'=>i} if c == 'S' @g = {'x'=>j, 'y'=>i} if c == 'G' } } @y_size = @map.size @x_size = @map[0].size end # using A-star def solve_map # push start node to open list node = {'x'=>@s['x'], 'y'=>@s['y'], 'f'=>0, 'parent'=>nil} @open_list.push node while (parent_node = pop_min_node) != nil # check goal if parent_node['x'] == @g['x'] && parent_node['y'] == @g['y'] return parent_node else @close_list.push parent_node end # look around [{'x'=>-1,'y'=>0},{'x'=>1,'y'=>0},{'x'=>0,'y'=>-1},{'x'=>0,'y'=>1}].each{|a| x = parent_node['x']+a['x'] y = parent_node['y']+a['y'] f = parent_node['f']+1 # move cost == 1 if (@map[y][x] == ' ' || @map[y][x] == 'G') # open list node = pop_open_list(x,y) if node != nil if node['f'] > f then child_node = {'x'=>x, 'y'=>y, 'f'=>f, 'parent'=>parent_node} @open_list.push child_node else @open_list.push node end next end # close list node = pop_close_list(x,y) if node != nil if node['f'] > f then child_node = {'x'=>x, 'y'=>y, 'f'=>f, 'parent'=>parent_node} @open_list.push child_node else @close_list.push node end next end # new node child_node = {'x'=>x, 'y'=>y, 'f'=>f, 'parent'=>parent_node} @open_list.push child_node end } end # cannot solve return nil end def pop_open_list(x, y) @open_list.each_with_index{|node,i| if node['x'] == x && node['y'] == y @open_list.delete_at(i) return node end } return nil end def pop_close_list(x, y) @close_list.each_with_index{|node,i| if node['x'] == x && node['y'] == y @close_list.delete_at(i) return node end } return nil end def pop_min_node f = 65535 node_i = -1 @open_list.each_with_index{|node,i| if node['f'] < f f = node['f'] node_i = i end } if node_i > -1 node = @open_list[node_i] @open_list.delete_at(node_i) return node else return nil end end def print_map(goal_node) # replace with '$' node = goal_node['parent'] while node != nil @map[node['y']][node['x']] = '$' node = node['parent'] end #display @map.each_with_index{|line,i| print line.to_s + "\n" } end end maze = Maze.new maze.run __END__ ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************
処理時間は0.125秒。リストの持ち方がアレとかノード判定がアレとか。