solve.c

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

#define DELIM " \n\r"

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

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

static int
execute(const char *ops, const char *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:
                c = constants[(int)*++ops];
                a += pow10[b] * c;
                b--;
                break;
            case OP_LDI:
                b = *++ops;
                break;
            case OP_SWP:
                tmp = a;
                a = x;
                x = tmp;
                break;
        }
    }
}

static char *
compile_word(char *ops, const char *word)
{
    *ops++ = OP_LDI;
    char *imm8 = ops++;
    int len = 0;
    for (const char *c = word; *c; c++, len++) {
        *ops++ = OP_MAD;
        *ops++ = *c - 'A';
    }
    *imm8 = len - 1;
    return ops;
}

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

static void
solve(const char *vars, const char *ops, char *constants, unsigned avail)
{
    int v = *vars;
    if (!v) {
        if (execute(ops, constants)) {
            for (int i = 0; i < 26; i++)
                if (constants[i] != 11)
                    printf("%c:%d ", i + 'A', constants[i]);
            putchar('\n');
        }
    } else {
        for (int i = 0; i < 10; i++) {
            unsigned bit = 1u << i;
            if (avail & bit) {
                constants[v - 'A'] = i;
                solve(vars + 1, ops, constants, avail & ~bit);
            }
        }
    }
}

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

    /* Compiled representation of the puzzle */
    char constants[26] = {
        11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
        11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
    };
    char program[4096];

    /* Compile puzzle into a program */
    int nvars = 0;
    char vars[11] = {0};
    char *ops = program;
    unsigned long seen = 0;
    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';
                    unsigned long bit = 1UL << i;
                    if (!(seen & bit)) {
                        seen |= bit;
                        vars[nvars++] = *c;
                    }
                }
                ops = compile_word(ops, tok);
                break;
        }
    }
    *ops = OP_RET;
    //disassemble(program);

    /* Run solver */
    solve(vars, program, constants, -1U);
}