DouKaku?beta

challenge いちばん長いしりとり

単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう

see: 難聴者のための単語了解度試験用単語リスト

post comment

Posted feedbacks - Java

Javaで単純に。 単純すぎるため、短時間で結果を出せるのは100単語ぐらいまでのようです。

  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
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
import java.io.*;
import java.util.*;

/**
 * いちばん長いしりとり
 */
public class TheLongestSiritori {
    
    // 単語
    private static class Word {
        String text;    // 単語の文字列
        boolean used;    // 使用中フラグ
    }

    // 頭文字をキーとする単語の索引。
    private static Map<String, List<Word>> index = new HashMap<String, List<Word>>();
    
    /**
     * メインルーチン
     * @param args 最初の引数は単語ファイルの名前
     */
    public static void main( String[] args ) {
    
        ////////////////////////////////////////////////////////////
        // 引数から単語ファイルの名前を取得する。
        ////////////////////////////////////////////////////////////
        
        // 引数に単語ファイルの名前が指定されていることを確認する。
        if ( args.length < 1 ) {
            // 指定されていない
            System.err.println( "引数に単語ファイルの名前を指定してください。"  );
            return;
        }
        
        // 引数からファイル名を取得する。
        String fileName = args[0];
        
        ////////////////////////////////////////////////////////////
        // 単語ファイルを読み込み、単語の一覧を作成する。
        ////////////////////////////////////////////////////////////
        
        List<Word> wordList = new ArrayList<Word>();
        BufferedReader reader = null;
        try {
            // 単語ファイルを開く。
            reader = new BufferedReader( new FileReader( fileName ) );
            
            // 単語ファイルの行ごとに以下を繰り返す。
            String line;
            while ( ( line = reader.readLine() ) != null ) {
                // 行が空でないことを確認する。
                if ( line.length() > 0 ) {
                    // 行の内容を単語の一覧に追加する。
                    Word word = new Word();
                    word.text = line;
                    word.used = false;
                    wordList.add( word );
                }
            }
            
        } catch ( IOException e ) {
            // 入力エラー:
            System.err.println( "単語ファイルを正常に読み込めませんでした。ファイル名前=[" + fileName + "]"  );
            return;
            
        } finally {
            if ( reader != null ) {
                try {
                    // 単語ファイルを閉じる。
                    reader.close();
                } catch ( IOException e ) {
                    /* 無視 */
                }
            }
        }
        
        ////////////////////////////////////////////////////////////
        // 頭文字をキーとした単語の索引を作成する。
        ////////////////////////////////////////////////////////////
        
        index = new HashMap<String, List<Word>>();

        // 単語の一覧中のすべての単語について、以下を繰り返す。
        for ( int i = 0; i < wordList.size(); ++i ) {
            Word word = wordList.get( i );
            // 単語の頭文字を取得する。
            String first = word.text.substring( 0, 1 );
            
            List<Word> container;
            // 同一の頭文字の単語が、索引に格納済みであることを確認する。
            if ( ! index.containsKey( first ) ) {
                // 同一の頭文字の単語が、まだ格納されていない:
                
                // 頭文字に対応する単語格納リストを作成する。
                container = new ArrayList<Word>();
                index.put( first, container );
            } else {
                // 頭文字に対応する単語格納リストを作成する。
                container = index.get( first );
            }

            // 単語格納リストに単語を追加する。
            container.add( word );
        }
        
        ////////////////////////////////////////////////////////////
        // しりとりをする。
        ////////////////////////////////////////////////////////////
        
        // 最初の単語をランダムに決める。
        int rnd = new Random().nextInt( wordList.size() );
        Word start = wordList.get( rnd );
        
        // 最長のしりとり結果(逆順)を取得する。
        List<String> longest = getLongest( start );
        
        // しりとり結果を反転する。
        Collections.reverse( longest );
        
        ////////////////////////////////////////////////////////////
        // 結果を表示する。
        ////////////////////////////////////////////////////////////
        
        for ( int i = 0; i < longest.size(); ++i ) {
            System.out.println( ( i + 1 ) + ": " + longest.get( i ) );
        }
    }
    
