DouKaku?beta

challenge いちばん長いしりとり

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

なお、単語リストの一例として
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 - JavaScript

総当り法を取ると重くて動かないので、残集団の中で最大数を締める文字で終わるような単語を選択するようにしてみました。

しりとり開始の単語をランダムで選ぶ形式ですが、350前後までつながるのを確認。

選択対照の単語リストはテキストエリアに貼り付けて使用します。

リストの文字区切りはtab,改行,半角スペースで指定。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
<html>
  <head>
    <meta http-equiv="content-type" content="text/html;charset=shift_jis">
    <script type="text/javascript"><!-- //

ls0={};

ls0.wordmap=null;
ls0.counter=null;

ls0.getWordList = function(){
  var str = document.getElementById("ls0_ta").value;
  str = str.replace(/(\t|\r|\n)/g, " ");
  str = str.replace(/ +/g, " ");
  str = str.replace(/ +$/g, "");
  return str.split(" ");
};

ls0.lastChar = function(word){ return word.charAt(word.length-1); };

ls0.chainSort = function(a,b){
  if(!a || !b){ return (!a) ? ( (!b) ? 0 : 1 ) : -1; }
  var a0 = ls0.lastChar(a);
  var b0 = ls0.lastChar(b);
  if(!ls0.counter[a0] || !ls0.counter[b0]){
    return (!ls0.counter[a0]) ? ((!ls0.counter[b0])?0:1) : -1;
  }
  return ls0.counter[b0]-ls0.counter[a0];
};

ls0.execute = function(){
  var result=document.getElementById("ls0_result");
  result.innerHTML="";
  ls0.counter=[];
  ls0.wordmap=[];
  var indexes=[];
  var arr = ls0.getWordList();
  for(var i = 0; i < arr.length; i++){
    var c = arr[i].charAt(0);
    if(!ls0.counter[c]){
      ls0.counter[c]=0;
      ls0.wordmap[c]=[];
      indexes.push(c);
    }
    ls0.counter[c]++;
    ls0.wordmap[c].push(arr[i]);
  }
  for(var i=0;i<indexes.length; i++){
    var c = indexes[i];
    ls0.wordmap[c] = ls0.wordmap[c].sort(ls0.chainSort);
  }
  var pos = Math.floor(Math.random()*arr.length);
  var word = arr[pos];
  arr=null;
  var longest = ls0.getLongest(word);
  for(var i = 0; i < longest.length; i++){
    var div = document.createElement("div");
    div.innerHTML=i+":"+longest[i];
    result.appendChild(div);
  }
};

ls0.getLongest = function(word){
  var longest=[];
  var c0 = word.charAt(0);
  var cz = ls0.lastChar(word);
  ls0.counter[c0]--;
  for(var i = 0;i < ls0.wordmap[c0].length;i++){
    if(!ls0.wordmap[c0][i]){ continue; }
    if(ls0.wordmap[c0][i]!=word){ continue; }
    ls0.wordmap[c0][i]=null;
    break;
  }
  //
  if(ls0.counter[cz]&&ls0.counter[cz]>0){
    ls0.wordmap[cz]=ls0.wordmap[cz].sort(ls0.chainSort);
    for(var i = 0; i < ls0.wordmap[cz].length; i++){
      if(!ls0.wordmap[cz][i]) continue;
      longest = ls0.getLongest(ls0.wordmap[cz][i]);
      break;
    }
  }
  longest.unshift(word);
  return longest;
};

    // --></script>
  </head>
  <body>
    <div>
      <input type="button"
             onclick="javascript:ls0.execute()"
             value="start" />
    </div>
    <div>
      <textarea id="ls0_ta" cols="50" rows="10"></textarea>
    </div>
    <div id="ls0_result"></div>
  </body>
</html>

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]