Caleidoscopioの日記

Ruby勉強

以下のエントリで面白いことをやっていたので試しにやってみた。

「人生を書き換える者すらいた。」 -- 「人材獲得作戦・４　試験問題ほか」

結構時間掛かったので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秒。リストの持ち方がアレとかノード判定がアレとか。

Permalink | コメント(0) | トラックバック(0) | 18:14