Generate all possible equations with 10 characters

Question

Nerdle is a Wordle variant, in which instead of words, the answers are equations. Each equation entered in the game must be a valid one.

Examples: 13³-1=2196, (1/1)²*8=8, (((3)))²=9

The task is to generate and output to a .txt file, one equation per line, all possible 10 character equations that could be an answer for the game (specifically the Maxi Nerdle) as fast as possible (note that the code should be limited to 100KB to avoid hardcoding).

The possible symbols for a Maxi Nerdle equation are:

• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /, ², ³, ), (, =

The rules that make an equation a possible answer to the game, besides being mathematically true, are:

• There are no leading zeros
• There are no lone zeros (There can't be a +0 in the equation, for example)
• There are no operators in sequence, that is, +, -, *, / can't be adjacent to each other (+++----1=1, for example)
• The right-hand side of the equation must be a non-negative integer
• Operations must be explicit, that is, 9(10-8)=18 is not valid, for example, as there should be a * between 9 and (
• There can only be one = symbol

Also note that commutativity doesn't apply. If the order of the numbers changes, it must be treated as a different equation.

Expected output

For 10 characters long equations with the Maxi Nerdle symbols, there should be 2,177,017 equations. They can be viewed here (this was generated in 1 hour with a simple Python script).

Score

As this is a fastest-code challenge, the score will be based on the time taken to run it on my computer (Windows 10). Here are my specs:

• Intel(R) Core(TM) i5-9300H CPU 2.40GHz
• 8 GB RAM with 2667 MHz speed

Please include instructions for how to compile/run your code.

Answer 1

C, about 6.3 seconds on my M1 MacBook Pro

Here's a start. I think there is a lot more optimisation to do here.

All credit for the recursive descent parser to @Henrik. I have lightly modified it to operate on doubles instead of ints, and to calculate 2nd and 3rd powers.

• Compile with cc -O3 nerdle.c -o nerdle
• Run as time ./nerdle. Generates a file nerdle.txt in the current directory.

On MacOS, the default cc is clang. -O3 sped up runtime by a factor of 4, over default optimisation. This should compile just as well with gcc.

The gen_*() functions recursively generate all valid expressions. Then these are evaluated with a recursive descent parser, and output if mathematically true.

I have taken care to output the results in the same order as NerdleMaxi.txt, so they may easily be verified with diff / cmp.

This code is not pretty, and would benefit from a good deal of deodorising.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

char * expressionToParse;
FILE *fp;

char peek()
{
    return *expressionToParse;
}

char get()
{
    return *expressionToParse++;
}

double expression();

double number()
{
    double result = get() - '0';
    while (peek() >= '0' && peek() <= '9')
    {
        result = 10*result + get() - '0';
    }
    return result;
}

double factor()
{
    if (peek() >= '0' && peek() <= '9')
        return number();
    else if (peek() == '(')
    {
        get(); // '('
        double result = expression();
        get(); // ')'
        return result;
    }
    else if (peek() == '-')
    {
        get();
        return -factor();
    }
    return 0; // error
}

double expon()
{
    double result = factor();
    while (peek() == 's' || peek() == 'c')
        if (get() == 's')
            result *= result;
        else
            result *= (result * result);
    return result;
}

double term()
{
    double result = expon();
    while (peek() == '*' || peek() == '/')
        if (get() == '*')
            result *= expon();
        else
            result /= expon();
    return result;
}

double expression()
{
    double result = term();
    while (peek() == '+' || peek() == '-')
        if (get() == '+')
            result += term();
        else
            result -= term();
    return result;
}



static void gen_nz_digit(int level, int br_level, char * buf, int ndigits);
static void gen_digit(int level, int br_level, char * buf, int ndigits);
static inline void gen_oper(int level, int br_level, char * buf, int ndigits);
static inline void gen_squared(int level, int br_level, char * buf, int ndigits);
static inline void gen_cubed(int level, int br_level, char * buf, int ndigits);
static inline void gen_open(int level, int br_level, char * buf, int ndigits);
static inline void gen_close(int level, int br_level, char * buf, int ndigits);
static inline void gen_equals(int level, int br_level, char * buf, int ndigits);

static void
gen_nz_digit (int level, int br_level, char * buf, int ndigits)
{
    int i;

    if (level >= 8) {
        return;
    }

    int next_level = level + 1;
    
    for (i = 1; i < 10; i++) {
        buf[level] = '0' + i;
        gen_equals(next_level, br_level, buf, 0);
        gen_digit(next_level, br_level, buf, 1);
        gen_oper(next_level, br_level, buf, 0);
        gen_squared(next_level, br_level, buf, 0);
        gen_cubed(next_level, br_level, buf, 0);
        if (br_level > 0) {
            gen_close(next_level, br_level, buf, 0);
        }
    }
}

static void
gen_digit (int level, int br_level, char * buf, int ndigits)
{
    int i;

    if (level >= 8) {
        return;
    }
    if (ndigits >= 4) {
        return;
    }

    int next_level = level + 1;

    for (i = 1; i < 10; i++) {
        buf[level] = '0' + i;
        gen_equals(next_level, br_level, buf, 0);
        gen_digit(next_level, br_level, buf, ndigits + 1);
        gen_oper(next_level, br_level, buf, 0);
        gen_squared(level +1, br_level, buf, 0);
        gen_cubed(next_level, br_level, buf, 0);
        if (br_level > 0) {
            gen_close(next_level, br_level, buf, 0);
        }
    }
    buf[level] = '0';
    gen_equals(next_level, br_level, buf, 0);
    gen_digit(next_level, br_level, buf, ndigits + 1);
    gen_oper(next_level, br_level, buf, 0);
    gen_squared(level +1, br_level, buf, 0);
    gen_cubed(next_level, br_level, buf, 0);
    if (br_level > 0) {
      gen_close(next_level, br_level, buf, 0);
    }

}

static inline void
gen_oper (int level, int br_level, char * buf, int ndigits)
{
    if (level >= 7) {
        return ;
    }

    int next_level = level + 1;

    buf[level] = '-';
    gen_nz_digit(next_level, br_level, buf, 0);
    gen_open(next_level, br_level, buf, 0);

    buf[level] = '+';
    gen_nz_digit(next_level, br_level, buf, 0);
    gen_open(next_level, br_level, buf, 0);

    buf[level] = '*';
    gen_nz_digit(next_level, br_level, buf, 0);
    gen_open(next_level, br_level, buf, 0);

    buf[level] = '/';
    gen_nz_digit(next_level, br_level, buf, 0);
    gen_open(next_level, br_level, buf, 0);
}


static inline void
gen_squared (int level, int br_level, char * buf, int ndigits)
{
    if (level >= 8) {
        return;
    }

    int next_level = level + 1;

    buf[level] = 's';
    if (level >= 3) {
        gen_equals(next_level, br_level, buf, 0);
    }
    gen_oper(next_level, br_level, buf, 0);
    if (br_level > 0) {
        gen_close(next_level, br_level, buf, 0);
    }
}
        
static inline void
gen_cubed (int level, int br_level, char * buf, int ndigits)
{
    if (level >= 8) {
        return;
    }

    int next_level = level + 1;

    buf[level] = 'c';
    if (level >= 2) {
        gen_equals(next_level, br_level, buf, 0);
    }
    gen_oper(next_level, br_level, buf, 0);
    if (br_level > 0) {
        gen_close(next_level, br_level, buf, 0);
    }
}
        
static inline void
gen_open (int level, int br_level, char * buf, int ndigits)
{
    if (level >= 7) {
        return;
    }

    int next_level = level + 1;
    buf[level] = '(';
    br_level++;
    gen_nz_digit(next_level, br_level, buf, 0);
    gen_open(next_level, br_level, buf, 0);
}


static inline void
gen_close (int level, int br_level, char * buf, int ndigits)
{
    if (level >= 8) {
        return;
    }

    int next_level = level + 1;

    buf[level] = ')';
    br_level--;
    gen_equals(next_level, br_level, buf, 0);
    gen_oper(next_level, br_level, buf, 0);
    gen_squared(next_level, br_level, buf, 0);
    gen_cubed(next_level, br_level, buf, 0);
    if (br_level > 0) {
        gen_close(next_level, br_level, buf, 0);
    }
}

static inline int
int_len (int n) {
    if (n < 10) {
        return 1;
    } else if (n < 100) {
        return 2;
    } else if (n < 1000) {
        return 3;
    } else if (n < 10000) {
        return 4;
    } else if (n < 100000) {
        return 5;
    } else {
        return 6;
    }
}
    
static inline void
gen_equals (int level, int br_level, char * buf, int ndigits)
{
    double result;
    double int_part;
    double frac_part;
    
    if (br_level > 0) {
        return;
    }
    buf[level] = '\0';
    expressionToParse = buf;
    result = expression();
    frac_part = modf(result, &int_part);
    if (frac_part == 0) {
        int rhs = (int)int_part;
        if (rhs >= 0) {
            if (level + int_len(rhs) == 9) {
            char out_str[20];
        char *ptr = out_str;
        char tmp_str[20];
        strcpy(out_str, buf);
        while (NULL != (ptr = strchr(ptr, 's'))) {
            strcpy(tmp_str, ptr + 1);
            sprintf(ptr, "²%s", tmp_str);
        }
        ptr = out_str;
        while (NULL != (ptr = strchr(ptr, 'c'))) {
            strcpy(tmp_str, ptr + 1);
            sprintf(ptr, "³%s", tmp_str);
        }
               
            fprintf(fp, "%s=%d\n", out_str, rhs);
            }
        }
    }
}

int
main (int argc, char ** argv)
{
    fp = fopen("nerdle.txt", "w");
    char buffer[20] = "";
    gen_nz_digit(0, 0, buffer, 0);
    gen_open(0, 0, buffer, 0);
    fclose(fp);
}