Word Peaks is a neat little word puzzle by Devin Spikowski. It's challenging but not overwhelming, and makes a nice example of how to develop an algorithm to solve the puzzle. My approach takes a lot from the treatment by 3Blue1Brown, but I'll look at a variety of different ways of solving it.

The code for my solution is available on my own Git server, and on Codeberg.

Word Peaks

The puzzle is very similar to the Wordle puzzle, in that you have to guess a five-letter word in as few tries as you can. After each guess, you get some clues that help you refine your guess. But rather then telling you which letters are correct (as in Wordle), Word Peaks tells you whether each letter is before or after the corresponding letter in the target word.

For instance, using the puzzle in the header image of this post, the target word is "greet" and my first guess was "mines". The response to my guess shows that the first letter of the target word comes before "m" in the alphabet, the second letter of the target word comes after "i" in the alphabet, and the fourth letter of the target is "e".

Solving Word Peaks

My overall approach is to follow the original puzzle's format. I start with a large set of possible words that could be the solution. From that set, I pick the "best" word then test it against the target. Based on the result of that challenge, I can reduce the number of candidate words. I pick the best word from that reduced set of candidates and go again, until I get the correct solution.

The interesting part of the programming challenge is coming up with a definition of "best" to allow solving the puzzle in as few guesses as possible.

