• 偷摸写了一个游戏

    2024-08-09 17:24

    是的, 纯 go

  • 尝试了三个优化:

    1. 初始化时加入了拼音,去掉了深搜时多次中文转拼音的复杂度。
    2. 剪枝了多次尝试已经试探过的部分,tryBehindStep提供记忆
    3. 采用了清华中文词库,将频率更高的词汇提前,这个实际并没有加速,但是就仅找到一个答案而言好像蛮有用的(如果采用更小的数据集也算优化😋)

    部分答案如:坚定不移 敲诈勒索 深恶痛绝 云蒸霞蔚 酒醉饭饱 柔肠百转

    image.png

    这版丑陋的代码:

    package main
    
    import (
    	"encoding/json"
    	"fmt"
    	"github.com/mozillazg/go-pinyin"
    	"io/ioutil"
    )
    
    var words, initWords []string
    var wordsFirst, wordsFinals [][]string
    var totalAns int
    
    func DFS(step int, tryBehindStep int, vis map[string]int, vowelVis map[string]int, ans []string) {
    	if step >= 6 {
    		// 退出
    		fmt.Println(ans)
    		totalAns++
    		return
    	}
    
    	for ind, w := range words {
    		if ind < tryBehindStep {
    			continue
    		}
    
    		// 试探首字母是否重复
    		wordArray := wordsFirst[ind]
    		if vis[wordArray[0]] > 0 || vis[wordArray[1]] > 0 || vis[wordArray[2]] > 0 || vis[wordArray[3]] > 0 {
    			continue
    		}
    
    		// 试探韵母是否重复
    		wordArray = wordsFinals[ind]
    		if vowelVis[wordArray[0]] > 0 || vowelVis[wordArray[1]] > 0 || vowelVis[wordArray[2]] > 0 || vowelVis[wordArray[3]] > 0 {
    			continue
    		}
    
    		// 暴搜下一步
    		for indF := 0; indF < 4; indF++ {
    			vowelVis[wordsFinals[ind][indF]]++
    			vis[wordsFirst[ind][indF]]++
    		}
    		ans = append(ans, w)
    		DFS(step+1, ind+1, vis, vowelVis, ans)
    		// 回溯
    		for indF := 0; indF < 4; indF++ {
    			vowelVis[wordsFinals[ind][indF]]--
    			vis[wordsFirst[ind][indF]]--
    		}
    		ans = ans[:len(ans)-1]
    	}
    
    	return
    }
    
    func main() {
    	// 读取 JSON 文件
    	fmt.Println("Start")
    	totalAns = 0
    	fileData, err := ioutil.ReadFile("good_data.json")
    	if err != nil {
    		fmt.Println("无法读取文件:", err)
    		return
    	}
    
    	// 解码 JSON 数据
    	err = json.Unmarshal(fileData, &initWords)
    	if err != nil {
    		fmt.Println("解码 JSON 失败:", err)
    		return
    	}
    
    	// 预处理
    	pinyinApp := pinyin.NewArgs()
    	for _, w := range initWords {
    		pinyinApp.Style = pinyin.FirstLetter
    		wordArray := pinyin.Pinyin(w, pinyinApp)
    
    		// 仅保留四字成语
    		if len(wordArray) != 4 {
    			continue
    		}
    
    		// 去除首字母本身重复
    		vis := make(map[string]int)
    		var firstWords, finalWords []string
    		for i := 0; i < 4; i++ {
    			vis[wordArray[i][0]]++
    			firstWords = append(firstWords, wordArray[i][0])
    		}
    		if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 {
    			continue
    		}
    
    		// 去除韵母本身重复
    		pinyinApp.Style = pinyin.Finals
    		wordArray = pinyin.Pinyin(w, pinyinApp)
    		vowelVis := make(map[string]int)
    		for i := 0; i < 4; i++ {
    			vowelVis[wordArray[i][0]]++
    			finalWords = append(finalWords, wordArray[i][0])
    		}
    		if vowelVis[wordArray[0][0]] > 1 || vowelVis[wordArray[1][0]] > 1 || vowelVis[wordArray[2][0]] > 1 || vowelVis[wordArray[3][0]] > 1 {
    			continue
    		}
    
    		words = append(words, w)
    		wordsFinals = append(wordsFinals, finalWords)
    		wordsFirst = append(wordsFinals, firstWords)
    	}
    	// 按照拼音排序
    	// 可能有效的优化
    	//sort.Slice(words, func(i, j int) bool {
    	//	return words[i] < words[j]
    	//})
    
    	fmt.Println("有效数据集: ", len(words))
    	DFS(0, 0, make(map[string]int), make(map[string]int), []string{})
    	fmt.Println("End.totalAns: ", totalAns)
    }
    

    仍存在的问题:

    • 只跑了成语数8000的小数据集,且有限时间内得不到所有答案
    • 声母韵母的处理仍然太暴力了,后续仍可以用位运算优化
  • 超级暴搜,可惜复杂度太高了,下周再来优化~~(要下班了)~~。目前可以跑出大量五个成语

    image.png

    抽象的代码如下

    package main
    
    import (
    	"encoding/json"
    	"fmt"
    	"github.com/mozillazg/go-pinyin"
    	"io/ioutil"
    	"sort"
    )
    
    var words, initWords []Word
    
    func DFS(step int, vis map[string]int, ans []string) {
    	if step >= 6 {
    		// 退出
    		fmt.Println(ans)
    		return
    	}
    
    	pinyinApp := pinyin.NewArgs()
    	pinyinApp.Style = pinyin.FirstLetter
    	for _, w := range words {
    		wordArray := pinyin.Pinyin(w.Word, pinyinApp)
    
    		// 试探是否重复
    		if vis[wordArray[0][0]] > 0 || vis[wordArray[1][0]] > 0 || vis[wordArray[2][0]] > 0 || vis[wordArray[3][0]] > 0 {
    			continue
    		}
    
    		// 暴搜下一步
    		vis[wordArray[0][0]]++
    		vis[wordArray[1][0]]++
    		vis[wordArray[2][0]]++
    		vis[wordArray[3][0]]++
    		ans = append(ans, w.Word)
    		DFS(step+1, vis, ans)
    		vis[wordArray[0][0]]--
    		vis[wordArray[1][0]]--
    		vis[wordArray[2][0]]--
    		vis[wordArray[3][0]]--
    		ans = ans[:len(ans)-1]
    	}
    
    	return
    }
    
    type Word struct {
    	Pinyin string `json:"pinyin"`
    	Word   string `json:"word"`
    }
    
    func main() {
    	// 读取 JSON 文件
    	fmt.Println("Start")
    	fileData, err := ioutil.ReadFile("data.json")
    	if err != nil {
    		fmt.Println("无法读取文件:", err)
    		return
    	}
    
    	// 解码 JSON 数据
    	err = json.Unmarshal(fileData, &initWords)
    	if err != nil {
    		fmt.Println("解码 JSON 失败:", err)
    		return
    	}
    
    	// 预处理
    	pinyinApp := pinyin.NewArgs()
    	pinyinApp.Style = pinyin.FirstLetter
    	for _, w := range initWords {
    		wordArray := pinyin.Pinyin(w.Word, pinyinApp)
    
    		// 仅保留四字成语
    		if len(wordArray) != 4 {
    			continue
    		}
    
    		// 去除本身重复
    		vis := make(map[string]int)
    		vis[wordArray[0][0]]++
    		vis[wordArray[1][0]]++
    		vis[wordArray[2][0]]++
    		vis[wordArray[3][0]]++
    		if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 {
    			continue
    		}
    
    		words = append(words, w)
    	}
    	// 按照拼音排序
    	sort.Slice(words, func(i, j int) bool {
    		return words[i].Pinyin < words[j].Pinyin
    	})
    
    	DFS(0, make(map[string]int), []string{})
    	fmt.Println("End")
    }
    

    可能存在的优化方案:

    找出频率最高的声韵母

破防的小蔡
Amove
离线
破了但没有完全破;摸了但不是全在摸
  • 0 标签
  • 1 帖子
  • 3 回帖
  • 1 关注者
  • 2 关注用户
  • 28,356 分钟 在线时间



个人主页