四字熟語パズルの作成
Posted feedbacks - Python
なぜ4人とも結果が違うのかがむしろ新たな問題になっちゃうかも(笑 ソースコードは公開されていますし。 とりあえず僕のコードも公開することにします。 変数dataにユニコード文字列のリストが入っています。
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 | starts = set(w[0] for w in data)
ends = set(w[3] for w in data)
from collections import defaultdict
start_dict = defaultdict(list)
end_dict = defaultdict(list)
for w in data:
start_dict[w[0]].append(w)
end_dict[w[3]].append(w)
count = 0
for s in start_dict:
starts = start_dict[s]
n = len(starts)
if n < 2: continue
for e in end_dict:
ends = end_dict[e]
if len(ends) < 2: continue
heads = [w[0] for w in ends]
for i in range(n):
w = starts[i]
tail = w[3]
if tail not in heads: continue
for j in range(i + 1, n):
w2 = starts[j]
tail2 = w2[3]
if tail == tail2: continue
if tail2 in heads:
w3 = ends[heads.index(tail)]
w4 = ends[heads.index(tail2)]
count += 1
print w
print u"%s %s" % (w2[1], w3[1])
print u"%s %s" % (w2[2], w3[2])
print w4
print
|
set()で重複を除いて、12118件の組み合わせ となりました。shift_jisコーデックだとデコード エラーになったので、cp932でデコード。
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 | import codecs
def count(words):
table = {}
for word in words:
table.setdefault(word[0], []).append(word)
ans = 0
for words in table.itervalues():
for i1 in xrange(len(words)):
for i2 in xrange(i1 + 1, len(words)):
c1 = words[i1][-1]
c2 = words[i2][-1]
if c1 == c2:
continue
for word1 in table.get(c1, []):
for word2 in table.get(c2, []):
if word1[-1] == word2[-1]:
ans += 1
return ans
def main():
words = set()
for line in codecs.open("a.txt", "r", "cp932"):
word = line.strip()
if len(word) != 4:
raise ValueError("not 4 length word: " + word)
words.add(word)
print count(words)
if __name__ == '__main__':
main()
|
ログインしてなかったので改めて投稿。
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 | import codecs
def count(words):
table = {}
for word in words:
table.setdefault(word[0], []).append(word)
ans = 0
for words in table.itervalues():
for i1 in xrange(len(words)):
for i2 in xrange(i1 + 1, len(words)):
c1 = words[i1][-1]
c2 = words[i2][-1]
if c1 == c2:
continue
for word1 in table.get(c1, []):
for word2 in table.get(c2, []):
if word1[-1] == word2[-1]:
ans += 1
return ans
def main():
words = set()
for line in codecs.open("a.txt", "r", "cp932"):
word = line.strip()
if len(word) != 4:
raise ValueError("not 4 length word: " + word)
words.add(word)
print count(words)
if __name__ == '__main__':
main()
|
27行目から31行目でフィルタ条件をコントロールします。 全部コメントで24236 27,29,31行をコメントで12118 29,31行をコメントで12109 28,30行をコメントで12107 になります。 実行時間は出力をファイルにリダイレクトして(画面出力は意外と時間を食う)20秒ほどでした。
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 | import sys
ENCODING = sys.getfilesystemencoding()
l = []
h = {}
t = {}
for s in dict.fromkeys((sys.stdin if len(sys.argv) < 2 else file(sys.argv[1])).readlines()).keys():
s = unicode(s.rstrip(), ENCODING)
l.append(s)
if s[0] not in h:
h[s[0]] = []
h[s[0]].append(s)
if s[-1] not in t:
t[s[-1]] = []
t[s[-1]].append(s)
r = {}
for a in l:
if (a[0] in h) and (a[3] in h):
for b in h[a[0]]:
if b[3] in h:
if a[3] == b[3]: continue
for c in h[a[3]]:
if c[3] in t:
for d in set(h[b[3]]).intersection(t[c[3]]):
if len(set([a, b, c, d])) < 4: continue
if ((a, b, c, d) in r) or ((b, a, d, c) in r): continue
# if tuple(sorted([a, b, c, d])) in r: continue
r[(a, b, c, d)] = 1
# r[tuple(sorted([a, b, c, d]))] = 1
print ('%s,%s,%s,%s'%(a, b, c, d)).encode(ENCODING)
# print ('%s\n%s %s\n%s %s\n%s\n'%(a, b[1], c[1], b[2], c[2], d)).encode(ENCODING)
|
にしお
#3644()
Rating-1/1=-1.00
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
[ reply ]