読者です 読者をやめる 読者になる 読者になる

試験問題を解いてみた

vim

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

なんか解いてる人が何人かいたので私も解いてみた。…例のごとく Vim で。

アルゴリズムは普通にA*使った。と言っても昔資料でちらっと読んだ程度で実際に使ったことはなかったので調べ直しましたが。
で、本来の問題の形式とは異なるけど、Vim なので問題テキストを開いたバッファで以下のVimスクリプトを :source すると結果に書き換わる、と言うようにした。
あと、無駄にstep数を数えて :echo します。

時間は、答えが出るようになるのに40分、が、よく検証したらA*になってなかったのでそこ直すのに(気づくのも含めて)更に30分。
とか言って実はまだA*になってないかも。違ってたら誰か教えてください。

function! s:func(n)
  return matchstr(expand('<sfile>'), '<SNR>\d\+_\zefunc$') . a:n
endfun

function! s:heuristic_cost(pos)
  return abs(a:pos[0] - s:goal[0]) + abs(a:pos[1] - s:goal[1])
endfunction

function! s:comp(a, b)
  return a:a.f - a:b.f
endfunction

function! s:around(board, pos)
  let list = []
  for [x, y] in [[-1, 0], [1, 0], [0, -1], [0, 1]]
    if a:board[a:pos[0] + x][a:pos[1] + y] != '*'
      call add(list, [a:pos[0] + x, a:pos[1] + y])
    endif
  endfor
  return list
endfunction

function! s:solve(progress)
  if !search('S', 'w')
    throw 'Start was not found.'
  endif
  let start = [line('.') - 1, col('.') - 1]
  if !search('G', 'w')
    throw 'Goal was not found.'
  endif
  let s:goal = [line('.') - 1, col('.') - 1]
  let board = map(getline(1, '$'), 'split(v:val, "\\zs")')

  let h = s:heuristic_cost(start)
  let open = {string(start): {'pos': start, 'f': h, 'h': h}}
  let close = {}
  let comp = s:func('comp')
  let step = 0
  while !empty(open)
    let now = sort(values(open), comp)[0]
    unlet open[string(now.pos)]

    if now.pos == s:goal
      let p = now.parent
      let dis = 1
      while has_key(p, 'parent')
        call cursor(p.pos[0] + 1, p.pos[1] + 1)
        normal! r$
        let p = p.parent
        let dis += 1
      endwhile
      return [step, dis]
    endif

    if a:progress && board[now.pos[0]][now.pos[1]] == ' '
      call cursor(now.pos[0] + 1, now.pos[1] + 1)
      normal! r.
      redraw
      sleep 50m
    endif

    let close[string(now.pos)] = now

    for around in s:around(board, now.pos)
      let h = s:heuristic_cost(around)
      let f = (now.f - now.h) + h + 1
      let k = string(around)
      if has_key(open, k)
        if f < open[k].f
          let open[k].f = f
          let open[k].parent = now
        endif
      elseif has_key(close, k)
        if f < close[k].f
          let open[k] = close[k]
          let open[k].f = f
          let open[k].parent = now
          unlet close[k]
        endif
      else
        let open[k] = {'pos': around, 'parent': now, 'f': f, 'h': h}
      endif
    endfor
    let step += 1
  endwhile
  throw 'Route was not found.'
endfunction

try
  echo s:solve(0)
catch
  echo v:exception
endtry

さらに、最後から4行目の

  echo s:solve(0)

  echo s:solve(1)

にすると、調べている箇所が少しずつ .(ドット) に置き換わる。これで解いてる経過が見れるね!(結果に.が入っちゃうけど)

このように、Vimアルゴリズムの可視化ツールとしても非常に有用なのです。あれ、なんでこんな結論に…。

追記: 案の定アルゴリズムを間違えまくってたので分かる範囲で修正。まだ違ってるかも…。あとついでに距離も出力するようにした。