侧边栏壁纸
博主头像
luoxx博主等级

只要思想不滑坡,办法总比困难多

  • 累计撰写 53 篇文章
  • 累计创建 58 个标签
  • 累计收到 981 条评论

目 录CONTENT

文章目录

猜字母游戏算法

luoxx
2023-10-17 / 0 评论 / 2 点赞 / 2,545 阅读 / 931 字
温馨提示:
本文最后更新于 2023-10-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

最近公司搞了个内部比赛,出了一个编程题目,现在比赛已经完成了,所以在这记录下博主的参赛代码(博主的成绩比较一般,只能到中等偏上的水平)

游戏介绍

猜单词是猜数字(又称 Bulls and Cows )的变形,猜数字是一种古老的密码破译类益智双人小游戏

通常由两个人玩,一方出单词,一方猜。出单词的人要想好一个由五个不同字母组成的单词,不能让猜的人知道。猜的人就可以开始猜。每猜一个单词,出单词的人就要根据这个单词给出几A几B,其中A前面的数字表示位置正确的字母的个数,而B前面的数字表示字母正确而位置不对的字母的个数。

如正确答案为 CGFDJ,而猜的人猜 CFDHL,则是1A2B,其中C的位置对了,记为1A,而F和D这两个字母对了,但位置没对,因此记为2B,合起来就是 1A2B。

接着猜的人再根据出题者的几A几B继续猜,直到猜中为止(即 5A0B)

比赛规则

  1. 参赛编程语言限定为Go

  2. 你需要编写guessword() 函数

  3. guessword() 函数中你需要调用一个预先定义好的函数 judge(guess string) (A int, B int)来获取猜测结果。注:如果 judge 返回的A等于5,guessword() 函数函数需要 return。如果guess参数不合规定,A、 B会等于0、0。

  4. 程序会执行100个case,所有case猜测正确才会统计排名。

  5. 上传的代码文件命名没有要求,package 必须是main

参赛代码

package main

import (
	"math/rand"
	"strings"
)

func guessWord() {
	guessesMade := make(map[string]bool)
	passwords := generatePasswords()
	index := 1
	for {
		var guess string
		if 1 == index {
			guess = "ADGJM"
		} else {
			for {
				guess = passwords[rand.Intn(len(passwords))]
				if !guessesMade[guess] {
					break
				}
			}
		}
		index++
		guessesMade[guess] = true
		a, b := judge(guess)

		if a == 5 {
			return
		}
		passwords = filterPasswords(passwords, guess, a, b)
	}
}

// 组合生成所有可能得排列方式
func generatePasswords() []string {
	var passwords []string
	letters := []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"}
	for i := 0; i < 13; i++ {
		for j := 0; j < 13; j++ {
			for k := 0; k < 13; k++ {
				for l := 0; l < 13; l++ {
					for m := 0; m < 13; m++ {
						if i != j && i != k && i != l && i != m &&
							j != k && j != l && j != m &&
							k != l && k != m &&
							l != m {
							passwords = append(passwords, letters[i]+letters[j]+letters[k]+letters[l]+letters[m])
						}
					}
				}
			}
		}
	}
	return passwords
}

// 根据猜测结果筛出不符合的组合
func filterPasswords(passwords []string, guess string, a int, b int) []string {
	var newPasswords []string
	for _, password := range passwords {
		// 检查password与guess字母相同的个数,与猜中总数比较,不相等则肯定不是最终结果,剔除
		matched := 0
		for i := 0; i < len(guess); i++ {
			if strings.Contains(password, string(guess[i])) {
				matched++
			}
		}
		if matched != a+b {
			continue
		}
		// 检查password与guess字母相同且位置相同的字母个数,若相同个数不等于a,则肯定不是最终结果,剔除
		positionMatched := 0
		for i := 0; i < len(guess); i++ {
			if guess[i] == password[i] {
				positionMatched++
			}
		}
		if positionMatched != a {
			continue
		}
		newPasswords = append(newPasswords, password)
	}
	return newPasswords
}

总结

博主的代码很简单,看注释就能很好理解,100次猜测运气最好的一次执行用了650次猜测,这个成绩比第一名的623次还差一截,后续等第一名的代码公布,再贴到本帖一起学习一下。

2

评论区