(In this instance, I don't worry about the limit of six guesses, but I am trying to minimise the number of guesses to find the solution.)

Representing a puzzle

As is usual with these things, the first thing to do is find a representation for the puzzle and all things related to it. A good starting place is the interface the original puzzle presents.

We need two main things. One is the bounds on the next guess, the other is the response to each guess. We could record things like the number of guesses or previous guesses, but I don't think we need that for finding the next guess; I'll not include them let, but will revise that choice if needed.

After each guess we get a result, so we need to represent that. As there are only three possible values for each element in the result, I use an Enum to ensure I don't get confused.

class TestResult(IntEnum):
    TOO_HIGH = 1
    CORRECT = 2
    TOO_LOW = 3

For user convenience, I include a little syntactic sugar for entering results. These functions allow me to enter responses as text strings (by comparison or colour) and have them converted to the respective Enums.

def canonicalise_response_element(resp):
    match resp:
        case TestResult.TOO_HIGH | 'H' | 'h' | 'B' | 'b':
            return TestResult.TOO_HIGH
        case TestResult.TOO_LOW | 'L' | 'l' | 'O' | 'o':
            return TestResult.TOO_LOW
        case TestResult.CORRECT | 'C' | 'c' | 'G' | 'g':
            return TestResult.CORRECT

def canonicalise_response(response):
    return [canonicalise_response_element(r) for r in response]

A puzzle knows the bounds on each letter, and can include a test result to narrow those bounds. It can also tell if a word is within the current bounds. That bundle of data and behaviour suggests representing it as an object.

As the bounds for each letter follow the same logic, I create an object for each letter bounds. This is the Bounds class.

class Bounds():
    def __init__(self):
        self.lower_bound = 'a'
        self.upper_bound = 'z'
    
    def in_bounds(self, probe):
        return self.lower_bound <= probe <= self.upper_bound

    def include_test_result(self, probe, result):
        match result:
            case TestResult.TOO_HIGH:
                self.upper_bound = chr(ord(probe) - 1)
            case TestResult.TOO_LOW:
                self.lower_bound = chr(ord(probe) + 1)
            case TestResult.CORRECT:
                self.upper_bound = probe
                self.lower_bound = probe
        return self
    
    def show_bounds(self):
        return f"[{self.lower_bound}-{self.upper_bound}]"

Using the Bounds, I can create a PuzzleState class.

class PuzzleState():
    def __init__(self):
        self.bounds = [Bounds() for _ in range(5)]

    def in_bounds(self, probe):
        return all(b.in_bounds(p) for b, p in zip(self.bounds, probe))
        
    def include_test_result(self, probe, results):
        for b, p, r in zip(self.bounds, probe, results):
            b.include_test_result(p, r)
        return self

    def show_bounds(self):
        return ''.join(b.show_bounds() for b in self.bounds)

I also need a function that will generate the correct response for a given guessed word. This needs to know the probe word and the actual solution.

def respond_to_challenge_letter(probe, solution):
    if probe > solution:
        return TestResult.TOO_HIGH
    elif probe == solution:
        return TestResult.CORRECT
    else:
        return TestResult.TOO_LOW

def respond_to_challenge(probe, solution):
    return [respond_to_challenge_letter(p, s) for p, s in zip(probe, solution)]

The final bit of setup is to have lists of words for the program to work with. The word lists for Word Peaks are in its source code. I also use the word lists for Wordle, obtained from an old commit of the 3Blue1Brown repository.

WORDS = [w.strip() for w in open('wordle_possible_words.txt').readlines()]
with open('word-peaks-dictionary-filtered.json') as f:
    wp_words = json.load(f)
WORDS = list(sorted(set(WORDS + wp_words)))
LEN_WORDS = len(WORDS)

TARGETS = [w.strip() for w in open('wordle_possible_answers.txt').readlines()]
with open('word-peaks-targets-filtered.json') as f:
    wp_targets = json.load(f)
TARGETS = list(set(TARGETS + wp_targets))

Baseline solution: binary search

Given all the setup, now it's time to solve the puzzle.

My first attempt, as a baseline, is good old binary search. I have a sorted list of words that could be the solution. I find the word in the middle of that list and try that. That should hopefully halve (or better) the number of candidate words.

Let's work that through slowly, step by step, to see how to implement it. Let's imagine the target word is "greet".

To start with, I have no information, so I pick the word in the middle of the list of candidate words and use that as my initial guess.

puzzle = PuzzleState()

candidate_words = WORDS
candidates_len = len(candidate_words)
guess = candidate_words[candidates_len // 2]

The guess is "louse". Using that as a challenge

response1 = respond_to_challenge('louse', 'greet')

gives the response [TOO_HIGH, TOO_LOW, TOO_HIGH, TOO_HIGH, TOO_LOW] .

I include that response in the puzzle and find the candidate words that remain.

puzzle.include_test_result('louse', response1)
candidate_words = [w for w in candidate_words if puzzle.in_bounds(w)]
candidates_len = len(candidate_words)
guess = candidate_words[candidates_len // 2]

There are 894 candidate words, and the middle one is "dsobo" (whatever that means). The response to that challenge is [TOO_LOW, TOO_HIGH, TOO_HIGH, TOO_LOW, TOO_LOW] .

Applying that pattern to the puzzle, then filtering, results in 46 candidate words. The middle is "grams".

response2 = respond_to_challenge('dsobo', 'greet')
puzzle.include_test_result('dsobo', response2)
candidate_words = [w for w in candidate_words if puzzle.in_bounds(w)]
candidates_len = len(candidate_words)
guess = candidate_words[candidates_len // 2]

and so on. The fifth guess is the correct one.

Automating the solving

Now I have the basic idea of how to solve the puzzle, let's automate it and write a procedure that will solve a puzzle and tell me how many guesses it took.

def solve_word_peaks_median(target):
    candidate_words = WORDS
    guess = ''
    num_guesses = 0
    puzzle = PuzzleState()
    while guess != target:
        cand_len = len(candidate_words)
        guess = candidate_words[cand_len // 2]
        pattern = respond_to_challenge(guess, target)
        num_guesses += 1
        puzzle.include_test_result(guess, pattern)
        candidate_words = [w for w in candidate_words if puzzle.in_bounds(w)]
    return num_guesses

If I use that to solve every TARGET word, I find it takes on average 4.04 guesses, and never more than six.

This is, frankly, unexpectedly good. There are just under 13,000 known words. A simple binary search should take about $log_2 13000 \simeq 14$ guesses, not the 4 we get. The four guess average suggests that the solver is reducing the space of possible words by about a factor of 7 with each guess, rather than a factor of two.

The reason for this is fairly easy to see. When I make a guess, I pick a word in about the middle of the alphabet, based on the first letter of the word. But that guess also gives information about the other letters in the word, narrowing down the range of possible answers even more than just relying on the first letter alone.

That suggests a way we could do better. Rather than looking at just the first letter of a word, why not look at all the letters of a word?

All-letter binary search

If we sort WORDS by the first letter, the middle word is "louse". If we sort by the second letter, the middle word is "blaze".

for i in range(5):
    print(i, list(sorted(WORDS, key=lambda w: w[i]))[LEN_WORDS // 2])

0 louse
1 blaze
2 ramus
3 groks
4 owler

If we take the middle letter while sorting by that letter, we get the "l" from "louse", the "l" from "blaze" and so on, generating the first guess of "llmkr". Which may be a powerful guess, but isn't a valid word.

I need a way of finding the valid word that minimises the "distance" from this optimal collection of letters. For that, I need to count how far each letter is from the middle letter.

If I look at the second letters and look at them, I find that the first 2265 letters are "a", the next 81 are "b", and so on. Overall, I get this distribution (using Python's convention of exclusive numbering for the end of ranges):

This shows that an "l" closest to the centre of the list of letters. The closest "k" to the middle is 117 steps away (the word "ukase") and the closest "m" is 583 steps away (the word "amahs"). That means that words like "ukase" would score 117 and words like "amahs" would score 583, for just their second letter.

If I find the score for each letter in the word, the best guess is the word that minimises this total score. For the initial set of words, that is "links" with a score of 627.

Implementing all-letter binary search

Now I have the idea, it's time to implement it.

First is to write a function that generates a table like the above, giving the penalty for each letter. This assumes that letter_count is a Counter that stores how many examples there are of each letter.

def penalties_for_letters(letter_count):
    total_letter_count = letter_count.total()
    midpoint = total_letter_count // 2
    penalties = {}
    running_total = 0

    for l in sorted(letter_count):
        prev_running_total = running_total
        running_total += letter_count[l]
        if running_total <= midpoint:
            penalties[l] = midpoint - running_total
        else: 
            if prev_running_total < midpoint:
                penalties[l] = 0
            else:
                penalties[l] = prev_running_total - midpoint + 1
    return penalties

Given the penalties for each letter, I can find the penalty for a word by adding the penalty for each letter.

def penalty_for_word_by_letters(word, penalties):
    return sum(ps[l] for l, ps in zip(word, penalties))

From that, I can create a procedure that solves a puzzle, using the all-letter binary score. It follows the same pattern as before, with the next guess being the candidate word with the lowest score.

def solve_word_peaks_letter_difference(target):
    candidate_words = WORDS
    guess = ''
    num_guesses = 0
    puzzle = PuzzleState()

    while guess != target:

        letter_counts = [collections.Counter(ls) for ls in zip(*candidate_words)]
        penalties = [penalties_for_letters(lc) for lc in letter_counts]
        guess = min(candidate_words, key=lambda w: penalty_for_word_by_letters(w, penalties))

        pattern = respond_to_challenge(guess, target)
        num_guesses += 1
        # print(guess, pattern)
        puzzle.include_test_result(guess, pattern)
        candidate_words = [w for w in candidate_words if puzzle.in_bounds(w)]
        # print(len(candidate_words))
    return num_guesses

When I use this procedure for all the valid solution words, this procedure takes 3.59 guesses on average, a healthy improvement over using the median word. The figure below shows the distribution of the number of guesses for the two methods.

This shows a significant improvement over the first version of the solver, with the average number of guesses falling from 4.0 guesses to 3.6.

There are still improvements to be made, but that will come in the next part of this exploration.

Code

The implementation of this post is available on my Git server and on Codeberg. The main code is in word_peaks_median_word_letter.py and a notebook that uses it is word_peaks_median_word_letter.ipynb (and word_peaks_median_word_letter.md ).