<repo_name>lynch0571/idiom-game<file_sep>/README.md
# idiom-game

成语接龙(ChengYuJieLong)小游戏，使用图论(Graph Theory)和递归(Recursion)等算法实现成语接龙和求特殊成语链，如自环、N连环、Max链等。


## 使用图论中的有向邻接矩阵描述成语之间的关系

#### 邻接矩阵(Adjacency Matrix)概念
> 简单来说，邻接矩阵是表示顶点之间相邻关系的矩阵，图论问题经常会用到。 设G=(V,E)是一个图，其逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。 因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。

邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。成语接龙问题显然是有方向的，A的下一个成语是B，但B的下一个成语不一定是A，也不一定不是A，具体定义如下。


**定义**:
设M=(X,Y)为有向邻接矩阵，X和Y均为成语的全集，X代表行，Y代表列，Xn为第n个成语x，x0为成语x的第一个字，x1为成语x的最后一个字，Y同理。

+ 0-无连接:x1!=y0且y1!=x0
+ 1-xy连接:x1=y0且y1!=x0
+ 2-yx连接:y1=x0且x1!=y0
+ 3-双向连接:x1=y0且y1=x0

示例:
```
      |           x1      x2       x3      x4
------|----------------------------------------
      |         木秀于林 林寒洞肃 花好月圆 防不胜防
    y1|木秀于林    0       2        0      0
    y2|林寒洞肃    1       0        0      0
    y3|花好月圆    0       0        0      0
    y4|防不胜防    0       0        0      3
      |
```<file_sep>/src/main/java/com/lynch/idiom/entity/Idiom.java
package com.lynch.idiom.entity;

import lombok.Data;

/**
 * 成语实体类
 *
 * @author Lynch
 * @date 2020-12-16
 */
@Data
public class Idiom {
    /**
     * 成语名称，如：花好月圆
     */
    private String name;
    /**
     * 成语的第一个字，如：花
     */
    private String head;
    /**
     * 第一个字的拼音，如：huā
     */
    private String headSymbol;
    /**
     * 成语的最后一个字，如：圆
     */
    private String tail;
    /**
     * 最后一个字的拼音，如：yuán
     */
    private String tailSymbol;
    /**
     * 成语的出处，如：宋·张先《木兰花》词：“人意共怜花月满，花好月圆人又散。欢情去逐远云空，往事过如幽梦断。”
     */
    private String derivation;
    /**
     * 成语的解释，如：花儿正盛开，月亮正圆满。比喻美好圆满的生活，多用作新婚颂辞。
     */
    private String explanation;


}
<file_sep>/src/test/java/com/lynch/idiom/IdiomGameApplicationTests.java
package com.lynch.idiom;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
class IdiomGameApplicationTests {

    @Test
    void contextLoads() {
    }

}
<file_sep>/src/main/java/com/lynch/idiom/utils/StringUtil.java
package com.lynch.idiom.utils;

import java.util.Stack;

/**
 * 字符串工具类
 *
 * @author Lynch
 * @date 2020-12-04
 */
public final class StringUtil {

    private StringUtil() {
    }

    /**
     * Check if the String is null or has only whitespaces.
     * Modified from {org.apache.commons.lang.StringUtils#isBlank(String)}.
     *
     * @param string String to check
     * @return {@code true} if the String is null or has only whitespaces
     */
    public static boolean isBlank(String string) {
        if (isEmpty(string)) {
            return true;
        }
        for (int i = 0; i < string.length(); i++) {
            if (!Character.isWhitespace(string.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * Check if the String has any non-whitespace character.
     *
     * @param string String to check
     * @return {@code true} if the String has any non-whitespace character
     */
    public static boolean isNotBlank(String string) {
        return !isBlank(string);
    }

    /**
     * Check if the String is null or empty.
     *
     * @param string String to check
     * @return {@code true} if the String is null or empty
     */
    public static boolean isEmpty(String string) {
        return string == null || string.isEmpty();
    }

    /**
     * Check if the String has any character.
     *
     * @param string String to check
     * @return {@code true} if the String has any character
     * @since 1.1.0
     */
    public static boolean isNotEmpty(String string) {
        return !isEmpty(string);
    }

    /**
     * 用栈解决括号匹配问题，实现数据格式化
     *
     * @param str
     * @return
     */
    public static String getFormatData(String str) {
        Stack<Character> st = new Stack<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '{' || str.charAt(i) == '[' || str.charAt(i) == '(') {
                st.push(str.charAt(i));
                sb.append(str.charAt(i));
                sb.append('\n');
                for (int j = 0; j < st.size(); j++) {
                    sb.append('\t');
                }
            } else if (str.charAt(i) == '}' || str.charAt(i) == ']' || str.charAt(i) == ')') {
                st.pop();
                sb.append('\n');
                for (int j = 0; j < st.size(); j++) {
                    sb.append('\t');
                }
                sb.append(str.charAt(i));
            } else if (str.charAt(i) == ',') {
                sb.append(str.charAt(i)).append("\n");
                for (int j = 0; j < st.size(); j++) {
                    sb.append('\t');
                }
            } else if (str.charAt(i) != ' ') {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

}<file_sep>/src/main/java/com/lynch/idiom/utils/IdiomUtil.java
package com.lynch.idiom.utils;

import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import lombok.extern.slf4j.Slf4j;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

/**
 * @author Lynch
 * @date 2020-12-16
 */
@Slf4j
public class IdiomUtil {

    private static final String idiomPath = "/Users/fire/git/idiom-game/src/main/resources/static/";

    public static void main(String[] args) {
        createIdiomSimpleJson();
    }

    /**
     * 根据原始成语库生成简略版成语库，大约能压缩十倍内容，为后续处理提高效率
     */
    private static void createIdiomSimpleJson() {
        try {
            List<String> lines = Files.readAllLines(Paths.get(idiomPath + "idiom.json"));
            StringBuilder sb = new StringBuilder();
            lines.forEach(e -> sb.append(e));
            JSONArray info = JSONObject.parseArray(sb.toString());
            StringBuilder wordSb = new StringBuilder();
            info.stream().forEach(e -> {
                JSONObject item = (JSONObject) e;
                String word = item.getString("word");
                /*全角空格替换为半角空格*/
                String pinyin = item.getString("pinyin").replace("　", " ");
                wordSb.append(word).append("(").append(pinyin).append(")").append("\n");
            });
            Files.write(Paths.get(idiomPath + "idiomSimple.json"), wordSb.toString().getBytes());
            log.info("创建精简成语json文件成功！共{}个成语。", info.size());
        } catch (IOException e) {
            log.info("创建精简成语json文件失败！e:{}", e.getMessage());
        }
    }
}
