四字熟語パズルの作成
Posted feedbacks - PHP
先頭の文字をキーとした配列、最後の文字をキーとした配列にふりわけな がら重複をはじく。それを組み合わせで繋いで今度は一つめの単語の最初 の文字と二つ目の単語の最後の文字を繋いでキーとして分類、同じキーの 中で組み合わせで出力。 12118件出力 Core2Duo 1.2GHz で 0.70秒
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 | <?php
$t=microtime(true);
$a=array();
while(($str=fgets(STDIN))!==false)
{ if(mb_strlen($str=trim($str))==4)
{ $a[mb_substr($str,-1)][0][$str]=1;
$a[mb_substr($str,0,1)][1][$str]=1;
}
}
$b=array();
foreach($a as $v)
{ if(count($v)==2)
{ foreach($v[0] as $k1=>$v1)
{ foreach($v[1] as $k2=>$v2)
$b[mb_substr($k1,0,1).mb_substr($k2,-1)][]=array($k1,$k2);
}
}
}
foreach($b as $v)
{ while(count($v)>1)
{ $w1=array_pop($v);
foreach($v as $w2)
{ if(mb_substr($w1[1],0,1)!=mb_substr($w2[1],0,1))
echo "${w1[0]},${w1[1]},${w2[0]},${w2[1]}\n";
}
}
}
fwrite(STDERR,(microtime(true)-$t)."sec\n");
?>
|
にしお
#3644()
Rating-1/1=-1.00
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
[ reply ]