schwarzの雑記

■ [Ruby]

なぜかふと桃鉄が作りたくなったので、新年早々ちょっと書いてみました。

class Station    
  attr_accessor :adjacency 
  def initialize(adjacency=[])    
    @adjacency = adjacency
  end  
  def adjacent?(station)
    return @adjacency.include?(station)
  end
  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
end

class CityStation < Station
  attr_accessor :name
  attr_accessor :property  
  def initialize(name, property=[], adjacency=[])
    super(adjacency)
    @name = name
    @property = property
  end  
end
class PlusStation < Station
end
class MinusStation < Station
end
class CardStation < Station
end

これが駅の定義クラスです。駅データはわが本拠地函館の周辺のJR駅からこんな感じで作ってみます。砂原線でループもあるし五稜郭や木古内で分岐もあるのでそんなに悪い例ではないはず。

data = Hash.new
data["函館"]     = CityStation.new("函館")
data["五稜郭"]   = CityStation.new("五稜郭")
data["大沼"]     = CityStation.new("大沼")
data["渡島砂原"] = CityStation.new("渡島砂原")
data["森"]       = CityStation.new("森")
data["木古内"]   = CityStation.new("木古内")
data["江差"]     = CityStation.new("江差")
data["吉岡海底"] = CityStation.new("吉岡海底")
data["青森"]     = CityStation.new("青森")

data["函館"].adjacency     << data["五稜郭"]
data["五稜郭"].adjacency   << data["函館"] << data["大沼"] << data["木古内"]
data["大沼"].adjacency     << data["五稜郭"] << data["渡島砂原"] << data["森"]
data["渡島砂原"].adjacency << data["大沼"] << data["森"]
data["森"].adjacency       << data["大沼"] << data["渡島砂原"]
data["木古内"].adjacency   << data["五稜郭"] << data["江差"] << data["吉岡海底"]
data["江差"].adjacency     << data["木古内"]
data["吉岡海底"].adjacency << data["木古内"] << data["青森"]
data["青森"].adjacency     << data["吉岡海底"]

駅と駅との最短経路を求めようと思ったんですが、昔大学で教わった気もしますがさっぱり覚えてませんでした。かろうじて「幅優先探索」のような単語だけは覚えてたので復習、なんとかこんな風に求まりました。

p data["函館"].shortest_route(data["青森"]).collect{|s| s.name}
  #=> ["函館", "五稜郭", "木古内", "吉岡海底", "青森"]

p data["森"].shortest_route(data["江差"]).collect{|s| s.name}
  #=> ["森", "大沼", "五稜郭", "木古内", "江差"]

これで「あと15マス」のような表示ができます。「いけるかな？」は最短以外の経路も全て調べればできそうです。最近の桃鉄には「いけますよ」という機能もあるそうですが、これも応用でできるでしょう。