expr.c

// given a string of digits and a target integer, insert + and * operators
// between the digits until the resultant equation results in the target,
// printing the result. if no possible equation exists with the given string,
// print "No solution found"

// Ex: "123456" and 464 prints 12*34+56

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

int apply_op(int result, unsigned char op, int number) {
    switch (op) {
        case '+': return result + number;
        case '*': return result * number;
        default: return result;
    }
}

int solve_expr(const char *expr) {
    int result = 0;
    int number = 0;
    int prev_op = '+';
    unsigned char c = *expr;

    while (c) {
        switch (c) {
            case '0' ... '9':
                number = number * 10 + c - '0';
                break;
            default:
                result = apply_op(result, prev_op, number);
                prev_op = c;
                number = 0;
                break;
        }

        expr++;
        c = *expr;
    }

    return apply_op(result, prev_op, number);
}

void inc_seed(char *seed, int seed_len, int seed_max_v) {
    for (int i = 0; i < seed_len; ++i) {
        seed[i]++;

        if (seed[i] - '0' > seed_max_v) {
            seed[i] = '0';
        } else {
            return;
        }
    }
}

int main() {
    char *digits = "123456";
    int need = 464;

    const int ops_n = 3;
    const int ops[ops_n] = {0, '+', '*'};

    int digits_n = strlen(digits);

    int expr_max_len = digits_n + digits_n - 1;
    char expr[expr_max_len + 1]; // +1 for nul

    int seed_len = digits_n - 1;
    int seed_max_v = ops_n - 1; // 2
    char seed[seed_len]; // 00000
    char max_seed[seed_len]; // 22222

    for (int i = 0; i < seed_len; ++i) {
        seed[i] = '0';
        max_seed[i] = '0' + seed_max_v;
    }

    printf("seed: %.*s\n", seed_len, seed);
    printf("max_seed: %.*s\n", seed_len, max_seed);

    do {
        int pos = 0;

        for (int i = 0; i < digits_n; ++i) {
            unsigned char digit = digits[i];
            expr[pos++] = digit;

            if (seed[i]) { // possible to add op
                int op_id = seed[i] - '0';
                unsigned char op = ops[op_id];

                if (op) { // need op
                    expr[pos++] = op;
                }
            }
        }

        expr[pos] = 0;

        int result = solve_expr(expr);

        printf("%s = %d\n", expr, result);

        if (result == need) {
            printf("%s\n", expr);
            return 0;
        }

        inc_seed(seed, seed_len, seed_max_v);
    } while (memcmp(seed, max_seed, seed_len) != 0);

    printf("No solution found\n");
}

/*
% make 1 && ./1
cc     1.c   -o 1
seed: 00000
max_seed: 22222
123456 = 123456
1+23456 = 23457
1*23456 = 23456
12+3456 = 3468
1+2+3456 = 3459
1*2+3456 = 3458
12*3456 = 41472
1+2*3456 = 10368
1*2*3456 = 6912
123+456 = 579
1+23+456 = 480
1*23+456 = 479
12+3+456 = 471
1+2+3+456 = 462
1*2+3+456 = 461
12*3+456 = 492
1+2*3+456 = 465
1*2*3+456 = 462
123*456 = 56088
1+23*456 = 10944
1*23*456 = 10488
12+3*456 = 6840
1+2+3*456 = 2736
1*2+3*456 = 2280
12*3*456 = 16416
1+2*3*456 = 4104
1*2*3*456 = 2736
1234+56 = 1290
1+234+56 = 291
1*234+56 = 290
12+34+56 = 102
1+2+34+56 = 93
1*2+34+56 = 92
12*34+56 = 464
12*34+56
*/