    /*
     * 最長のしりとり結果(逆順)を取得する。
     * @param 単語
     * @return 最長のしりとり結果(逆順)
     */
    public static List<String> getLongest( Word word ) {
        // 単語使用中フラグをオンにする。
        word.used = true;
        
        // 単語の末尾の文字を取得する。
        String text = word.text;
        int length = text.length();
        String last = text.substring( length - 1, length );
        
        List<String> longest = new ArrayList<String>();
        
        // 索引に末尾の文字が含まれていることを確認する。
        if ( index.containsKey( last ) ) {

            ////////////////////////////////////////////////////////////
            // 末尾の文字の後に続く、最長のしりとり結果を見つける。
            ////////////////////////////////////////////////////////////

            // 末尾の文字から始まるすべての単語について、以下を繰り返す。
            List<Word> container = index.get( last );
            for ( int i = 0; i < container.size(); ++i ) {
                Word nextWord = container.get( i );
                // 単語使用中フラグがオフであることを確認する。
                if ( ! nextWord.used ) {
                    // しりとり結果を取得する。
                    List<String> temp = getLongest( nextWord );
                    // 最長のしりとり結果を見つける。
                    if ( temp.size() > longest.size() ) {
                        longest = temp;
                    }
                }
            }
        }
        
        // 単語をしりとり結果に追加する。
        longest.add( text );
        
        // 単語使用中フラグをオフにする。
        word.used = false;

        return longest;
    }
}

促音・拗音は、前の単語と合わせてキーとするようにしたり、ひらがな→カタカナに変換して同一視したりしてみました。

ただ、全単語を単純に探索しているので計算量が爆発してました。160単語程度なら、すぐに結果が返ってくる程度です。

  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
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
import java.io.*;
import java.util.*;

public class Sample277 {
    static class Word {
        /// キーは全てカタカナに正規化
        public static String convertHiraganaToKatakana(String s) {
            StringBuilder builder = new StringBuilder(s);
            for (int index = 0; index < builder.length(); index++) {
                char c = builder.charAt(index);
                if ('ぁ' <= c && c <= 'ん') {
                    builder.setCharAt(index, (char)(c - 'ぁ' + 'ァ'));
                }
            }
            return builder.toString();
        }

        /// 拗音・促音・濁点などのリスト
        private static final Set<Character> anomalyLetters_ = new HashSet<Character>();
        {
            anomalyLetters_.add('ぁ');
            anomalyLetters_.add('ぃ');
            anomalyLetters_.add('ぅ');
            anomalyLetters_.add('ぇ');
            anomalyLetters_.add('ぉ');
            anomalyLetters_.add('っ');
            anomalyLetters_.add('ゃ');
            anomalyLetters_.add('ゅ');
            anomalyLetters_.add('ょ');
            anomalyLetters_.add('ァ');
            anomalyLetters_.add('ィ');
            anomalyLetters_.add('ゥ');
            anomalyLetters_.add('ェ');
            anomalyLetters_.add('ォ');
            anomalyLetters_.add('ッ');
            anomalyLetters_.add('ャ');
            anomalyLetters_.add('ュ');
            anomalyLetters_.add('ョ');
            anomalyLetters_.add('゛');
            anomalyLetters_.add('゜');
        }

        public final String s;
        public final String first;
        public final String last;
        private boolean used_ = false;

        public Word(String s) {
            this.s = s;
            first = convertHiraganaToKatakana(getFirstLetter(s));
            last = convertHiraganaToKatakana(getLastLetter(s));
        }
        // しりとりのキーとしての最初の音
        private String getFirstLetter(String s) {
            if (anomalyLetters_.contains(s.charAt(1))) {
                return s.substring(0, 2);
            }
            return s.substring(0, 1);
        }
        // しりとりのキーとしての最後の音
        private String getLastLetter(String s) {
            int lastStartIndex = s.length() - 1;
            int lastEndIndex = s.length();
            char c = s.charAt(lastStartIndex);
            if (c == 'ー' || c == 'ー') {
                lastStartIndex--;
                lastEndIndex--;
                c = s.charAt(lastStartIndex);
            }
            if (anomalyLetters_.contains(c)) {
                lastStartIndex--;
            }
            return s.substring(lastStartIndex, lastEndIndex);
        }

        public boolean isUsed() {
            return used_;
        }
        public void setUsed(boolean used) {
            used_ = used;
        }


