いちばん長いしりとり
Posted feedbacks - Python
% time shiritori.py < data.txt
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 101 102 103 104 105 106 107 | #!/usr/bin/python
# -*- coding: utf-8 -*-
# http://ja.doukaku.org/277/
import sys
ENCODING = 'utf8'
class Word:
def __init__(self, word):
self._word = word
self._trailwords = []
def word(self):
return self._word
def head_char(self):
return self.word()[0]
def tail_char(self):
return self.word()[-1]
def is_trailword(self, trailword):
return self.tail_char() == trailword.head_char()
def is_last_word(self):
return self.tail_char() in (u'ん', u'ン')
def append_trailword_list(self, trailword):
if not self.is_last_word() and self.is_trailword(trailword):
self.trailwords().append(trailword)
def trailwords(self):
return self._trailwords
def num_trailwords(self):
return len(self.trailwords())
class WordQueue:
def __init__(self, words=[]):
self._words = words
self._queue = []
self._walk_step = 0
def words(self):
return self._words
def num_words(self):
return len(self.words())
def append(self, word):
self._words.append(word)
def queue(self):
return self._queue
def queue_len(self):
return len(self.queue())
def walk(self):
return self._walk(self.words(), [])
def _walk(self, words, queue):
self._walk_step += 1
if self.walk_step() % 1000 == 0:
print '(%d, %d, %d)' % (self.walk_step(), self.num_words(),
self.queue_len())
for word in words:
if word in queue or word in self.queue():
continue
queue.append(word)
self._walk(word.trailwords(), queue)
else:
if len(queue) > self.queue_len():
self._queue = map(None, queue)
if len(queue) > 0:
queue.pop()
def walk_step(self):
return self._walk_step
if __name__ == '__main__':
q = WordQueue()
for line in sys.stdin:
for item in line.decode(ENCODING).strip().split('\t'):
if item is None or item == '':
continue
new_word = Word(item)
for word in q.words():
word.append_trailword_list(new_word)
new_word.append_trailword_list(word)
q.append(new_word)
q.walk()
for (i, w) in enumerate(q.queue()):
print '%s %s %d' % (id(w), w.word(), w.num_trailwords())
print 'number of words : %d' % q.num_words()
print 'queue length : %d' % q.queue_len()
print 'number of step : %d' % q.walk_step()
# vim : fileencoding=utf8
|
探索の無駄を省いた。 1000語の探索はT2300 (1.66GHz)で14分半くらい。 最長しりとり長は408語（多分）。「ヘルニア」で始まり「ツウブン」で終はる。
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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #!/usr/bin/python
# -*- coding: utf-8 -*-
# http://ja.doukaku.org/277/
import sys
ENCODING = 'utf8'
class Word:
def __init__(self, word):
self._word = word
self._prewords = []
self._trailwords = []
def word(self):
return self._word
def head_char(self):
return self.word()[0]
def tail_char(self):
return self.word()[-1]
def is_trailword(self, trailword):
return self.tail_char() == trailword.head_char()
def is_last_word(self):
return self.tail_char() in (u'ん', u'ン')
def append_trailword_list(self, trailword):
if not self.is_last_word() and self.is_trailword(trailword):
self.trailwords().append(trailword)
trailword.prewords().append(self)
def prewords(self):
return self._prewords
def trailwords(self):
return self._trailwords
def num_prewords(self):
return len(self.prewords())
def num_trailwords(self):
return len(self.trailwords())
class WordQueue:
def __init__(self, words=[]):
self._words = words
self._queue = []
self._walk_step = 0
def words(self):
return self._words
def num_words(self):
return len(self.words())
def append(self, word):
for w in self.words():
w.append_trailword_list(word)
word.append_trailword_list(w)
self.words().append(word)
def queue(self):
return self._queue
def queue_len(self):
return len(self.queue())
def walk(self):
self._walk(self.words(), [])
self._is_valid_queue()
self._view()
def _walk(self, words, queue):
self._walk_step += 1
if self.walk_step() % 1000 == 0:
print '(%d, %d, %d)' % (self.walk_step(), self.num_words(),
self.queue_len())
for word in words:
if word in queue:
continue
elif word in self.queue():
i = self.queue().index(word)
if len(queue) > i:
self._queue[0:i] = queue
continue
else:
queue.append(word)
self._walk(word.trailwords(), queue)
else:
if len(queue) > self.queue_len():
self._queue = map(None, queue)
if len(queue) > 0:
queue.pop()
def _is_valid_queue(self):
for word in self.queue():
if self.queue().count(word) > 1:
sys.stderr.write('%s %s is duplicated.\n' % (id(word),
word.word()))
sys.exit(1)
for i in range(0, len(self.queue()) - 1):
w = self.queue()[i]
n = self.queue()[i + 1]
if not w.is_trailword(n):
sys.stderr.write('%s %s, %s %s are not shiritori.\n'
% (id(w), w.word(), id(n), n.word()))
sys.exit(1)
def _view(self):
for w in self.queue():
print '%s\t%s\t%d\t%d' % (id(w), w.word().encode(ENCODING),
w.num_prewords(), w.num_trailwords())
def walk_step(self):
return self._walk_step
if __name__ == '__main__':
q = WordQueue()
for line in sys.stdin:
for item in line.decode(ENCODING).strip().split('\t'):
if item is not None and item != '':
q.append(Word(item))
q.walk()
print 'number of words : %d' % q.num_words()
print 'queue length : %d' % q.queue_len()
print 'number of step : %d' % q.walk_step()
# vim : fileencoding=utf8
|
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 ]