いちばん長いしりとり
Posted feedbacks - Smalltalk
Squeak Smalltalk で。1000 語程度にも対応できるアルゴリズムにも挑戦したいところですが、とりあえずは愚直に。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | | url allWords intermediates dict results words |
url := 'http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txt' asUrl.
allWords := (url retrieveContents contents convertFromEncoding: #sjis) subStrings.
results := (Array new: 10 withAll: #()) asSortedCollection: [:a :b | a size > b size].
intermediates := (words := allWords shuffled first: 100) collect: [:each | OrderedCollection with: each].
dict := words groupBy: [:each | each first] having: [:group | true].
[intermediates notEmpty] whileTrue: [
| nextGen |
nextGen := OrderedCollection new.
(intermediates groupBy: [:each | each last last] having: [:group | true]) associationsDo: [:assoc |
| nexts |
nexts := dict at: assoc key ifAbsent: [#()].
assoc value do: [:each |
(nexts difference: each) ifEmpty: [results add: each; removeLast] ifNotEmptyDo: [:cands |
cands do: [:next | nextGen add: (each copyWith: next)]]]].
(intermediates := nextGen) size printString, ' ' displayAt: 0 asPoint].
^results first asArray
|
greentea #9391() Rating5/7=0.71
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。
なお、単語リストの一例として
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: 難聴者のための単語了解度試験用単語リスト
[ reply ]