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マス(リニアカード相当)でも何ともなかったので大丈夫そうです。まあ駅が増えたらわかりませんが。

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

08/01/01 (Tue)1月1日の雑記

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

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

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

yf30yf302008/01/02 21:24すごいな~

DQにもすごろく場があるし
参考に…できるのでしょうか?^^

どうも新しいスクリプトをXPで作る気力が減ってます。
ちょっとまずいなぁ~

SchwarzSchwarz2008/01/03 05:31あけましておめでとうございます。

そういえばDQにもありましたね。
グラフ理論の問題としては桃鉄よりは簡単そうですけど、複数の階層に分かれてたりワープがあったりと、やっぱり大変そうな予感。

こんなので参考になれば幸いです。

07/12/11 (Tue)12月11日の雑記

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

VX体験版やってみました。なんとなく2000への回帰が感じられます。


スクリプトを流し読みしてみて、まずシーンクラスがだいぶ変わったと思います。開始処理・メイン処理・終了処理・・・というようにメソッドが分かれていて、いい感じです。


だいぶコメントが取っ払われているのでとっつきにくいかもしれませんが、最低限のことは書かれているし、かえってコードが読みやすいと言えるかもしれません。


既存のコードの改造は大の苦手ですが、VXでは少し頑張ってみようかとも思っております。

mr-80bmr-80b2007/12/12 23:32おお。
今回もRubyでスクリプト書けるってことですか。
じゃあ買おうかなぁ。
ライセンス認証の仕組みが、改善されているといいなぁ。

SchwarzSchwarz2007/12/13 22:13認証はXPと同じシステム名のようなので、あまり期待できないですね・・・