DouKaku? 3680 matyr: 100秒程(@Turion64x2 1...(四字熟語パズルの作成)

Comment detail

100秒程(@Turion64x2 1.8GHz)かかって，8312件 → 24236通り。
「可能な四角を全て出力」と解釈して鏡像・重複共に許したため，他の人の約二倍量になりました。

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'));

ruckerさんのアルゴリズム(#3695)を拝借して高速化を図りました。上と同条件で約9秒。

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;
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq