経路探索問題

ちょっと前にtwitterで流行ってた(?)人材獲得作戦・４　試験問題ほかの問題を試しに解いてみました。
(今ごろ...)
CとかC++とかRubyとかいるので、他にいなさそうなシェルスクリプトで実装。
Dijkstraのアルゴリズムを使いました。
配列の実装がヒドいので(それだけじゃないが)なんと、実行に3分も掛ります。

しかも、くだらないところ(evalとかスペルミス)でつまづいてしまって、
実装に約2時間もかかってしまった...。

反省:

• こういうalgorithmicなものをシェルスクリプトで書いちゃだめだろ
• evalは諸刃の刃
• 未定義の変数は空文字列に置換される、というのとevalを組み合わせると見付けにくいバグの温床
• ksh, bash, zshで評価のされかたが微妙に違う(設定によるのかな?)
  
• Dijkstraとか忘れてる...
• A*にしたらもうちょっと早くなるかなー。(もうあきたのでやらないけど)
• こんな下らないのに2時間も浪費した自分に反省。

なぜシェルスクリプトかって?
それは最近仕事でこんな程度のコードしか書いてないヘタレだからです。




使い方：

問題の図をコピペしてファイルへ保存し、シェルスクリプトの引数として食わせて実行します。

$ ./dijkstra.sh data.txt

-------- data.txt --------
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

#!/bin/bash
MSG () { echo "$@"; }
DIE () { MSG ERROR "$@"; exit 1; }
x_of () { echo ${1%,*}; }
y_of () { echo ${1#*,}; }

load_data_file () {
  local mazename="$1"
  local datafile="$2"
  local y=0
  local xmax=0
  [ -r "$datafile" ] || DIE "No data file given"
  while read line
    do
      let y++
      for x in $(seq 0 ${#line})
      do
          local status=${line:$x:1}
          local value
          case "$status" in
              "*"|" ") value="$status";;
              "S") value="S"; eval "${mazename}_start=$((x+1)),$y";;
              "G") value="G"; eval "${mazename}_goal=$((x+1)),$y";;
          esac
          eval "${mazename}_DATA_$((x+1))_${y}='$value'"
          if [ $x -gt $xmax ]; then
              xmax=$x
          fi
      done
  done < "$datafile"
  eval "${mazename}_height=$y"
  eval "${mazename}_width=$xmax"
}

dump_data () {
  local mazename="$1"
  local width=$(eval echo \$"${mazename}_width")
  local height=$(eval echo \$"${mazename}_height")
  echo "---- $mazename: ${width}x${height} ----"
  echo "   1   5    1   5    1"
  for y in `seq 1 $height`
  do
      printf '%2d ' $y
      for x in `seq 1 $width`
      do
          printf "%c" "`get_value ${mazename}_DATA $x,$y`"
      done
      printf '\n'
  done
}

get_value() {
  local mazename="$1"
  local xy="$2"
  local value
  eval value=\"\$"${mazename}_$(x_of $xy)_$(y_of $xy)"\"
  echo "$value"
}

set_value () {
  local mazename="$1"
  local xy="$2"
  local value="$3"
  eval "${mazename}_$(x_of $xy)_$(y_of $xy)='$value'"
}

get_adj () {
  local xy="$1"
  local dir="$2"
  local x=$(x_of $xy)
  local y=$(y_of $xy)

  case $dir in
      N) echo $x,$((y-1));;
      E) echo $((x+1)),$y;;
      S) echo $x,$((y+1));;
      W) echo $((x-1)),$y;;
  esac
}

get_from () {
  local mazename="$1"
  local xy="$2"
  local value
  eval value=\"\$"${mazename}_FROM_$(x_of $xy)_$(y_of $xy)"\"
  echo "$value"
}

is_reachable () {
  local mazename="$1"
  local xy="$2"

  local data=$(get_value ${mazename}_DATA $xy)
  case "$data" in
      '*')
          return 1;;
      S|G|_|@|' ') return 0;;
      *) DIE "BUG: Unknown data in $mazename:$xy='$data'";;
  esac
}

is_not_yet_reached () {
  local mazename="$1"
  local xy="$2"
  local value=$(get_value $mazename $xy)
  if [ -z "$value" ]
  then
      return 0
  else
      return 1
  fi
}

search_maze () {
  local mazename="$1"
  local start="$2"
  MSG "$start"
  local start_value=$(get_value $mazename $start)

  set_value ${mazename}_DATA $start "@"

  for dir in N E S W
  do
      local adj=$(get_adj $start $dir)
      local adj_value=$(get_value $mazename $adj)

      if is_reachable $mazename $adj
      then
          if [ -z "$adj_value" ] || [ $adj_value -gt $((start_value+1)) ]
          then
              set_value ${mazename}      $adj $((start_value+1))
              set_value ${mazename}_FROM $adj $start
              search_maze $mazename $adj
          fi
      fi
  done

  set_value ${mazename}_DATA $start "_"
}

backtrace () {
  local mazename="$1"
  local goal="$2"

  local from=$(get_from $mazename $goal)
  while [ -n "$from" -a "$(get_value ${mazename}_DATA "$from")" != S ]
    do
      set_value ${mazename}_DATA "$from" '%'
      from=$(get_from $mazename $from)
  done
}

trap 'echo; dump_data HOGE; exit' INT

main () {
  load_data_file HOGE "$1"

  set_value HOGE $HOGE_start 0
  search_maze HOGE $HOGE_start

  set_value HOGE_DATA $HOGE_start 'S'
  set_value HOGE_DATA $HOGE_goal  'G'
  backtrace HOGE $HOGE_goal
  dump_data HOGE
}

main "$1"