solve.c

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

#define DELIM " \n\r"

enum op {OP_RET, OP_MAD, OP_LDI, OP_LDC, OP_SWP};

static const long pow10[] = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
};

static int
execute(const char *ops, const long *constants)
{
    long a = 0;
    long b = 0;
    long c = 0;
    long x = 0;
    long tmp;
    for (;; ops++) {
        switch ((enum op)*ops) {
            case OP_RET:
                return a == x;
            case OP_MAD:
                a += pow10[b] * c;
                b--;
                break;
            case OP_LDI:
                b = *++ops;
                break;
            case OP_LDC:
                c = constants[(int)*++ops];
                break;
            case OP_SWP:
                tmp = a;
                a = x;
                x = tmp;
                break;
        }
    }
}

static char *
compile_word(char *ops, const char *word)
{
    int len = strlen(word);
    *ops++ = OP_LDI;
    *ops++ = len - 1;
    for (int i = 0; i < len; i++) {
        *ops++ = OP_LDC;
        *ops++ = word[i] - 'A';
        *ops++ = OP_MAD;
    }
    return ops;
}

void
disassemble(char *ops)
{
    for (;; ops++) {
        switch ((enum op)*ops) {
            case OP_RET:
                puts("ret");
                return;
            case OP_MAD:
                puts("mad");
                break;
            case OP_LDI:
                printf("ldi %d\n", *++ops);
                break;
            case OP_LDC:
                printf("ldc %c\n", 'A' + *++ops);
                break;
            case OP_SWP:
                puts("swp");
                break;
            default:
                printf("INVALID:%d\n", *ops);
        }
    }
}

static long
solve(const char *vars, const char *ops, long *constants, unsigned avail)
{
    int v = *vars;
    if (!v) {
        return execute(ops, constants);
    } else {
        for (int i = 0; i < 10; i++) {
            unsigned bit = 1u << i;
            if (avail & bit) {
                constants[v - 'A'] = i;
                long r = solve(vars + 1, ops, constants, avail & ~bit);
                if (r)
                    return r;
            }
        }
    }
    return 0;
}

int
main(void)
{
    char line[4096];
    fgets(line, sizeof(line), stdin);

    /* Compiled representation of the puzzle */
    char vars[11] = {0};
    int nvars = 0;
    static char program[1024UL * 1024];

    /* Compile puzzle into a program */
    char seen[26] = {0};
    char *ops = program;
    for (char *tok = strtok(line, DELIM); tok; tok = strtok(0, DELIM)) {
        switch (tok[0]) {
            case '+':
                break;
            case '=':
                *ops++ = OP_SWP;
                break;
            default:
                for (char *c = tok; *c; c++) {
                    int i = *c - 'A';
                    if (!seen[i]) {
                        seen[i] = 1;
                        vars[nvars++] = *c;
                    }
                }
                ops = compile_word(ops, tok);
                break;
        }
    }
    *ops = OP_RET;
    //disassemble(program);

    /* Run solver */
    long constants[26] = {0};
    if (solve(vars, program, constants, -1U))
        for (char *v = vars; *v; v++)
            printf("%c:%ld%c", *v, constants[*v - 'A'], " \n"[!v[1]]);
}