search_name_path.rb

NAMES = DATA.read.split(/\s*\n\s*/)
LENGTH = 2

connections = Hash.new{|h, s| h[s] = []}
NAMES.each do |name|
  name.chars.each_cons(LENGTH) do |array|
    part = array.join
    NAMES.each do |search_name|
      if search_name.include?(part)
        connections[name] << search_name
      end
    end
  end
end

search = lambda do |start_name, end_name|
  queue = Array.new
  flags = Hash.new{|h, s| h[s] = false}
  parents = Hash.new{|h, s| h[s] = nil}
  queue.push(start_name)
  until queue.empty?
    name = queue.shift
    finished = false
    connections[name].each do |next_name|
      unless flags[next_name]
        queue.push(next_name)
        flags[next_name] = true
        parents[next_name] = name
        if next_name == end_name
          finished = true
          break
        end
      end
    end
    if finished
      break
    end
  end
  history = Array.new
  name = end_name
  until name == start_name || name == nil
    history.unshift(name)
    name = parents[name]
  end
  history.unshift(start_name)
  next (name != nil) ? history : nil
end

history = search["ほんだみお", "ふたばあんず"]
puts(history.join(" -> "))
puts("#{history.size - 1} steps")


__END__
しまむらうづき
なかのゆか
みずもとゆかり
ふくやままい
しいなのりこ
いまいかな
もちだありさ
みむらかなこ
おくやまさおり
まなかみさと
こひなたみほ
おがたちえり
いがらしきょうこ
やなせみゆき
さくらいももか
えがみつばき
ながとみはすみ
よこやまちか
せきひろみ
おおたゆう
むなかたあつみ
ふじもとりな
おおはらみちる
ゆさこずえ
おおぬまくるみ
いちのせしき
まえかわみく
あかにしえりか
まつばらさや
あいはらゆきの
みやもとふれでりか
こばやかわさえ
さいおんじことか
ふたばあんず
やおふぇいふぇい
ももいあずき
すずみやせいか
つきみやみやび
ひょうどうれな
にわひとみ
どうみょうじかりん
やなぎきよら
いむらせつな
くさかべわかば
さかきばらさとみ
こしみずさちこ
あんざいみやこ
あさのふうか
おおにしゆりこ
あべなな
くどうしのぶ
くりはらねね
こがこはる
くらりす
さくままゆ
むらまつさくら
しらぎくほたる
はやさかみれい
ありうらかんな
おとくらゆうき
はらだみよ
いけぶくろあきは
しぶやりん
くろかわちあき
まつもとさりな
きりのあや
たかはしれいこ
あいかわちなつ
かわしまみずき
かみやなお
かみじょうはるな
あらきひな
とうごうあい
ただりいな
みずきせいら
ささきちえ
みふねみゆ
はっとりとうこ
きばまなみ
ふじわらはじめ
にったみなみ
みずのみどり
ふるさわよりこ
たちばなありす
さぎさわふみか
やがみまきの
らいら
あさりななみ
へれん
まつながりょう
こむろちなみ
たかみねのあ
たかがきかえで
かんざきらんこ
いじゅういんめぐみ
ひいらぎしの
ほうじょうかれん
けいと
せなしおり
あやせほのか
さじょうゆきみ
しのはられい
わくいるみ
よしおかさき
うめきおとは
しらさかこうめ
きしべあやか
うじいえむつみ
にしかわほなみ
なるみやゆめ
ふじいとも
しおみしゅうこ
わきやまたまみ
おかざきやすは
はやみかなで
おおいしいずみ
まつおちづる
もりくぼのの
あなすたしあ
やまとあき
ゆうきはる
にのみやあすか
きりゅうつかさ
もちづきひじり
たかふじかこ
ほんだみお
たかもりあいこ
なみきめいこ
りゅうざきかおる
きむらなつき
まつやまくみこ
さいとうようこ
さわだまりな
やぐちみう
あかぎみりあ
あいのなぎさ
まなべいつき
おおつきゆい
ひめかわゆき
きたみゆず
うえだすずほ
えびはらなほ
おいかわしずく
こせきれいな
えとうみさき
ほししょうこ
かたぎりさなえ
ほりゆうこ
にしじまかい
まとばりさ
ざいぜんときこ
よりたよしの
あいばゆみ
ののむらそら
はまかわあゆな
わかばやしともか
じょうがさきみか
じょうがさきりか
せんざきえま
ひのあかね
もろぼしきらり
とときあいり
なたーりあ
そうまなつみ
まきはらしほ
むかいたくみ
いちはらにな
きたひなこ
すぎさかうみ
きたがわまひろ
めありーこくらん
こまついぶき
みよしさな
きゃしーぐらはむ
なんばえみ
はまぐちあやめ
むらかみともえ
つちやあこ
しゅとうあおい
さえじまきよみ
さとうしん
なんじょうひかる
いゔさんたくろーす