四字熟語パズルの作成
Posted feedbacks - JavaScript
matyr
#3680()
[
JavaScript
]
100秒程(@Turion64x2 1.8GHz)かかって，8312件 → 24236通り。
「可能な四角を全て出力」と解釈して鏡像・重複共に許したため，他の人の約二倍量になりました。
「可能な四角を全て出力」と解釈して鏡像・重複共に許したため，他の人の約二倍量になりました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | function doukaku75(y){
for(var h = {}, i = y.length, c; i--;)
(h[c = y[i].charAt(0)] || (h[c] = {}))[i] = y[i].charAt(3);
var o = [], s = ' ', n = '\n', t, l, r, b, tl, tr, bl, htl, htr, hbl;
for(tl in h) for(t in htl = h[tl]) for(l in htl) if((tr = htl[t]) != (bl = htl[l])) // 右上隅 != 左下隅
for(r in htr = h[tr]) for(b in hbl = h[bl]) if(htr[r] == hbl[b])
o[++i] = [y[t], n,
y[l].charAt(1), s, y[r].charAt(1), n,
y[l].charAt(2), s, y[r].charAt(2), n,
y[b]].join('');
return o;
}
with(WSH.stdIn) for(var lst = [], i = 0; !atEndOfStream;) lst[i++] = readLine();
var start = new Date, result = doukaku75(lst);
WSH.echo(result.length, (new Date - start) +'[ms]\n\n'+ result.join('\n\n'));
|
matyr
#3703()
[
JavaScript
]
ruckerさんのアルゴリズム(#3695)を拝借して高速化を図りました。上と同条件で約9秒。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function doukaku75r(y){
for(var C = {}, i = y.length, c, h, t; i--;){
h = y[i].charAt(0), t = y[i].charAt(3);
((c = (C[h] || (C[h] = {}))).asHead || (c.asHead = {}))[y[i]] = t;
((c = (C[t] || (C[t] = {}))).asTail || (c.asTail = {}))[y[i]] = h;
}
var CC = {}, cc, f, r;
for(c in C) if((h = C[c].asHead) && (t = C[c].asTail)) for(r in h) for(f in t)
(CC[cc = t[f] + h[r]] || (CC[cc] = [])).push({hitch: c, front: f, rear: r});
var out = [], s = ' ', n = '\n', x1, x2, c1, c2;
for(cc in CC) for(x1 in C = CC[cc]) for(x2 in C) if((c1 = C[x1]).hitch != (c2 = C[x2]).hitch)
out[++i] = [c1.front, n,
c2.front.charAt(1), s, c1.rear.charAt(1), n,
c2.front.charAt(2), s, c1.rear.charAt(2), n,
c2.rear].join('');
return out;
}
|
にしお
#3644()
Rating-1/1=-1.00
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
[ reply ]