2

有效地解决wordle（对于人类和计算机）现在风靡一时。

解决单词的一种特殊方法让我很好奇。这个想法是选择 5 个具有不同字母的单词，这样你最终会得到 25 个字符。如果你在游戏中使用这 5 个单词作为你的前 5 个猜测，你将有接近 100% 的机会在最后一次猜测中得到正确的单词（它本质上是所有线索的字谜，你可能会有一个几个绿色的）。建议使用一组单词（所有单词都是有效的英文单词）：

  • 砖
  • 格伦特
  • 跳动
  • vozhd
  • 宗教信仰

但这让我想知道：这 5 个单词组合中有多少个存在，我开始编写递归算法，但我快要放弃了。

我最初的想法是：

  • 从第一个单词开始
  • 减少单词列表中的重叠单词
  • 选择单词列表中的下一个剩余单词
  • 重复下一个单词

但这只有在你有一组五个不同的单词时才真正起作用。

对于此列表：

  • 砖
  • 盛宴
  • 格伦特
  • 跳动
  • vozhd
  • 宗教信仰

我最终会得到：[brick, feast, jumpy, vozhd]因为feast来之前glent并且会过滤掉它，但最终glent会是更好的选择。

我无法为这个特定问题找到任何算法，所以我想知道是否有任何现有的算法可以应用于此？

4

1 回答 1

1

这是可能的暴力破解。为了提高效率，可以丢弃所有具有重复字母的单词，并对单词进行预处理以使用它们具有哪些字母的位掩码（有 26 个字母，因此这适合 32 位无符号整数）。

然后只需进行深度优先搜索，维护一个与目前找到的单词不相交的单词列表（位掩码）。

我已经编写了一些执行此操作的 go 代码。它使用仅包含解决方案单词的简短单词列表（完整的单词列表太长，无法在此处包含），但即使使用完整列表，代码也会在几秒钟内运行。

因为它使用位掩码来表示单词，所以解决方案中可能存在多个具有相同字母的单词。该程序显示了|介于两者之间的那些。只有一对：cylix|xylic在解决方案中：

bling treck waqfs jumpy vozhd
pling treck waqfs jumby vozhd
brick glent waqfs jumpy vozhd
kreng clipt waqfs jumby vozhd
fjord chunk vibex gymps waltz
fjord gucks vibex nymph waltz
prick glent waqfs jumby vozhd
kempt brung waqfs cylix|xylic vozhd
blunk waqfs cimex grypt vozhd
clunk waqfs bemix grypt vozhd

它可以在这里运行：https ://go.dev/play/p/wVEDjx3G1fE

package main

import (
    "fmt"
    "math/bits"
    "sort"
    "strings"
)

var allWords = []string{
    "bemix", "bling", "blunk", "brick", "brung", "chunk", "cimex", "clipt", "clunk", "cylix", "fjord", "glent", "grypt", "gucks", "gymps", "jumby", "jumpy", "kempt", "kreng", "nymph", "pling", "prick", "treck", "vibex", "vozhd", "waltz", "waqfs", "xylic",
}

func printSol(res []uint32, masks map[uint32][]string) {
    var b strings.Builder
    for i, r := range res {
        if i > 0 {
            b.WriteString(" ")
        }
        b.WriteString(strings.Join(masks[r], "|"))
    }
    fmt.Println(b.String())
}

func find5(w []uint32, mask uint32, n int, res []uint32, masks map[uint32][]string) {
    if n == 5 {
        printSol(res, masks)
        return
    }
    sub := []uint32{}
    for _, x := range w {
        if x&mask != 0 {
            continue
        }
        sub = append(sub, x)
    }
    for i, x := range sub {
        res[n] = x
        find5(sub[i+1:], mask|x, n+1, res, masks)
    }
}

func find5clique() {
    masks := map[uint32][]string{}
    for _, x := range allWords {
        m := uint32(0)
        for _, c := range x {
            m |= 1 << (c - 'a')
        }
        if bits.OnesCount32(m) == 5 {
            masks[m] = append(masks[m], x)
        }
    }
    maskSlice := []uint32{}
    for m := range masks {
        maskSlice = append(maskSlice, m)
    }
    sort.Slice(maskSlice, func(i, j int) bool {
        return maskSlice[i] < maskSlice[j]
    })
    find5(maskSlice, uint32(0), 0, make([]uint32, 5, 5), masks)
}

func main() {
    find5clique()
}
于 2022-02-07T08:44:25.303 回答