LoginSignup
0

More than 3 years have passed since last update.

Y字路巡り(どう書く)

Last updated at Posted at 2020-12-14

http://nabetani.sakura.ne.jp/hena/ord3ynode/

あるグラフに対し、「右折して進む/左折して進む/後戻り」の連続する指示が与えられた場合、通過するノードの列を出力する問題です。

Ruby
module YshapedRoadTour
  Graph = {"A"=>"DCB", "B"=>"CEA", "C"=>"FBA",
           "D"=>"EFA", "E"=>"DBF", "F"=>"ECD"}

  def self.solve(input)
    input = input.each_char
    result = ""

    go = ->(s, e) {
      result << e
      idx = Graph[e].index(s)
      case input.next
      when "b"
        go.(e, s)
      when "r"
        i = (idx - 1) % 3
      when "l"
        i = (idx + 1) % 3
      end
      go.(e, Graph[e][i])
    }
    go.("B", "A")
  rescue StopIteration
    result
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'YshapedRoadTour' do
    [
      ["b", "AB"],
      ["l", "AD"],
      ["r", "AC"],
      ["bbb", "ABAB"],
      ["rrr", "ACBA"],
      ["blll", "ABCAB"],
      ["llll", "ADEBA"],
      ["rbrl", "ACADE"],
      ["brrrr", "ABEDAB"],
      ["llrrr", "ADEFDE"],
      ["lrlll", "ADFEDF"],
      ["lrrrr", "ADFCAD"],
      ["rllll", "ACFDAC"],
      ["blrrrr", "ABCFEBC"],
      ["brllll", "ABEFCBE"],
      ["bbbrrlrl", "ABABEDFCB"],
      ["rbllrrrr", "ACABCFEBC"],
      ["lbrlrrblr", "ADABCFEFCA"],
      ["rlbrrrrbl", "ACFCADFCFD"],
      ["bllrlrbrrb", "ABCADEFEBCB"],
      ["rllrllllbb", "ACFDEBADEDE"],
      ["blblrlrrlbr", "ABCBEDFCABAC"],
      ["lrlrrrrrbrb", "ADFEBCFEBEDE"],
      ["rblllrlrrlrr", "ACABCADEFDABE"],
      ["rbrrlrblrllb", "ACADFEBEFDACA"],
      ["lrrrlrllrrllr", "ADFCABEFCADEBC"],
      ["rrlblllrrlrrb", "ACBEBADEFDABEB"],
      ["brbllrrbbrlrll", "ABEBADFCFCABEFC"],
      ["rrrbbrlbrlblrb", "ACBABACFCABADFD"],
      ["lllllllllllblrr", "ADEBADEBADEBEFDE"],
      ["llllllrllrlbrrr", "ADEBADEFCBADABED"]
    ].each do |input, expect|
      it input do
        assert_equal YshapedRoadTour.solve(input), expect 
      end
    end
  end
end

右折や左折を表現するのがむずかしいですね。ここではグラフを Hash で表しているのですが、{"A"=>"DCB"}なら、ノードAを中心として右回りにD, C, Bとなっているとの意味です。

入力はeach_charで Enumerator に変換して、一文字ずつnextで取り出しています。取り出すべきものがなくなると例外StopIterationが発生するので、それをrescueで捕捉して結果を返すようにしています。

go.(s, e)というのは、sからeへ進むという意味です。

ここでは再帰を使っていますが、ループの方がいいのでしょうね。でも、再帰が何となく好きなので(笑)。

ループ版

ループを使ったものはこんな感じでしょうか。やっぱりこの方がいいか(笑)。

module YshapedRoadTour
  Graph = {"A"=>"DCB", "B"=>"CEA", "C"=>"FBA",
           "D"=>"EFA", "E"=>"DBF", "F"=>"ECD"}

  def self.solve(input)
    input = input.each_char
    result = ""
    s, e = "B", "A"

    loop do
      result << e
      idx = Graph[e].index(s)
      case input.next
      when "b"
        s, e = e, s
      when "r"
        i = (idx - 1) % 3
        s, e = e, Graph[e][i]
      when "l"
        i = (idx + 1) % 3
        s, e = e, Graph[e][i]
      end
    end
    result
  end
end

なお、loop do ~ end は例外 StopIteration を捕捉するようになっているので、Enumerator#next が素直に書けます。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0