Serendip

Web Studio

以前読んだブログに、とある求人の際のプログラミングの実技試験についての記事（人生を書き換える者すらいた。: 人材獲得作戦・３）があった。
その時は問題内容については、『ちょっとしたパズル』としか書かれていなかったが、記事の続編が投稿されたようで、試験問題の内容が公開されていた。

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

試験問題は迷路の最短経路探索プログラム。
最初、アルゴリズムとかがわからないので力技で解いてみたが、迷路内の空白が大きくなると処理が終らないのでアルゴリズムを調べてから再度実装してみた。
使ったアルゴリズムはダイクストラ法、こちらのサイト "ダイクストラ法（最短経路問題）" を参考にした。

あと、Gauche で解こうとしてみたが、行き詰まってしまったので Ruby で解いた。

追記：Gauche 版も解けた。

### ノードクラス
class Node
  def initialize(val, edges_to)
    @val = val        # マップ上での文字
    @edges_to = edges_to    # 各エッジの接続先のノード番号
    @edges_cost = []  # 各エッジのコスト
    @done = false     # 確定ノードか否か
    @cost = -1        # このノードへの現時点で判明している最小コスト
  end
  attr_accessor :val, :edges_to, :edges_cost, :done, :cost
end

### マップ文字列を2次元配列に変換する
def map2array(s_map)
  rt = []
  s_map.each{|line|
    rt.push(line.chomp.split(//))
  }
  return rt
end

### 接続先を探す
def find_movable(x, y, a_map)
  rt = []
  [[x,y-1], [x,y+1], [x-1,y], [x+1,y]].each{|v|
    if a_map[v[1]][v[0]].match(/(?:\s|S|G)/) then
      rt.push(v)
    end
  }
  return rt
end

### マップ配列(2次元)からノードリスト(配列)を作る
def array2nodelist(a_map)
  rt = []
  a_map.each_with_index{|y, i|
    _y = []
    y.each_with_index{|x, j|
      if x == ' ' || x == 'S' || x == 'G' then
        node = Node.new(x, find_movable(j,i,a_map))
        if x == 'S' then # スタートノードのコストを 0 にする
          node.cost = 0
        end
        _y.push(node)
      else
        _y.push(nil)
      end
    }
    rt.push(_y)
  }
  return rt
end

### ノードの座標を得る
def get_pos(nodes, str)
  nodes.each_with_index{|y,i|
    y.each_with_index{|x,j|
      if x && x.val == str then
        return [j,i]
      end
    }
  }
  return nil
end

### アルゴリズム実行
def search(nodes)

  # 確定ノードを探す
  while true
    done_node = nil
    nodes.each_with_index{|y,i|
      y.each_with_index{|x,j|
        if x then
          if x.done || x.cost < 0 then
            next
          end
          if done_node == nil || x.cost < done_node.cost then
            done_node = x
            break
          end
        end
      }
      if done_node then
        break
      end
    }
    # 確定ノードがなくなれば終了
    if done_node == nil
      break
    end

    # 確定フラグを立てる
    done_node.done = true
    # 接続先のノードの情報を更新する
    done_node.edges_to.each_with_index{|v, i|
      cost = done_node.cost + 1 # 各エッジのコストは 1
      nodes_to = nodes[v[1]][v[0]]
      if nodes_to.cost < 0 || cost < nodes_to.cost then
        nodes[v[1]][v[0]].cost = cost
      end
    }
  end

  return nodes
end

### 再帰的に最小コストの接続元ノードをたどり、valに'$'を代入していく
def get_from_node(node, nodes)
  if node then
    node.edges_to.each{|e|
      n = nodes[e[1]][e[0]]
      if n.cost == node.cost - 1 && n.val != 'S' then
        n.val = '$'
        return get_from_node(n, nodes)
      end
    }
  end
  return nil
end

### マップ文字列を受け取り、最短経路を探索して、結果のマップを印字する
def maiz(map_str)
  a_map = map2array(map_str)
  nodes = array2nodelist(a_map)
  result_nodes = search(nodes)
  goal_pos = get_pos(result_nodes, 'G')
  goal = result_nodes[goal_pos[1]][goal_pos[0]]
  get_from_node(goal, result_nodes)
  # 結果のマップを印字する
  result_nodes.each_with_index{|y,i|
    y.each_with_index{|x,j|
      if x then
        print x.val
      else
        print '*'
      end
    }
    print "\n"
  }
end

### 実行結果

# マップ文字列
$MAP1 =<<EOD
**********
*S*      *
* * ** * *
*   ** * *
***  *  G*
**********
EOD
$MAP2 =<<EOD
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
EOD
$MAP3 =<<EOD
**************************
*S                       *
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*                     G  *
*                        *
*                        *
*                        *
**************************
EOD

maiz($MAP1)
puts ""
maiz($MAP2)
puts ""
maiz($MAP3)

実行結果

$ ./maze.rb
**********
*S*$$$$$$*
*$*$** *$*
*$$$** *$*
***  *  G*
**********

**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

**************************
*S$$$$$$$$$$$$$$$$$$$$$  *
*                     $  *
*                     $  *
*                     $  *
*                     $  *
*                     $  *
*                     $  *
*                     G  *
*                        *
*                        *
*                        *
**************************

プログラミング言語 Ruby

posted with amazlet at 10.01.14

まつもと ゆきひろ David Flanagan
オライリージャパン
売り上げランキング: 24906

Amazon.co.jp で詳細を見る