リンクリストの探索

ポインタの無いrubyでどうやってリストを実現するのか？とgoogleに聞いてみたところ，ルート探索(2) - バリケンのRuby日記 - Rubyistを教えてくれた．ハッシュか配列に一意なキーを入れてそれで検索すればいいのか．

#!ruby -Ks

route_map = {
  :A => [:B, :D],
  :B => [:A, :C],
  :C => [:A, :D],
  :D => [:B, :C]
}

def find_all_route( map, start, goal, max_lv = nil)
  result = []
  route = lambda {|pos, work, lv|
    if pos==goal
      result.push( work.dup.push(pos))
    # 探索が深すぎるようなら打ち切る
    elsif max_lv and lv>=max_lv
      # work.size≒lvな気もするが、専用の変数を用意しておく
    else
      map[pos].each {|d|
        route[d, work.dup.push(pos), lv+1] unless work.include?(d)
      }
    end
  }
  route[ start, [], 1]
  result
end

def find_all_route_loop( map, start, goal, max_lv = nil)
  result = []
  work = [start]
  lv = 1

  loop do
    break if work.empty?
    ptr = work[-1]
    if (ptr==goal)
      result.push( work.dup)
      work.pop
      lv -= 1
    else
      n = (map[ptr]-work)[0]
      if n and (!max_lv or max_lv>lv)
        lv += 1
        work.push(n)
        next
      end
    end

    loop do
      lv -= 1
      ptr = work.pop
      break if work.empty?
      parent = work[-1]

      # カレントの次を探す
      m = map[parent] - work
      i = m.index(ptr)
      n = (i)? m[i+1]: nil
      if n and (!max_lv or max_lv>lv)
        lv += 1
        work.push(n)
        break
      end
    end
  end
  result
end


p find_all_route(route_map, :B, :D)
p find_all_route_loop(route_map, :B, :D)
#=> [[:B, :A, :D], [:B, :C, :A, :D], [:B, :C, :D]]

p find_all_route(route_map, :B, :D, 3)
p find_all_route_loop(route_map, :B, :D, 3)
#=> [[:B, :A, :D], [:B, :C, :D]]

自分の使い道としては，経路が見つからない場合もあるので打ち切り距離を入れられるようにしてみた以外はリンク先のパクり．

なぜか再帰しないバージョンも書いてみた．あまりにも再帰に慣れたためにアホのように苦労してしまった．使わない筋肉は衰えていくものだな*1．

非再帰版で map[parent] - workを最初，脳内言語をそのまま翻訳してmap[parent].reject{|i| work.include?(i)}のような書き方をしていたのを，途中でこっちの書き方に気づいた．

*1:いや再帰版がコピペしただけだから楽だったんだよ