Generation of Equations

[mikeynic]

Hi, please could you explain how your code works that creates equations for the "use suggestion" button? Thanks in advance.

[TonyBUK]

Hi,

No problem, apologies if this is pitched at the wrong level. If you want this more as a code walkthrough or something of that ilk, let me know.

So at the core of it is basically a nested series of loops, with one loop nesting for each character position, and at its most basic level, it's basically going to try every combination of numbers/operators until it finds a balanced mathematical expression.

Basically:

FOR each number/operator in position 1

  FOR each number/operator in position 2

    ...

    FOR each number/operator in position N

      IF the Equation is Balanced, break out of all of the loops with the solution, otherwise carry on

    END FOR

    ...

END FOR

END FOR

Because nesting a dynamic number of loops is a bit of a pain iteratively (you're either hard coding the nesting of loops, or you're having to store some sort of stack of meta-data), my solution uses recursion to achieve this, using a DFS (Depth First Search), but really it just boils down to each depth of the recursion corresponding to level of the nested loop example shown above. This is all performed within nerdleSolver.js in the function generateNewSuggestionRecursive.

The issue with this approach is that it's very time consuming, as for the standard Nerdle game, you have 8 positions, and if you try 0123456789+-/*= in all positions, that's 14^8 total permutations that could be checked, which would take far too long.

So there's a few tricks it employs to try and reduce which numbers/operators it tries in each position.

1. We know the general form of Nerdle is: [Mathematical Expression] = [Constant Value].
   a. This means if our solution already contains a "=" sign, then we only need to check values which are legal for a number (so =+/* can be ignored)
2. As the game progresses, the processResult function within nerdleSolver.js is actively reducing which numbers/operators are legal in which positions, and runs each time you colour in the results Nerdle provides, i.e. if we know 1 is the correct value for position 1, then there's no point checking 023456789+-/* in that position.
   a. I do go into a fair amount of detail on how I determine what values are legal in which position on the main page: https://github.com/TonyBUK/NerdleSolver
   Specifically everything below the text : "Secondly, the part you're here for, the solver..."

The final aspect of the function, and probably the most convoluted aspect (and where the bulk of the code is), is trying to manage the quality of the results. The problem with the brute force method is you may end up with an answer like: 000000=0 or 0+0+-0=0, where the answer is technically balanced, but would be an awful guess to make in the game. In fact by hand, my usual openers are:

0+12/3=4
9*8-7=65

What makes these guesses good is the number of unique items in the list (i.e. aside from the "=" sign, there's no repeated numbers/operators). So what it'll actually do for each level of the Loop is:

FOR each number/operator in position 1

  Sort the Legacy numbers/operators for position 2 such we process numbers/operators not yet seen first, then numbers/operators we have already seen.

  FOR each number/operator in position 2

    ...

    Sort the Legacy numbers/operators for position N such we process numbers/operators not yet seen first, then numbers/operators we have already seen.

    FOR each number/operator in position N

      IF the Equation is Balanced, break out of all of the loops with the solution, otherwise carry on

    END FOR

    ...

END FOR

END FOR

What this will hopefully do is to reduce how many answers are suggested that have repetition.

Additionally, we can prioritise "genuine" Nerdle puzzles over custom ones. So by that I mean we can apply further constraints that Nerdle outlines here: https://faqs.nerdlegame.com

The main one is Nerdle puzzles will never have negative literals. i.e.

1+2-3=-1

But the Nerdle Engine itself does allow this. Meaning if it's a custom puzzle, we have to suggest results that the Nerdle Engine itself will accept as balanced, but if it's a regular Nerdle game, we know that whilst some results are technically legal, Nerdle will never have it as an actual puzzle.

To try and accommodate this without having to tweak any code, the suggestion generator will actually try suggesting solutions up to 3 times.

1. Suggest only "Good" solutions, these will be only allowing solutions that meet the Nerdle FAQ.
2. Suggest "Good/OK" solutions, these will now also allow "NOP" Arithmetic (i.e. 10*0+0=0)
3. Suggest "Good/OK/Naff" solutions, which will now also allow Unary abuse (i.e. +-1--1=0)

I was too lazy to make the subsequent guesses trim the guesses already made, mostly as I don't think anyone playing custom games would use the tool, so as it compromises on solution quality, it will end up repeating alot of the work it's already done.

So once all that's done, all that's left is for each suggested solution, test it. Is the left side of the "=" a legal expression (i.e. would Nerdle allow it), same with the right side, and do they produce equivalent values. If yes, then we've found a suggestion, if not, carry on with the nested loop.

Hope this helps,

Tony.

[mikeynic]

I don't know Javascript very well, so that cleared up a lot of questions I had! Thank you very much for taking the time to explain your program.