Solving wordle efficiently (for humans and for computers) is all the rage right now.
One particular way of solving a wordle made me curious. The idea is to select 5 words that have distinct letters so you'll end up with 25 characters. If you use these 5 words as your first 5 guesses in the game, you'll have a close to 100% chance of getting the correct word in your last guess (it's essentially an anagram of all the clues and you'll probably have a few green ones). There is a set of words that is suggested (all of the words are valid English words):
But this made me wonder: How many of these 5 word combinations are out there and I started whipping up a recursive algorithm but I am close to giving up.
My initial thought was:
But this only really works if you have a set of five distinct words in order.
For this list:
I will end up with: [brick, feast, jumpy, vozhd] because feast comes before glent and will filter it out but in the end glent would have been the better pick.
I wasn't able to find any algorithms for this specific problem so I was wondering if there is any existing algorithm that can be applied to this?
It's possible to brute-force this. For efficiency, one can discard all words with duplicate letters, and pre-process the words to use a bitmask of which letters they have (there are 26 letters, so this fits in a 32-bit unsigned integer).
Then just do a depth-first search, maintaining a list of words (bitmasks) that don't intersect with the words found so far.
I've written some go code that does this. It uses a shortened list of words that just contains the solution words (the full wordlist is too long to include here), but the code runs in a few seconds even with the full list.
Because it uses bitmasks to represent words, it's possible that there's multiple words with the same letters in the solution. The program shows those with a | inbetween. There's just one pair: cylix|xylic in the solution:
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
It can be run here: 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()
}