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