Birthday Puzzle 2022!

It's time for another birthday puzzle! This year, my birthday puzzle was an entire Pokémon Romhack - I don't want to get into too many specifics, but I made, start to finish, a very puzzle-centric Pokemon chapter. I've never done anything like that before, so it had a lot of puzzle ideas that had been building up in me for a while!

But, I couldn't resist also making something smaller in scope but wider in audience for a birthday puzzle. It's definitely simpler than many of its predecessors, but I enjoyed creating it all the same. I hope you enjoy solving it!

Sequence Differences (Diffsy Qs I)

 Years and years ago, back in my old Math League days, I came up with a trick to finding out the formulas of sequences. The problem type I'm talking about would give me a list of Xs and Ys in a table like this:

Wait, I need HTML for tables? Wow, okay.

X	1	2	3	4	5
Y	4	8	14	22	32

Oh my god, I thought I hated tables when I only knew of how awful they were in the context of word processors. HTML tables are so much worse.

Anyways, the problems would have a table like the one above and ask for the equation that generated those values, usually in the form of y = f(x). There aren't any convenient algorithms for this, so usually the student is expected to graph it, determine if it's a line or parabola, and use the appropriate equations. 

This problem is actually one of the few interesting math problems that a student might see in school. I categorize a lot of math taught in schools as a three step process: 

1. Remember the formula or algorithm that applies to this problem.

2. Apply the formula or algorithm and follow the steps.

3. Write down the result.

This problem gets an additional step; an analysis of the results, as simple as it may be. 

1. Remember the formula or algorithm that applies to this problem (Hm, when the problem looks like this, I have to graph the points on a Cartesian plane)

2. Apply the formula or algorithm and follow the steps. (Actually graph each point)

3. Analyze the results. (Check if the graphed points follow a line or a parabola)

4. Remember the formula or algorithm that applies to this problem (Remember the appropriate formulas for your graph)

5. Apply the formula or algorithm and follow the steps. (Use the appropriate formulas / plug 'n chug)

6. Write down the result (The formulas spit out this number for the slope and this number for the y-intercept, so I can put them in place of the m and the b and write down the equation)

Yeah, that additional analysis step is very simple, but it's one of two examples that come to mind in the math I learned as a kid that weren't completely algorithmic. (The other is triangle congruence, which was always a favorite of mine!) 

This analysis step is something I loved back then, because I could get around it with some thinking. Why bother graphing out all those points when you can just intuitively figure out whether the points will make a line or a parabola? (Well, because the teacher's going to take points away for not showing your work, that's why.)

So, how do you figure out whether it's a line or a parabola without graphing it? I came up with a method that I'm now going to retroactively call "Sequence Differences". I called them "subsequences" back then, but it turns out that that term is protected. I subtracted adjacent y values from each other to make a new sequence that had one fewer term. Let's see if I can get a table to illustrate that:

X	1	2	3	4	5
Y1	4	8	14	22	32
Y2	4	6	8	10

Eh, close enough. As you can see, the Y₂ sequence comes from 8 - 4, 14 - 8, 22 - 14, and 32 - 22. Upon seeing this, I thought "these numbers are all different, and lines have a constant slope, so it must be a parabola!" and went on to the next part of the problem. But isn't it interesting that the numbers are increasing in an arithmetic sequence? If I were to do another round of sequence differences here, 

X	1	2	3	4	5
Y1	4	8	14	22	32
Y2	4	6	8	10
Y3	2	2	2

we can see that the sequence is constant. Somehow, every time I performed a sequence difference, I decremented the degree of the source equation. The first equation was y = x² + x +2; the second can be solved to be y = 2x + 2, and the last is just y = 2. Looks... a bit familiar, doesn't it? The constant isn't the same, but it looks almost like we're taking the derivative to find the equations that describe our new sequences. There's a mystery there!

But, that's probably plenty for one day; it's definitely enough HTML tables for one day. All that remains is a name, and I think I've got a good one. Differential Equations are often abbreviated to Diff Eq, pronounced "Diffy Q", and this problem is about Differences (of) Sequences, so let's go with the almost cringeworthy Diffsy Q. Next time, a deep dive into the mechanics of Diffsy Qs!

Nerdle + Absurdle: A Theoretical Combination of Two Games

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.

Adding to that, I've got some intuition about this problem - nothing I can prove without a computer, but intuition is all we have when we're first approaching a problem like this. 

• 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.

That seems like a good stopping point for our groundwork for this problem. Next time, we'll get into making some initial guesses and then refining our strategy, and maybe retroactively trying to understand how and why these qualities are intuitively desirable. All that remains is a name for the problem, and it really writes itself: Absnerdle! Need a name for a problem and don't know what to pick? A lazy portmanteau always does the trick!