いちばん長いしりとり in Ruby DouKaku?

いちばん長いしりとり

単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう

see: 難聴者のための単語了解度試験用単語リスト

post comment

Posted feedbacks - Ruby

リチャード・ドーキンスの「遺伝子の川」を読んでヒントを得たロジックです。各単語をDNA切片と見なし、接続可能な全相手との新切片をリストに追加していきます。 100語程度以上では計算量が多くなります。

# -*- coding: utf-8 -*-

word_list = []
max_word_list = []
max_word_list_lth = 0

while w = gets
  w.chomp.split().each{|i|
    ii = i.split(//)
    word_list << [[i], ii[0], ii[-1]]
  }
end

while w = word_list.shift
  if w[0].size > max_word_list_lth
    max_word_list = w
    max_word_list_lth = w[0].size
  end
  word_list.each{|i|
    word_list << [w[0] + i[0], w[1], i[2]] if (w[2] == i[1]) && (w[0] == (w[0] - i[0]))
    word_list << [i[0] + w[0], i[1], w[2]] if (w[1] == i[2]) && (i[0] == (i[0] - w[0]))
  }
end

printf("max= %d words , %s\n",max_word_list_lth, max_word_list[0])

DouKaku?

いちばん長いしりとり

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq