四字熟語パズルの作成
Posted feedbacks - Nested
Flatten Hiddenそれなりに効率化を図ったつもり。 サンプルデータ 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))))
|
データは words.txt というファイルの中に入っていて、 改行で区切られていると仮定しています。
Squeak Smalltalk で。
四字熟語のデータは、熟語ごとに行を改めた Unicode のテキストファイル(in.txt)で与えられているとします。
#groupBy:having: は、レシーバ(コレクション)に対し、まず第一引数のブロックで指定した条件(キー)にもとづいて要素を括りだした後、各グループについてあらためて第二引数で与えたブロックの条件に合致するかをチェックし、当てはまるものだけを集めて返すメソッドです。
結果として得られた四個の組の要素に重複がないことは組をセットにしてその要素を数えること(quartet asSet size = 4)で、また、右上隅と左下隅の文字が異なることは、最初の熟語の最後の文字と、最後の熟語の最初の文字が一致しないこと(quartet first last ~= quartet last first)でチェックしています。
お題の例と同じデータを使っているはずなのですが、出力件数は 11712 でした。熟語四組の抽出には、1.0 GHz PowerPC (Mac OS X 10.4.10) で 14 秒弱ほどかかりました(ただし、入出力時間は含まず)。
四字熟語のデータは、熟語ごとに行を改めた Unicode のテキストファイル(in.txt)で与えられているとします。
#groupBy:having: は、レシーバ(コレクション)に対し、まず第一引数のブロックで指定した条件(キー)にもとづいて要素を括りだした後、各グループについてあらためて第二引数で与えたブロックの条件に合致するかをチェックし、当てはまるものだけを集めて返すメソッドです。
結果として得られた四個の組の要素に重複がないことは組をセットにしてその要素を数えること(quartet asSet size = 4)で、また、右上隅と左下隅の文字が異なることは、最初の熟語の最後の文字と、最後の熟語の最初の文字が一致しないこと(quartet first last ~= quartet last first)でチェックしています。
お題の例と同じデータを使っているはずなのですが、出力件数は 11712 でした。熟語四組の抽出には、1.0 GHz PowerPC (Mac OS X 10.4.10) で 14 秒弱ほどかかりました(ただし、入出力時間は含まず)。
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 38 39 40 | | in yojis yoji firstCharDict pairs bothCharsDict results out timeToRun |
in := FileStream fileNamed: 'in.txt'.
yojis := OrderedCollection new.
[(yoji := in nextLine) notNil] whileTrue: [yojis add: yoji].
in close.
timeToRun := [
firstCharDict := yojis
groupBy: [:each | each first]
having: [:group | group size > 1].
pairs := OrderedCollection new.
yojis do: [:first |
firstCharDict at: first last ifPresent: [:found |
found do: [:second | pairs add: {first. second}]]].
bothCharsDict := pairs
groupBy: [:pair | {pair first first. pair second last}]
having: [:group | group size > 1].
results := OrderedCollection new.
bothCharsDict do: [:val | val combinations: 2 atATimeDo: [:pair |
| quartet |
quartet := pair first, pair second.
(quartet asSet size = 4 and: [quartet first last ~= quartet last first])
ifTrue: [results add: quartet]]]
] timeToRun.
out := FileStream fileNamed: 'out.txt'.
results do: [:quartet |
out nextPutAll: quartet first; cr.
(2 to: 3) do: [:idx |
out nextPut: (quartet third at: idx).
out nextPutAll: ' '.
out nextPut: (quartet second at: idx); cr].
out nextPutAll: quartet last; cr; cr].
out edit.
^{results size. timeToRun} "=> #(11712 13835) "
|
数が食い違う原因はまだ分からないのですが、とりあえずひとつ明らかなバグが見つかったので修正。結果、少し増えて 12109 件でした。多数派の数にちょっと近づいたか?(^_^;)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | @@ -8,7 +8,7 @@
timeToRun := [
firstCharDict := yojis
groupBy: [:each | each first]
- having: [:group | group size > 1].
+ having: [:group | true].
pairs := OrderedCollection new.
yojis do: [:first |
@@ -37,4 +37,4 @@
out nextPutAll: quartet last; cr; cr].
out edit.
-^{results size. timeToRun} "=> #(11712 13835) "
+^{results size. timeToRun} "=> #(12109 13792) "
|
Unicode の扱いが分かる言語が Python だけだったので にしおさんの結果と差分をとってみたところ、にしおさんのにあって私のになかったのは次の7個でした。
#('一切即一' '一期四相' '一期四相' '相門有相')
#('一場春夢' '夢中説夢' '一切即一' '一場春夢')
#('一念通天' '天下第一' '一切即一' '一切即一')
#('一了百当' '当代第一' '一切即一' '一切即一')
#('一期一会' '会三帰一' '一切即一' '一切即一')
#('一文不知' '知行合一' '一切即一' '一切即一')
#('一読三嘆' '嘆息嗟嘆' '一切即一' '一読三嘆')
とりあえずこれらについては、私のほうではセットを使って重複を外す手続きをしているのでその関係かと思われます。
これと別に、同じ組み合わせでも順序が違うときに省くかどうかという判断も影響しそうです。
#('一切即一' '一期四相' '一期四相' '相門有相')
#('一場春夢' '夢中説夢' '一切即一' '一場春夢')
#('一念通天' '天下第一' '一切即一' '一切即一')
#('一了百当' '当代第一' '一切即一' '一切即一')
#('一期一会' '会三帰一' '一切即一' '一切即一')
#('一文不知' '知行合一' '一切即一' '一切即一')
#('一読三嘆' '嘆息嗟嘆' '一切即一' '一読三嘆')
とりあえずこれらについては、私のほうではセットを使って重複を外す手続きをしているのでその関係かと思われます。
これと別に、同じ組み合わせでも順序が違うときに省くかどうかという判断も影響しそうです。
ocean さんの Python 版 12118 個と比較したところ、先の 7 個に加えて次の2点が私のでははじかれていました。やはり、4組のうちの重複要素の扱いに起因する違いのようです。
#('一唱三嘆' '嘆息嗟嘆' '一切即一' '一唱三嘆')
#('一切即一' '一炊之夢' '一炊之夢' '夢中説夢')
あと、以下の並びの異なる2セットをそれぞれ区別するかで 12109 と 12107 の差が出ることも分かりました。
#('一切即一' '一読三嘆' '一唱三嘆' '嘆息嗟嘆')
#('一切即一' '一唱三嘆' '一読三嘆' '嘆息嗟嘆')
#('一炊之夢' '夢中説夢' '一切即一' '一場春夢')
#('一場春夢' '夢中説夢' '一切即一' '一炊之夢')
#('一唱三嘆' '嘆息嗟嘆' '一切即一' '一唱三嘆')
#('一切即一' '一炊之夢' '一炊之夢' '夢中説夢')
あと、以下の並びの異なる2セットをそれぞれ区別するかで 12109 と 12107 の差が出ることも分かりました。
#('一切即一' '一読三嘆' '一唱三嘆' '嘆息嗟嘆')
#('一切即一' '一唱三嘆' '一読三嘆' '嘆息嗟嘆')
#('一炊之夢' '夢中説夢' '一切即一' '一場春夢')
#('一場春夢' '夢中説夢' '一切即一' '一炊之夢')
サンプルデータ(8312件),CPU1.8GHz,3秒で14,456件出力されました。
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 | def jukugo(f)
r, ht, a, h, t = {}, {}, {}, {}, {}
open(f) {|fin|
cnt = 0
while line = fin.gets
a[cnt] = line
h[line[0..1]] = [] if not h[line[0..1]]
h[line[0..1]] << cnt #--- head
t[cnt] = line[6..7] #--- tail
cnt+=1
end
}
t.each{|c,i|
next if not h[i]
hh = a[c][0..1]
h[i].each{|k|
tt = a[k][6..7]
next if hh == tt
hhtt = hh+tt
ht[hhtt] = [] if not ht[hhtt]
ht[hhtt].each {|m|
mm = [a[m[0]], a[m[1]], a[c], a[k]].flatten.sort
r[sprintf("%s\n",mm)] = true if mm.uniq.size == 4
}
ht[hhtt] << [c, k]
}
}
r.each {|i|puts i}
end
jukugo(ARGV[0])
|
なぜ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
|
僕のコードも30~31行目あたり手抜きなので もう一度きちんと考える必要がありそうだ…
コマンドライン引数に、四字熟語を改行で区切って列挙したファイルのパスを指定したものとします。ファイルのパスは複数指定可です。文字コードはUnicodeです。
出力例に含まれる四字熟語を列挙したファイルでは一瞬で例と同じ出力結果が得られました。
今、ダウンロードしたサンプルを上記形式に加工したファイルを読み込ませて実行しているのですが、待てど暮らせど終わりません。もう1時間程経ってます。
VB.net一番乗り狙って投稿します。
出力例に含まれる四字熟語を列挙したファイルでは一瞬で例と同じ出力結果が得られました。
今、ダウンロードしたサンプルを上記形式に加工したファイルを読み込ませて実行しているのですが、待てど暮らせど終わりません。もう1時間程経ってます。
VB.net一番乗り狙って投稿します。
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | Module Module1
Sub Main(ByVal args() As String) '引数に四字熟語をCRLFで区切り列挙したテキストファイルを指定。文字コードはUnicode。ファイルは複数指定可能。
Dim Ticks As Long = Now.Ticks
Dim JukugoList As New List(Of String) '四字熟語のリスト
'四字熟語リストの読み込みループ
For Each CmdLine As String In args
JukugoList.AddRange(System.IO.File.ReadAllLines(CmdLine))
Next
JukugoPuzul(JukugoList)
Console.WriteLine(Now.Ticks - Ticks)
Console.ReadKey()
End Sub
Private Sub JukugoPuzul(ByVal JukugoList As List(Of String))
Dim Kouho As New List(Of String())
For Each JukugoTop As String In JukugoList '上
For Each JukugoRight As String In JukugoList '右
For Each JukugoBottom As String In JukugoList '下
For Each JukugoLeft As String In JukugoList '左
If JukugoTop.Substring(3, 1) = JukugoRight.Substring(0, 1) AndAlso _
JukugoRight.Substring(3, 1) = JukugoBottom.Substring(3, 1) AndAlso _
JukugoBottom.Substring(0, 1) = JukugoLeft.Substring(3, 1) AndAlso _
JukugoLeft.Substring(0, 1) = JukugoTop.Substring(0, 1) Then
If JukugoTop.Substring(3, 1) <> JukugoBottom.Substring(0, 1) Then '右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
Dim Group() As String = {JukugoTop, JukugoRight, JukugoBottom, JukugoLeft}
If ChofukuCheck(Kouho, Group) Then
OutPut(Group)
Kouho.Add(Group)
End If
End If
End If
Next
Next
Next
Next
End Sub
Private Function ChofukuCheck(ByVal List As List(Of String()), ByVal Kouho As String()) As Boolean
For Each Group As String() In List
Dim Count As Integer = 0
For Each Jukugo As String In Group
For Each Jukugo1 As String In Kouho
If Jukugo = Jukugo1 Then
Count += 1
End If
Next
Next
If Count = 4 Then
Return False
End If
Next
Return True
End Function
Private Sub OutPut(ByVal Group() As String)
Console.WriteLine(Group(0))
Console.WriteLine(Group(3).Substring(1, 1) & " " & Group(1).Substring(1, 1))
Console.WriteLine(Group(3).Substring(2, 1) & " " & Group(1).Substring(2, 1))
Console.WriteLine(Group(2) & vbCrLf)
End Sub
End Module
|
やっぱりガチムチにFor Eachの4重ネストで総当り判定してるのが遅い原因でしょうか…。 まだ終わりません…。CPUは2GHz、デバッグモードで実行してます。
高速化しました。
サンプル(重複あり)8,582件
結果12,117件
CPU2.0GHz 610秒orz
サンプル(重複あり)8,582件
結果12,117件
CPU2.0GHz 610秒orz
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | Module Module1
Sub Main(ByVal args() As String) '引数に四字熟語をCRLFで区切り列挙したテキストファイルを指定。文字コードはUnicode。ファイルは複数指定可能。
Dim Ticks As Long = Now.Ticks
Dim JukugoList As New List(Of String) '四字熟語のリスト
'四字熟語リストの読み込みループ
For Each CmdLine As String In args
JukugoList.AddRange(System.IO.File.ReadAllLines(CmdLine))
Next
JukugoPuzul(JukugoList)
Console.WriteLine((Now.Ticks - Ticks) / 10000000L & "秒")
Console.ReadKey()
End Sub
Private Sub JukugoPuzul(ByVal JukugoList As List(Of String))
Dim Kouho As New List(Of String())
For Each JukugoTop As String In JukugoList '上
Dim Top() As Char = JukugoTop.ToCharArray
For Each JukugoRight As String In JukugoList '右
Dim Right() As Char = JukugoRight.ToCharArray
If Top(3) = Right(0) Then
For Each JukugoBottom As String In JukugoList '下
Dim Bottom() As Char = JukugoBottom.ToCharArray
If Right(3) = Bottom(3) Then
For Each JukugoLeft As String In JukugoList '左
Dim Left() As Char = JukugoLeft.ToCharArray
If Bottom(0) = Left(3) AndAlso _
Left(0) = Top(0) Then
If Top(3) <> Bottom(0) Then '右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
Dim Group() As String = {JukugoTop, JukugoRight, JukugoBottom, JukugoLeft}
If ChofukuCheck(Kouho, Group) Then
OutPut(Group)
Kouho.Add(Group)
End If
End If
End If
Next
End If
Next
End If
Next
Next
Console.WriteLine(Kouho.Count & "組の組み合わせがありました。")
End Sub
Private Function ChofukuCheck(ByVal List As List(Of String()), ByVal Kouho As String()) As Boolean
For Each Group As String() In List
Dim Count As Integer = 0
For Each Jukugo As String In Group
For Each Jukugo1 As String In Kouho
If Jukugo = Jukugo1 Then
Count += 1
End If
Next
Next
If Count = 4 Then
Return False
End If
Next
Return True
End Function
Private Sub OutPut(ByVal Group() As String)
Console.WriteLine(Group(0))
Console.WriteLine(Group(3).Substring(1, 1) & " " & Group(1).Substring(1, 1))
Console.WriteLine(Group(3).Substring(2, 1) & " " & Group(1).Substring(2, 1))
Console.WriteLine(Group(2) & vbCrLf)
End Sub
End Module
|
重複無しの8312件を食わせて走らせてみました。
OS:Windows XP Home SP2
CPU:AMD Sempron 3400+ 1.99GHz
メモリ:480MB
処理時間:507.078125秒
件数:12117件
組み合わせた後に重複チェックをしているので、元データの重複は件数に影響しないようです。
僕は
>四角く配置することのできる熟語の組み合わせを探すプログラム
と言うところに着目して、同じ熟語の組み合わせなら、四角に組む順番が違っても同一の組み合わせと判断して結果から除いています。
もっと厳密に定義をすれば件数が揃うんじゃないでしょうか。
それよりも、この桁違いの遅さは何なんでしょうorz .NETだからって極端に遅いって事も無いと思うのですが…。
OS:Windows XP Home SP2
CPU:AMD Sempron 3400+ 1.99GHz
メモリ:480MB
処理時間:507.078125秒
件数:12117件
組み合わせた後に重複チェックをしているので、元データの重複は件数に影響しないようです。
僕は
>四角く配置することのできる熟語の組み合わせを探すプログラム
と言うところに着目して、同じ熟語の組み合わせなら、四角に組む順番が違っても同一の組み合わせと判断して結果から除いています。
もっと厳密に定義をすれば件数が揃うんじゃないでしょうか。
それよりも、この桁違いの遅さは何なんでしょうorz .NETだからって極端に遅いって事も無いと思うのですが…。
同じアルゴリズムでJavaでも書いてみました。更に遅くなりました。コード晒すの恥ずかしくなってきました…。
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | import java.io.*;
import java.util.*;
class YojijukugoPuzul{
public static void main(String args[]){
long start = System.currentTimeMillis();
ArrayList<String[]> ans = new ArrayList<String[]>();
ArrayList<String> jukugoList = new ArrayList<String>();
//読み込み
try{
BufferedReader br = new BufferedReader(new FileReader(args[0]));
while(true){
String str;
if((str = br.readLine()) == null) break;
else jukugoList.add(str);
}
br.close();
}catch(IOException err){System.out.println(err);}
//組み合わせ探索
for(String top : jukugoList){ //top
for(String right : jukugoList){ //right
if(top.charAt(3) == right.charAt(0)){
for(String bottom : jukugoList){ //bottom
if((right.charAt(3) == bottom.charAt(3)) && (top.charAt(3) != bottom.charAt(0))){
for(String left : jukugoList){ //left
if((bottom.charAt(0) == left.charAt(3)) && (left.charAt(0) == top.charAt(0))){
String[] check = new String[]{top,right,bottom,left};
if( !isChofuku(check,ans) ){
ans.add(check);
//出力
System.out.println(check[0]);
System.out.println(check[3].substring(1,2) + " " + check[1].substring(1,2));
System.out.println(check[3].substring(2,3) + " " + check[1].substring(2,3));
System.out.println(check[2]);
System.out.println();
}
}
}
}
}
}
}
}
//出力
System.out.println(ans.size());
long end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
}
//組み合わせの重複をチェック
public static Boolean isChofuku(String[] check , ArrayList<String[]> ans){
for(String[] str : ans){
int count = 0;
for(String str_ : check){
for(String str__ : str){
if(str__.equalsIgnoreCase(str_)){
count++;
}
}
}
if(count == 4){
return true;
}
}
return false;
}
}
|
12107件でした。kozimaさんと近いですね。 Athlon64 3000,メモリ1G,WinXPで出力含め15秒ほどでした。 ちなみに、Scalaのforはモナドのための記法として扱えます。 HashMap#getはOptionといういわゆるMaybeモナドですのでシンプルに書けます。
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 | import scala.io.Source.fromFile
import scala.collection.mutable.{HashMap,LinkedHashSet}
object JukugoPazzule {
type S = LinkedHashSet[String]
val jukugos = fromFile("kanji_uniq.txt").getLines.toList
val headMap = (new HashMap[Char, S]() /: jukugos){(map, jukugo) =>
map.getOrElseUpdate(jukugo(0), new S) += jukugo; map
}
def solve = {
var i = 0
var uniqChekMap = new S
for(j1 <- jukugos;
jlst2 <- headMap.get(j1(0));
j2 <- jlst2 if j2 != j1;
jlst3 <- headMap.get(j1(3));
j3 <- jlst3 if j3!=j2 && j3!=j1 && j1(3)!=j2(3);
jlst4 <- headMap.get(j2(3));
j4 <- jlst4 if j4!=j3 && j4!=j2 && j4!=j1 && j4(3)==j3(3)
) {
var all = List(j1,j2,j3,j4).sort(_<_).mkString("")
if(!uniqChekMap.contains(all)) {
print(j1)
(1 to 2).foreach{i => println(j2(i)+" "+j3(i))}
println(j4)
println("-----------------------")
i = i+1
uniqChekMap += all
}
}
println(i)
}
}
JukugoPazzule.solve
|
熟語データはeuc-jpのin.txt Celeron2.4GHzで8.6秒ほどかかって12118件でした。 40行目は鏡像のチェックです
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #!/usr/local/bin/perl
use strict;
use warnings;
use encoding 'euc-jp';
open( my $file, "<:encoding(euc-jp)", "in.txt" ) or die;
my @words;
my %left_right_list; #1文字目をキーにしたテーブル
my %bottom_list; #1,4文字目をキーにしたテーブル
for my $word (<$file>)
{
chomp $word;
push @words, $word;
my ( $char_0, $char_3 ) = ( split //, $word )[ 0, 3 ];
push @{ $left_right_list{$char_0} }, $word;
push @{ $bottom_list{"$char_0$char_3"} }, $word;
}
close $file;
my $counter;
my %seen;
for my $top (@words)
{
my ( $top_char_0, $top_char_3 ) = ( split //, $top )[ 0, 3 ];
for my $left ( @{ $left_right_list{$top_char_0} } )
{
next if $top eq $left;
my $left_char_3 = substr $left, 3, 1;
next if $top_char_3 eq $left_char_3;
for my $right ( @{ $left_right_list{$top_char_3} } )
{
my $right_char_3 = substr $right, 3, 1;
for my $bottom ( @{ $bottom_list{"$left_char_3$right_char_3"} } )
{
next if $seen{"$left$top$bottom$right"};
$seen{"$top$left$right$bottom"} = 1;
print "$top $left $right $bottom\n";
print substr( $left, 1, 1 ), " ", " ", substr( $right, 1, 1 ), "\n";
print substr( $left, 2, 1 ), " ", " ", substr( $right, 2, 1 ), "\n";
print "$bottom\n";
print "--------\n";
$counter++;
}
}
}
}
print "$counter\n";
|
重複がありますね。 雲竜風虎 雲蒸竜変 変成男子 虎穴虎子 などは4回, 千秋万歳 千秋万古 古琴之友 歳寒三友 などは8回重複しています。 これらをそれぞれ1回と数えれば, 12118 個のようです。
これは私の#3669に対してでしょうか?手元でもう一度処理してみましたが、重複は出ませんでした。 #書いていませんでしたが元データは重複を排除してある物を前提にしていたので、そのせいでしょうか?
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()
|
重複なしの8312単語,utf-8 でソートしたもの 9080個の解が見つかったというのだが(少ない?) 1.33GH PowerPC G4 > system.time(foo()) 1 1 180 一上一下 一期四相 相利共生 下化衆生 2 1 300 一上一下 一貧一富 富貴利達 下学上達 3 2 175 一世一度 一朝之忿 忿忿之心 度衆生心 4 2 245 一世一度 一筆啓上 上下一心 度衆生心 5 2 268 一世一度 一草一木 木人石心 度衆生心 6 4 21 一世之雄 一入再入 入室升堂 雄気堂堂 途中省略 071 8153 8158 鬼手仏心 鬼面仏心 心煩意乱 心狂意乱 9072 8153 8158 鬼手仏心 鬼面仏心 心融神会 心領意会 9073 8153 8158 鬼手仏心 鬼面仏心 心融神会 心領神会 9074 8153 8158 鬼手仏心 鬼面仏心 心領意会 心領神会 9075 8153 8159 鬼手仏心 鬼面嚇人 人人具足 心満意足 9076 8157 8158 鬼臉嚇人 鬼面仏心 心満意足 人給家足 9077 8157 8159 鬼臉嚇人 鬼面嚇人 人人具足 人




にしお
#3644()
Rating-1/1=-1.00
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
[ reply ]