人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。
なんか解いてる人が何人かいたので私も解いてみた。…例のごとく 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 はアルゴリズムの可視化ツールとしても非常に有用なのです。あれ、なんでこんな結論に…。
追記: 案の定アルゴリズムを間違えまくってたので分かる範囲で修正。まだ違ってるかも…。あとついでに距離も出力するようにした。
