Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@obelisk68

Y字路巡り(どう書く)

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 が素直に書けます。

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?