        @Override
        public boolean equals(Object obj) {
            if (!this.getClass().equals(obj.getClass())) {
                return false;
            }
            Word other = (Word) obj;
            return this.s.equals(other.s);
        }
        @Override
        public int hashCode() {
            return s.hashCode();
        }
    }


    private final Map<String, Set<Word>> wordMap_ = new HashMap<String, Set<Word>>();

    public Sample277() {
    }

    public void addWord(String s) {
        Word word = new Word(s);
        Set<Word> set = wordMap_.get(word.first);
        if (set == null) {
            set = new HashSet<Word>();
            wordMap_.put(word.first, set);
        }
        set.add(word);
    }


    public List<String> getLongest(String start) {
        Word w = new Word(start);
        return getLongestR(w);
    }
    public List<String> getLongestR(Word w) {
        List<String> result = new LinkedList<String>();
        w.used_ = true;
        Set<Word> set = wordMap_.get(w.last);
        Set<String> firstLetter = new HashSet<String>();
        if (set != null) {
            for (Word word: set) {
                if (word.isUsed()) {
                    continue;
                }
                if (firstLetter.contains(word.last)) {
                    continue;
                }
                firstLetter.add(word.last);
                
                List<String> list = getLongestR(word);
                if (result.size() < list.size()) {
                    result = list;
                }
            }
        }
        w.used_ = false;
        result.add(0, w.s);
        return result;
    }


    public static List<String> loadFile(String path) throws FileNotFoundException {
        List<String> result = new ArrayList<String>();
        Scanner scanner = new Scanner(new File(path), "MS932");
        while (scanner.hasNext()) {
            result.add(scanner.next());
        }
        scanner.close();
        return result;
    }

    public static void main(String[] args) throws IOException {
        List<String> strings = loadFile("fam55_10.txt");
        System.out.println("input count: " + strings.size());

        Sample277 sample = new Sample277();
        for (String s: strings) {
            sample.addWord(s);
        }

        long start = System.currentTimeMillis();
        List<String> result = sample.getLongest("しりとり");
        long elapse = System.currentTimeMillis() - start;
        System.out.println("elapse: " + elapse + "(ms)");

        System.out.println("max length: " + result.size());
        for (String s: result) {
            System.out.println(s);
        }
    }
}

厳密解ではなく、ヒューリスティックな解法ですが、お題の単語リストに対して1秒程度で580語前後のしりとりを抽出できます。
見つけた最長のしりとりは624語 (ホロバシャ, ヤスヤド, ドクダミ, … 略 … , ツノブエ, エスプリ, リンカン) でした。

しりとりは、文字と文字をつなぐ有向グラフと考えられるので、グラフ理論を応用すればもっと良い解法が得られるのではないかと思います。 
  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
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
import java.io.InputStreamReader;
import java.util.*;

