Wordle is a simple-to-understand game that chooses a secret five-letter English word, and then asks you to guess it. If your guess has letters in common with the secret word, you get a yellow square if it's in the wrong position, and a green square if it's in the right position. It's the classic Bagels Pico Fermi / Mastermind / Bulls and Cows (which is the first implementation of this concept I was able to find) feedback system when trying to guess a secret sequence. And when any game gets the widespread popularity that Wordle got, there will absolutely be game variants with varying degrees of quality. I want to focus in on two - Nerdle and Absurdle.
Absurdle is an adversarial version of Wordle - Absurdle will dynamically change the chosen word to make it as hard as possible for you to get it. In return, you get an infinite number of guesses. This makes it interesting, but not replayable - the same moves in the same order will win every time.
Nerdle is a version of Wordle that uses simple equations instead of words - a valid, eight-character equation is chosen, and your goal is to guess what it is. Your "letters" are the digits 0 through 9, the four standard operations (+, -, *, and ÷), and the equals sign. There are a few additional rules, but the important one for our purposes is that the equation is set up in an "expression = number" format, so equations like "15 = 60 - 45" and "10 - 8 = 7 - 5" aren't valid. It's called Nerdle because math is for nerds, I guess.
So here's the question. If there was an adversarial version of Nerdle that tried to dynamically change the secret equation to give you the least information possible, how would we solve it? What would be the best technique to find a solution?
So, one approach to this would be to start exploring the space of all possible valid equations. This is definitely a task for a Python script - a basic script could simply iterate through all ~7,000,000,000 possible permutations of these 15 characters in a 8 character sequence and evaluate whether they are mathematically valid. A more complicated script could eliminate lots of those cases by only allowing one equals sign, not allowing adjacent operations, not allowing numbers to start with 0, etc. But I'm more interested in what we can do without brute forcing it.
Let's assume that the adversarial algorithm tries to give us the least information possible. If we type in a guess, it will change its secret equation so that it can give us less information, and it'll keep doing it as long as possible. That gives us a general starting point - maybe it's true that any equation we choose for our first guess is going to have nothing in common with the answer, except for the mandatory equals sign.
So, here's what that would look like. If we start with my standard Nerdle opener, "12+35=47", the best case for the algorithm is to return something without 1, 2, 3, 4, 5, 7, or +, and with the equals sign in a different place. Does such an equation exist? Well, with a little thought, we can see that the trivial equation "9999*0=0" satisfies those conditions, so the algorithm will be able to achieve its best case scenario of giving us the least information possible.
But it has actually given us a lot of critical information. It's told us that 1, 2, 3, 4, 5, 7, and + appear nowhere in its equation, and that the equals sign must be in some place other than the 6th slot. The only tools we're left with are 6, 8, 9, 0, -, *, and ÷.
Another angle we can explore here is that there's only a few places the equals sign can be. The equation must be of the form "Expression = number", so we're limited by how big the number on the right can be. It could be a one-digit number (such as in the case of "10-2-3=5"), a two-digit number (such as "10+20=30", or a three-digit number ("80*4=320"). But can it be a four-digit number? It would have to take the form of "#*#=####" - we only have three characters to make a four-digit number. And without exponents, factorials, or up arrows, our best bet is multiplication, but we can already see that that won't work. When multiplying integers, the product can only have as many digits as the two factors combined. So there's exactly three places that the equals sign can be. And using our earlier method, that means we can force it into being in a particular place with two calculated guesses. It also means that there's no way we'll be able to win without at least three guesses.
So now we've got some proven techniques and ideas:
- We can eliminate digits and operations with guesses.
- We can use two guesses to nail down the location of the equals sign.
- We have a starting lower bound for this problem of 3 guesses.
- We should try to choose a solution that we like, and then try to force it onto the algorithm by eliminating everything else, as opposed to a top-down approach.
- We should try to use multiplication and division instead of addition or subtraction - it forces the product or dividend to have factors, which limits the kinds of numbers it can be. There are a lot of numbers that add up or subtract to get 562, but only a very small number that multiply or divide to get 562 (within our domain, of course).
- We should try to optimize for a solution with the fewest digits and operations, to minimize complexity and eliminate many possibilities immediately.
- We should try to optimize for a solution without the possibility of commutativity - "10+10=20" is better than "10+11=21", even though they have the same digits and operations; the latter can also be written as "11+10=21", and the algorithm will gleefully mark us incorrect no matter which one we choose first.
