schwarzの雑記 このページをアンテナに追加 RSSフィード

08/01/02 (Wed)1月2日の雑記

[] 1月2日の雑記 - schwarzの雑記 を含むブックマーク

「いけるかな?」と「いけますよ!」の実装も追加。

class Station    
  attr_accessor :adjacency 
  # オブジェクト初期化
  def initialize(adjacency=[])    
    @adjacency = adjacency
  end 
  # 駅targetへの最短経路を返す
  def shortest_route(target)
    queue = [[self]]
    until queue.empty?
      route = queue.shift
      newroute = []
      route.last.adjacency.each{ |s|
        # 一度通った経路は除外
        unless route.include?(s)
          newroute << (route + [s])
          if s == target
            return newroute.last
          end
        end
      }
      queue.concat(newroute)
    end
    return nil
  end
  # 駅targetへの経路のうち、距離distanceマスのものを返す(いけるかな?)
  def route(target, distance)
    queue = [[self]]
    until queue.empty?
      route = queue.shift
      newroute = []
      route.last.adjacency.each{ |s|
        # 戻るのはダメ
        if route.length < 2 || route[-2] != s
          r = (route + [s])
          if (r.length - 1) != distance
            newroute << r
          elsif r.last == target
            return r
          end
        end
      }
      queue.concat(newroute)
    end
    return nil
  end
  # distanceマスで行くことのできる駅を全て返す(いけますよ!)
  def reachable_stations(distance)
    result = []
    queue = [[self]]
    until queue.empty?
      route = queue.shift
      newroute = []
      route.last.adjacency.each{ |s|
        # 戻るのはダメ
        if route.length < 2 || route[-2] != s
          if route.length == distance
            result << s
          else 
            newroute << (route + [s])
          end
        end
      }
      queue.concat(newroute)
    end
    return result.uniq
  end
end

「いけますよ!」のテスト。30マスで行ける場所の一覧を出して見ます。

p data["函館"].reachable_stations(30).collect{|s| s.name}
  #=> ["青森", "五稜郭", "渡島砂原", "森"]

意外と少ない。青森が行けるらしいので「いけるかな?」で経路テスト。

p data["函館"].route(data["青森"], 30).collect{|s| s.name}
  #=> ["函館", "五稜郭", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "渡島砂原", "森", "大沼", "五稜郭", "木古内", "吉岡海底", "青森"]

砂原線をぐるぐる回ってます。


ちなみに、本物の路線図はこちら。

http://www.jrhokkaido.co.jp/network/barrier/map_south.html


速度面がちょっと心配でしたが30マス(リニアカード相当)でも何ともなかったので大丈夫そうです。まあ駅が増えたらわかりませんが。

lptrocrkerlptrocrker 2014/06/01 21:15 jxgrqshtt, <a href="http://www.nijrijjjla.com/">pzminctmye</a> , [url=http://www.gtkzajvuyf.com/]hzsmeudctv[/url], http://www.hfxutjeqtf.com/ pzminctmye

ゲスト