public class Shiritori3 {
    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        final Scanner scanner = new Scanner(new InputStreamReader(
                Shiritori.class.getResourceAsStream("Words_jp.txt"), "UTF-8"));
        new Shiritori3(scanner).analyze();
        System.out.printf("%f [sec]%n", ((double)System.nanoTime() - startTime) / 100000000);
    }

    Map<Character, Node> nodes;

    public Shiritori3(Scanner scanner) {
        nodes = new HashMap<Character, Node>();
        init(scanner);
    }

    private void init(Scanner scanner) {
        while (scanner.hasNext()) {
            String edge = scanner.next();
            char head = headChar(edge);
            char tail = tailChar(edge);
            if (!nodes.containsKey(head)) nodes.put(head, new Node(head));
            if (!nodes.containsKey(tail)) nodes.put(tail, new Node(tail));
            nodes.get(head).addGoOutEdge(edge);
            nodes.get(tail).addCominEdge(edge);
        }
        scanner.close();
    }

    public void analyze() {
        Set<Node> noflows = new HashSet<Node>();
        Set<Node> flows = new HashSet<Node>();
        for (Node node : nodes.values())
            if (node.hasCapacity()) flows.add(node);

        List<LinkedList<String>> pathList = new ArrayList<LinkedList<String>>();

        while (!flows.isEmpty()) {

            // 初期ノードの選択により、結果が変化する
            Node head = flows.toArray(new Node[0])[new java.util.Random().nextInt(flows.size())];
            Node tail = head;

            LinkedList<String> path = new LinkedList<String>();
            pathList.add(path);

            while (head.hasCapacity() || tail.hasCapacity()) {
                if (!head.inEdges.isEmpty()) {
                    String newHead = popInEdge(head);
                    path.addFirst(newHead);
                    if (!head.hasCapacity()) flows.remove(head);
                    head = nodes.get(headChar(newHead));
                }

                if (!tail.outEdges.isEmpty()) {
                    String newTail = popOutEdge(tail);
                    path.addLast(newTail);
                    if (!tail.hasCapacity()) flows.remove(tail);
                    tail = nodes.get(tailChar(newTail));
                }
            }
        }

        for (int i = 0, n = pathList.size(); i < n; i++) {
            LinkedList<String> pathA = pathList.get(i);
            if (pathA.size() <= 2) break;
            for (int j = i + 1; j < n; j++) {
                LinkedList<String> pathB = pathList.get(j);
                if (pathB.size() <= 2) break;
                cross(pathA, pathB);
            }
        }

        Collections.sort(pathList, new Comparator<List<?>>() {
            public int compare(List<?> o1, List<?> o2) {
                return o1.size() - o2.size(); }});

        for (LinkedList<String> path : pathList) {
            System.out.printf("%d, %s%n", path.size(), path);
        }
    }

    void cross(LinkedList<String> pathA, LinkedList<String> pathB) {
        int ma = -1, mb = -1;
        int ac = pathA.size(), bc = pathB.size();
        int max = Math.max(ac, bc);
        int a = 0;
        for (String aw : pathA) {
            int b = 0;
            for (String bw : pathB) {
                if (tailChar(aw) == headChar(bw)) {
                    int nmax = Math.max(a + (bc - b) + 1, (ac - a) + b - 1);
                    if (max < nmax) {
                        ma = a;
                        mb = b;
                        max = nmax;
                    }
                }
                b++;
            }
            a++;
        }

        if (ma != -1) {
            LinkedList<String> old1 = new LinkedList<String>(pathA);
            LinkedList<String> old2 = new LinkedList<String>(pathB);
            pathA.clear();
            pathB.clear();
            pathA.addAll(old1.subList(0, ma + 1));
            pathA.addAll(old2.subList(mb, bc));
            pathB.addAll(old2.subList(0, mb));
            pathB.addAll(old1.subList(ma + 1, ac));
            cross(pathA, pathB);
        }
    }

    String popInEdge(Node node) {
        int max = -1;
        String next = null;
        for (String s : node.inEdges) {
            Node nextHead = nodes.get(headChar(s));
            if (max < nextHead.flowCapacity()) {
                max = nextHead.flowCapacity();
                next = s;
            }
        }
        node.inEdges.remove(next);
        return next;
    }

    String popOutEdge(Node node) {
        int max = -1;
        String next = null;
        for (String s : node.outEdges) {
            Node nextTail = nodes.get(tailChar(s));
            if (max < nextTail.flowCapacity()) {
                max = nextTail.flowCapacity();
                next = s;
            }
        }
        node.outEdges.remove(next);
        return next;
    }

    static char tailChar(String edge) {
        return toShiritoriChar(edge.charAt(edge.length() - 1));
    }

    static char headChar(String edge) {
        return toShiritoriChar(edge.charAt(0));
    }

    static final String YOUON = "ァィゥェォヵヶッャュョヮ";
    static final String SEION = "アイウエオカケツヤユヨワ";
    static char toShiritoriChar(final char c) {
        if (YOUON.indexOf(c) == -1)
            return c;
        else
            return SEION.charAt(YOUON.indexOf(c));
    }

    static class Node {
        final LinkedList<String> inEdges = new LinkedList<String>();
        final LinkedList<String> outEdges = new LinkedList<String>();
        final Character c;
        int lilmit;

        public Node(Character c) {
            this.c = c;
        }

        void addCominEdge(String e) {
            inEdges.add(e);
        }

        void addGoOutEdge(String e) {
            outEdges.add(e);
        }

        int flowCapacity() {
            return Math.min(inEdges.size(), outEdges.size());
        }

        boolean hasCapacity() {
            return flowCapacity() > 0;
        }
    }
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]