四字熟語パズルの作成
Posted feedbacks - Common Lisp
kozima
#3658()
[
Common Lisp
]
それなりに効率化を図ったつもり。 サンプルデータ 8312 件を 2.66 GHz の CPU で 3.5 秒でした。 出力が 12118 件で問題文と一致しませんが、 特におかしな結果は見当たりませんでした。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | (defun group (list key &optional (test #'eql))
(let ((tbl (make-hash-table :test test)))
(dolist (x list) (push x (gethash (funcall key x) tbl)))
tbl))
(defun make-puzzle (words)
(let ((tbl1 (group words (lambda (s) (elt s 0)))))
(loop for grp1 being each hash-value of tbl1 nconc
(loop for a in grp1 and rest1 on (cdr grp1) nconc
(loop for b in rest1
if (char/= (elt a 3) (elt b 3)) nconc
(loop for c in (gethash (elt a 3) tbl1) nconc
(loop for d in (gethash (elt b 3) tbl1)
if (char= (elt c 3) (elt d 3))
collect (list a b c d))))))))
;;; test
(compile 'make-puzzle)
(let ((words (with-open-file (s "words.txt" :direction :input)
(loop for x = (read-line s nil) while x collect x))))
(print (time (make-puzzle words))))
|
にしお
#3644()
Rating-1/1=-1.00
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
[ reply ]