四字熟語パズルの作成 in Java DouKaku?

四字熟語パズルの作成

与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。

出力例:

無憂無風
礼　　林
千　　火
万水千山

知行合一
者　　筆
不　　勾
言語道断

四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。

四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。

問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。

post comment

Posted feedbacks - Java

四字熟語のリストは標準入力から１行１エントリの形式で与えます。
出題で参考に与えられたリストを重複排除したもの(8312個)を使用したところ、12118個の組み合わせが見つかりました（単純に縦横を入れ替えて同じになるのは除外しています）。例として「阿」で始まる組み合わせを示します。

阿衡之才阿付雷同才子佳人同行二人
阿衡之才阿附迎合才弁縦横合従連横
阿衡之才阿諛迎合才弁縦横合従連横
阿衡之才阿諛苟合才弁縦横合従連横
阿付雷同阿諛追随同心同徳随喜功徳
阿爺下頷阿諛追随頷下之珠随侯之珠
阿諛取容阿諛奉承容貌顔色承顔候色

上記データの場合、1.67 GHz PowerPC G4 で 10秒程度かかりました。

import java.util.*;
import java.io.*;

public class Sample {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String> jukugoList = new ArrayList<String>();
        LinkedHashMap<Integer, List<String>> startMap = new LinkedHashMap<Integer, List<String>>();
        String jukugo;
        while ((jukugo = r.readLine()) != null) {
            jukugoList.add(jukugo);
            int i = jukugo.codePointAt(0);
            List<String> il = startMap.get(i);
            if (il == null) {
                il = new ArrayList<String>();
                startMap.put(i, il);
            }
            il.add(jukugo);
        }
        for (Map.Entry<Integer, List<String>> e : startMap.entrySet()) {
            List<String> jL = e.getValue();
            for (int i1 = 0; i1 < jL.size(); i1++) {
                String j1 = jL.get(i1);
                int j1Last = j1.codePointBefore(j1.length());
                for (int i2 = i1 + 1; i2 < jL.size(); i2++) {
                    String j2 = jL.get(i2);
                    int j2Last = j2.codePointBefore(j2.length());
                    if (j1Last != j2Last && startMap.get(j1Last) != null && startMap.get(j2Last) != null) {
                        for (String j3 : startMap.get(j1Last)) {
                            for (String j4: startMap.get(j2Last)) {
                                if (j3.codePointBefore(j3.length()) == j4.codePointBefore(j4.length())) {
                                    print(j1, j2, j3, j4);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    public static void print(String j1, String j2, String j3, String j4) {
        System.out.println(j1);
        System.out.println(j2.replaceAll(".(.).*", "$1") + "    " + j3.replaceAll(".(.).*", "$1"));
        System.out.println(j2.replaceAll("..(.).*", "$1") + "    " + j3.replaceAll("..(.).*", "$1"));
        System.out.println(j4);
        System.out.println();
    }
}

最後の2つの熟語を単純に総当たりで調べていたのが若干気になったので、もう少し工夫してみました。先頭の文字と末尾の文字の両方から直接最後の熟語を求めています。

先ほどと同じ条件で7秒まで短縮しました。

ちなみに、最初に提示したプログラムを含めサロゲートペアに対応しています。

import java.util.*;
import java.io.*;

public class Sample3 {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        LinkedHashMap<Integer, List<String>> startMap = new LinkedHashMap<Integer, List<String>>();
        Map<Long, List<String>> startEndMap = new HashMap<Long, List<String>>();
        String jukugo;
        while ((jukugo = r.readLine()) != null) {
            int i = jukugo.codePointAt(0);
            List<String> il = startMap.get(i);
            if (il == null) {
                il = new ArrayList<String>();
                startMap.put(i, il);
            }
            il.add(jukugo);
            long l = ((long)i << 32) + jukugo.codePointBefore(jukugo.length());
            List <String> ll = startEndMap.get(l);
            if (ll == null) {
                ll = new ArrayList<String>();
                startEndMap.put(l, ll);
            }
            ll.add(jukugo);
        }
        for (Map.Entry<Integer, List<String>> e : startMap.entrySet()) {
            List<String> jL = e.getValue();
            for (int i1 = 0; i1 < jL.size(); i1++) {
                String j1 = jL.get(i1);
                int j1Last = j1.codePointBefore(j1.length());
                for (int i2 = i1 + 1; i2 < jL.size(); i2++) {
                    String j2 = jL.get(i2);
                    int j2Last = j2.codePointBefore(j2.length());
                    if (j1Last != j2Last && startMap.get(j1Last) != null && startMap.get(j2Last) != null) {
                        for (String j3 : startMap.get(j1Last)) {
                            long l = ((long)j2Last << 32) + j3.codePointBefore(j3.length());
                            List<String> l4 = startEndMap.get(l);
                            if (l4 != null) {
                                for (String j4: l4) {
                                    print(j1, j2, j3, j4);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    public static void print(String j1, String j2, String j3, String j4) {
        System.out.println(j1);
        System.out.println(j2.replaceAll(".(.).*", "$1") + "    " + j3.replaceAll(".(.).*", "$1"));
        System.out.println(j2.replaceAll("..(.).*", "$1") + "    " + j3.replaceAll("..(.).*", "$1"));
        System.out.println(j4);
        System.out.println();
    }
}

四隅の漢字を求めてから、中間の熟語をはめ込めば効率的ではないかという発想から改造してみました。組み合わせの数は同じですが生成される順番は変わっています。

ちなみに、先ほどの測定結果は全て裏で重いプロセスが走ったままで測定していましたので、計り直しました（4回測定して最速のもの）。

#3687 3.56秒
#3688 2.36秒
本コメント 2.40秒

最適化が充分でなかったようで、わずかですが却って遅くなってしまいました（それでも、最初よりは早いです）。

import java.util.*;
import java.io.*;

public class Sample4 {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        LinkedHashMap<Integer, Set<Integer>> startMap = new LinkedHashMap<Integer, Set<Integer>>();
        Map<Long, List<String>> startEndMap = new HashMap<Long, List<String>>();
        String jukugo;
        while ((jukugo = r.readLine()) != null) {
            int i = jukugo.codePointAt(0);
            int j = jukugo.codePointBefore(jukugo.length());
            Set<Integer> il = startMap.get(i);
            if (il == null) {
                il = new TreeSet<Integer>();
                startMap.put(i, il);
            }
            il.add(j);
            long l = ((long)i << 32) + j;
            List <String> ll = startEndMap.get(l);
            if (ll == null) {
                ll = new ArrayList<String>();
                startEndMap.put(l, ll);
            }
            ll.add(jukugo);
        }
        for (Map.Entry<Integer, Set<Integer>> e : startMap.entrySet()) {
            int j0 = e.getKey();
            List<Integer> jL = new ArrayList<Integer>(e.getValue());
            for (int i1 = 0; i1 < jL.size(); i1++) {
                int j1 = jL.get(i1);
                List<String> l1 = startEndMap.get(((long)j0<<32) + j1);
                for (int i2 = i1 + 1; i2 < jL.size(); i2++) {
                    int j2 = jL.get(i2);
                    List<String> l2 = startEndMap.get(((long)j0<<32) + j2);
                    Set<Integer> s = startMap.get(j1);
                    Set<Integer> s2 = startMap.get(j2);
                    if (s != null && s2 != null) {
                        s = new TreeSet<Integer>(s);
                        s.retainAll(s2);
                        for (int j3 : s) {
                            List<String> l3 = startEndMap.get(((long)j1<<32) + j3);
                            List<String> l4 = startEndMap.get(((long)j2<<32) + j3);
                            for (String jk1 : l1) {
                                for (String jk2 : l2) {
                                    for (String jk3 : l3) {
                                        for (String jk4 : l4) {
                                            print(jk1, jk2, jk3, jk4);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    public static void print(String j1, String j2, String j3, String j4) {
        System.out.println(j1);
        System.out.println(j2.replaceAll(".(.).*", "$1") + "    " + j3.replaceAll(".(.).*", "$1"));
        System.out.println(j2.replaceAll("..(.).*", "$1") + "    " + j3.replaceAll("..(.).*", "$1"));
        System.out.println(j4);
        System.out.println();
    }
}

初投稿です。
四字熟語の異音による重複を排除してから処理を行っています。
処理結果は12116組の検出でした。（処理時間：5156ms、環境：Pen4 2.4GHz）
※組み合わせの検出を行っているため、処理結果は回転や入れ替えによる重複は単純に排除してあります。

package nt.doukaku;

import java.io.*;
import java.util.*;

public class Jukugo {
    private static List<String> words;
    private static List<String> headChars;
    private static HashMap<String, Integer> headMap;
    
    public static void main(String[] args) throws Exception {
//        long start = System.currentTimeMillis();
        init();
        HashMap<String, Integer[]> map = new HashMap<String, Integer[]>();
        int top = 0;
        for (String word : words) {
            String upperRight = word.substring(word.length() - 1);
            List<Integer> lefts = findChars(headChars.get(top));
            List<Integer> rights = findChars(upperRight);
            for (Integer left : lefts) {
                String lowerLeft =
                    words.get(left).substring(words.get(left).length() - 1);
                if (upperRight.equals(lowerLeft)) continue;
                List<Integer> bottoms = findChars(lowerLeft);
                for (Integer right : rights) {
                    String lowerRight =
                        words.get(right).substring(words.get(right).length() - 1);
                    for (Integer bottom : bottoms) {
                        if (words.get(bottom).endsWith(lowerRight)) {
                            Integer[] i = new Integer[]{top, left, right, bottom};
                            Arrays.sort(i);
                            map.put(Arrays.toString(i), i);
                            
                        }
                    }
                }
            }
            top++;
        }
        Collection<Integer[]> res = map.values();
//        long end = System.currentTimeMillis();
//        System.out.println("count: " + res.size());
//        System.out.println("time: " + (end - start) + "ms");
//        for (Integer[] i : res) {
//            System.out.println(
//                words.get(i[0]) + "," + words.get(i[1]) + ","
//                    + words.get(i[2]) + "," + words.get(i[3]));
//        }
    }
    private static void init() throws IOException {
        HashSet<String> set = new HashSet<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(new File("words.txt")));
            String line;
            while ((line = reader.readLine()) != null) {
                set.add(line);
            }
        } finally {
            if (reader != null) reader.close();
        }
        words = new ArrayList<String>(set);
        Collections.sort(words);
        headMap = new HashMap<String, Integer>();
        headChars = new ArrayList<String>(words.size());
        int index = 0;
        for (String word : words) {
            String head = word.substring(0, 1);
            headChars.add(head);
            if (!headMap.containsKey(head)) {
                headMap.put(head, index);
            }
            index++;
        }
    }
    private static List<Integer> findChars(String s) {
        List<Integer> pickIndex = new ArrayList<Integer>();
        if (!headMap.containsKey(s)) {
            return Collections.emptyList();
        }
        int index = headMap.get(s);
        pickIndex.add(index);
        for (int i = index + 1; i < headChars.size(); i++) {
            if (s.equals(headChars.get(i))) {
                pickIndex.add(i);
            } else {
                break;
            }
        }
        return pickIndex;
    }
}

　同じアルゴリズムでJavaでも書いてみました。更に遅くなりました。コード晒すの恥ずかしくなってきました…。

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

DouKaku?

四字熟語パズルの作成

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq