Skip to content

Instantly share code, notes, and snippets.

@timburks
Last active January 10, 2022 05:13
Show Gist options
  • Save timburks/98cdb0a77cd62f1f7c059ef435cbccdd to your computer and use it in GitHub Desktop.
Save timburks/98cdb0a77cd62f1f7c059ef435cbccdd to your computer and use it in GitHub Desktop.
"serai blunt moped" are the three best words to start a Wordle game according to this greedy algorithm that seeks to minimize the largest set of possible solutions after each successive guess.
package main
import (
"fmt"
"io/ioutil"
"sort"
"strings"
)
// This computes a list of static guesses to prune the Wordle solution space.
// Guesses are "static" because we choose these guesses without knowing what
// Wordle's scoring will return for them.
func main() {
// Get the word list from https://tiny.one/wordlewords.
// Make sure that your saved version does not end with a blank line!
bytes, err := ioutil.ReadFile("words.txt")
if err != nil {
panic(err)
}
words := strings.Split(string(bytes), "\n")
if false {
// Optionally filter the word list to a smaller size.
// This is mainly useful for testing and debugging.
filtered := make([]string, 0)
for i, w := range words {
if i%5 == 0 {
filtered = append(filtered, w)
}
}
words = filtered
}
// The prefix is the set of guesses that have already been made.
// We start with an empty prefix and will add to it as each next guess is determined.
prefix := []string{}
// This loop greedily chooses the next guess by selecting the one that
// minimizes the size of the largest bucket of words associated with
// any possible scoring of a guess (or set of guesses).
for {
guess, maxBucketSize, histogram := computeBestGuess(words, prefix)
fmt.Printf("best guess %s (%d) using prefix %+v\n", guess, maxBucketSize, prefix)
printHistogram(histogram)
if maxBucketSize == 1 {
// A max bucket size of 1 means our guesses would identify all the
// possible solution words.
break
}
done := false
for _, p := range prefix {
if guess == p {
// A repeated guess means there's no more information to be gained
// by guessing with the available words.
done = true
}
}
if done {
break
}
prefix = append(prefix, guess)
}
}
// Compute the next guess which minimizes the largest bucket of possible solutions
// where the buckets correspond to scorings of our guess and any specified "prefix" guesses.
func computeBestGuess(words []string, prefix []string) (string, int, map[int]int) {
steps := len(words) / 40 // We use this to print a progress indicator (below).
bestGuess := ""
bestMaxBucketSize := len(words)
var bestBuckets map[string]int
fmt.Printf("choosing guess %d", len(prefix)+1)
for g, guess := range words {
buckets := make(map[string]int, 0)
for _, secret := range words {
var s string
for _, p := range prefix {
s += score(p, secret)
}
s += score(guess, secret)
buckets[string(s)] += 1
}
max := 0
for _, v := range buckets {
if v > max {
max = v
}
}
if g%steps == 0 {
fmt.Printf(".")
}
if max < bestMaxBucketSize {
bestGuess = guess
bestMaxBucketSize = max
bestBuckets = buckets
}
}
fmt.Printf("\n")
// Compute a histogram of the buckets.
// This is the number of buckets of each size in the buckets of possible solutions
// that we would have after making the best guess.
histogram := make(map[int]int)
for _, v := range bestBuckets {
histogram[v] += 1
}
return bestGuess, bestMaxBucketSize, histogram
}
// Print a histogram of bucket sizes.
func printHistogram(histogram map[int]int) {
keys := make([]int, 0)
total := 0.0
for k, v := range histogram {
keys = append(keys, k)
total += float64(k * v)
}
sort.Ints(keys)
sum := 0.0
fmt.Println("SIZE N PERCENT (of words in a bucket of this size or less)")
fmt.Println("---- ----- -------")
for _, k := range keys {
sum += float64(k * histogram[k])
fmt.Printf("%4d %5d %6.2f%%\n", k, histogram[k], 100.0*sum/total)
}
}
// Score a wordle guess.
func score(guessWord, secretWord string) string {
// These byte arrays will be modified as the score is computed.
guess := []byte(guessWord)
secret := []byte(secretWord)
// Mark the exact matches.
for i, g := range guess {
if g == secret[i] {
guess[i] = '2' // Mark the exact match.
secret[i] = ' ' // We don't want to match this letter against any other.
}
}
// Find letters that are correct but out-of-place.
for i, g := range guess {
if g != '2' { // Only do this for letters that weren't exact matches.
for j, s := range secret {
if g == s {
guess[i] = '1' // Mark the right letter that's in the wrong place.
secret[j] = ' ' // We don't want to match this letter against any other.
break
}
}
}
}
// Set all unmarked letters to '0'.
for i, g := range guess {
if g != '1' && g != '2' {
guess[i] = '0'
}
}
// By now we have transformed the guess into a score. Return it.
return string(guess)
}
choosing guess 1.........................................
best guess serai (697) using prefix []
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 16 0.12%
2 16 0.37%
3 9 0.58%
4 8 0.82%
5 1 0.86%
6 8 1.23%
7 2 1.34%
8 2 1.46%
9 4 1.74%
10 2 1.90%
11 4 2.24%
12 6 2.79%
13 2 2.99%
14 1 3.10%
15 1 3.21%
17 1 3.35%
18 4 3.90%
19 2 4.19%
20 1 4.35%
21 2 4.67%
23 1 4.85%
24 1 5.03%
26 1 5.23%
27 2 5.65%
28 2 6.08%
29 1 6.31%
30 1 6.54%
31 1 6.78%
32 1 7.02%
37 1 7.31%
39 1 7.61%
40 1 7.92%
42 3 8.89%
43 4 10.21%
45 1 10.56%
47 1 10.92%
49 1 11.30%
50 1 11.69%
51 1 12.08%
52 1 12.48%
53 1 12.89%
55 1 13.31%
56 1 13.74%
57 1 14.18%
61 3 15.60%
65 1 16.10%
68 1 16.62%
74 2 17.76%
75 1 18.34%
77 1 18.93%
78 1 19.53%
79 1 20.14%
81 1 20.77%
86 1 21.43%
87 1 22.10%
89 1 22.79%
91 1 23.49%
111 1 24.34%
113 1 25.22%
114 1 26.09%
116 1 26.99%
131 2 29.01%
132 1 30.03%
140 1 31.11%
149 1 32.25%
161 1 33.50%
162 1 34.74%
172 1 36.07%
201 1 37.62%
211 1 39.25%
214 1 40.90%
221 1 42.60%
222 1 44.31%
227 1 46.06%
233 1 47.86%
260 1 49.86%
271 1 51.95%
316 1 54.39%
322 1 56.87%
342 1 59.51%
350 1 62.20%
391 2 68.23%
421 1 71.48%
513 1 75.43%
550 1 79.67%
626 1 84.50%
638 1 89.42%
676 1 94.63%
697 1 100.00%
choosing guess 2.........................................
best guess blunt (131) using prefix [serai]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 919 7.08%
2 347 12.43%
3 204 17.15%
4 125 21.01%
5 82 24.17%
6 65 27.17%
7 46 29.66%
8 51 32.80%
9 30 34.88%
10 35 37.58%
11 17 39.02%
12 26 41.43%
13 21 43.53%
14 18 45.47%
15 15 47.21%
16 10 48.44%
17 11 49.88%
18 12 51.55%
19 12 53.31%
20 10 54.85%
21 11 56.63%
22 8 57.99%
23 5 58.87%
25 5 59.84%
26 2 60.24%
27 2 60.65%
28 6 61.95%
29 6 63.29%
30 6 64.68%
31 3 65.39%
32 3 66.13%
33 2 66.64%
34 3 67.43%
35 3 68.24%
36 4 69.35%
37 2 69.92%
38 2 70.51%
39 2 71.11%
41 1 71.42%
42 2 72.07%
43 4 73.40%
44 2 74.07%
45 1 74.42%
46 4 75.84%
47 2 76.56%
48 2 77.30%
49 1 77.68%
52 2 78.48%
54 1 78.90%
55 1 79.32%
56 3 80.62%
57 2 81.50%
58 2 82.39%
59 1 82.85%
60 1 83.31%
61 2 84.25%
62 2 85.21%
63 1 85.69%
64 1 86.19%
67 1 86.70%
70 1 87.24%
75 1 87.82%
78 2 89.02%
87 1 89.69%
90 1 90.39%
91 1 91.09%
97 2 92.58%
104 1 93.39%
113 1 94.26%
115 1 95.14%
120 1 96.07%
124 1 97.02%
127 1 98.00%
128 1 98.99%
131 1 100.00%
choosing guess 3.........................................
best guess moped (39) using prefix [serai blunt]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 3934 30.33%
2 1101 47.30%
3 405 56.67%
4 247 64.28%
5 148 69.99%
6 91 74.20%
7 74 78.19%
8 51 81.34%
9 33 83.63%
10 28 85.78%
11 20 87.48%
12 16 88.96%
13 20 90.97%
14 6 91.61%
15 6 92.31%
16 6 93.05%
17 8 94.09%
18 4 94.65%
19 3 95.09%
20 3 95.55%
21 1 95.71%
22 5 96.56%
23 2 96.92%
24 2 97.29%
26 1 97.49%
28 2 97.92%
29 1 98.14%
30 2 98.60%
34 1 98.87%
35 1 99.14%
36 1 99.41%
37 1 99.70%
39 1 100.00%
choosing guess 4.........................................
best guess gawcy (15) using prefix [serai blunt moped]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 8318 64.12%
2 1086 80.87%
3 325 88.38%
4 146 92.88%
5 55 95.00%
6 34 96.58%
7 17 97.49%
8 10 98.11%
9 12 98.94%
10 4 99.25%
11 5 99.68%
13 1 99.78%
14 1 99.88%
15 1 100.00%
choosing guess 5.........................................
best guess fehme (7) using prefix [serai blunt moped gawcy]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 10184 78.51%
2 848 91.58%
3 201 96.23%
4 64 98.20%
5 24 99.13%
6 13 99.73%
7 5 100.00%
choosing guess 6.........................................
best guess amoks (5) using prefix [serai blunt moped gawcy fehme]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 11358 87.56%
2 595 96.73%
3 87 98.74%
4 22 99.42%
5 15 100.00%
choosing guess 7.........................................
best guess ajiva (4) using prefix [serai blunt moped gawcy fehme amoks]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 11994 92.46%
2 411 98.80%
3 40 99.72%
4 9 100.00%
choosing guess 8.........................................
best guess dusts (3) using prefix [serai blunt moped gawcy fehme amoks ajiva]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 12364 95.31%
2 274 99.54%
3 20 100.00%
choosing guess 9.........................................
best guess aahed (3) using prefix [serai blunt moped gawcy fehme amoks ajiva dusts]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 12364 95.31%
2 274 99.54%
3 20 100.00%
choosing guess 10.........................................
best guess aahed (3) using prefix [serai blunt moped gawcy fehme amoks ajiva dusts aahed]
SIZE N PERCENT (of words in a bucket of this size or less)
---- ----- -------
1 12364 95.31%
2 274 99.54%
3 20 100.00%
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment