Write a FAST word equation solver

Question

This question is similar to Write a word equation solver by David Frank but different in three important ways: (1) David asked for just the first solution found, and I am asking for all the solutions. (2) I am asking to output the time required to solve the puzzle. And (3), it is a completely different undertaking to write a program designed to be fast compared with one designed to be short. A brute force method is probably best for code golf, but will not beat my ?amazing? time of 0.15 seconds. -I say "amazing" only to encourage other to try it out. I'm sure mine won't be the fastest.

(I'm going to copy a lot of the text from that question.)

Introduction

Consider the following example:

  CODE
+ GOLF
——————
 GREAT

This is an equation where each letter represents a decimal digit and the words represent natural numbers (similar letters represent similar digits and different letters represent different digits). The task is to match each letter with its digit value so that the equation is correct. One of the four solutions for the equation above is:

  9265
+ 1278
——————
 10543

Your task

Your task is to write a program or function to find ALL of the answers to such a word equation. Your program should output all the answers and the time it took to find them in seconds.

Input

The input will be something like this, two words added together to make a third word.

Example:

1. CODE+GOLF=GREAT
2. AA+BB=CC

Spaces are omitted and only letters between capital A and Z will be used (no special or small letters). This string can be read from the standard input, from a file, or as a function parameter.

Output

The output should look something like this. To take luck out of the competition, your program must list all the solutions.

time = XX.XXX seconds
(1) 9265+1278=10543
(2) 9275+1268=10543
(3) 9428+1437=10865
(4) 9438+1427=10865

Rules

1. Similar letters represent similar digits and different letters represent different digits
2. To make things easier, you can assume that numbers can or don't start with a leading zero, it's up to you. The four answers I got for the sample problem assume numbers do not start with leading zeros.
3. You can use any language and the standard library of the chosen language (no external libs)
4. You cannot connect to any resources on the internet (why would you anyways?)
5. So the goal here is speed, but of coarse that depends on what computer you use. In order to account for the different speed of different computers, you could run my example on your computer and then report how many times faster or slower yours is than my sample answer.
6. Please explain how your code works.

Example in JavaScript

http://goo.gl/TdQczX

Answer 1

Python3, 0.03 seconds:

def f(a, b, r, c = {}, s = [], k = 0, l = [], A = [], B = []):
   if not a and not b:
      yield f"{''.join(map(str, A))}+{''.join(map(str, B))}={''.join(map(str, l))}"
      return
   for x in c.get(a[-1], range(10)):
      if a[-1] in c or x not in s:
         _c, _s = {**c, a[-1]:[x]}, s+[x]
         for y in _c.get(b[-1], range(10)):
             if b[-1] in _c or y not in _s:
                n_c, v = {**_c, b[-1]:[y]}, k+x+y
                n_s = _s+[y]
                if a[:-1] and b[:-1]:
                    _v, _k = v%10, v//10
                    if [_v] == n_c.get(r[-1], [_v])and (r[-1] in n_c or _v not in n_s):
                        yield from f(a[:-1], b[:-1], r[:-1], {**n_c, r[-1]:[_v]}, n_s+[_v], _k, [_v]+l, [x]+A, [y]+B)
                else:
                    if len(str(v)) == len(r):
                        F = 1
                        for J, K in zip(r[::-1], str(v)[::-1]):
                            if n_c.get(J, [int(K)]) == [int(K)] and (J in n_c or int(K) not in n_s):
                               n_c[J] = [int(K)]
                               n_s = n_s + [int(K)]
                            else:
                               F = 0
                               break
                        if F: yield from f(a[:-1], b[:-1], '', n_c, n_s, 0, [v]+l, [x]+A, [y]+B) 
            
t = time.time()
result = [*f('CODE', 'GOLF', 'GREAT')]
print(time.time() - t)
print(result)

Try it online!

Answer 2

C++, 10000× faster (~20 µs)

#include <stdio.h>
#include <time.h>
#include <algorithm>

// digits
typedef int digit_t;
const digit_t BASE = 10;
typedef unsigned digit_mask_t;
inline char format_digit(digit_t d) { return '0' + d; }

// letters
typedef int letter_t;
const letter_t ALPHABETSIZE = 26;
typedef unsigned letter_mask_t;
inline bool is_letter(char c) { return unsigned(c - 'A') < 26u; }
inline letter_t parse_letter(char c) { return letter_t(c - 'A'); }

// terms
typedef int term_t;
inline term_t term_abs(term_t x) { return x < 0 ? -x : x; }


bool parse_formula(const char* formula, term_t coeffs[ALPHABETSIZE], letter_mask_t* ppresent, letter_mask_t* pleading) {
    // Convert BA+BB=CCC into A + 21*B - 111*C = 0.
    letter_mask_t present = 0, leading = 0;
    const char* p = formula;
    term_t side = +1, place = +1;
    for (;;) {
        const char* r;
        for (r = p; is_letter(*r); ++r) {}
        if (p < r)
            leading |= letter_mask_t(1) << parse_letter(*p);
        for (const char* q = r; q != p; --q) {
            letter_t l = parse_letter(q[-1]);
            coeffs[l] += place;
            present |= letter_mask_t(1) << l;
            place *= BASE;
        }
        p = r;
        switch (*p++) {
            case 0:
                *ppresent = present; *pleading = leading; return true;
            case '+':
                place = +side; break;
            case '-':
                place = -side; break;
            case '=':
                if (side < 0)
                    return false;
                place = side = -1;
                break;
            default:
                return false;
        }
    }
}

struct Var {
    digit_t value;
    term_t coeff;
    digit_t minval;  // 0 or 1
    letter_t name;
};

class Solver {
    const char* formula;
    letter_t num_vars;
    Var vars[BASE];
    void solve2(Var*, digit_mask_t, term_t, term_t);
public:
    bool solve(const char* formula);
};

bool Solver::solve(const char* formula) {
    this->formula = formula;
    term_t coeffs[ALPHABETSIZE] = {0};
    letter_mask_t present, leading;
    if (!parse_formula(formula, coeffs, &present, &leading))
        return false;
    // sort the used letters by magnitude of their coefficient
    letter_t letters[BASE];
    letter_t num_vars = 0;
    for (letter_t i = 0; i < ALPHABETSIZE; ++i) {
        if (present & (letter_mask_t(1) << i)) {
            if (num_vars == BASE)
                return false;
            letters[num_vars++] = i;
        }
    }
    if (num_vars == 0)
        return false;
    this->num_vars = num_vars;
    std::sort(letters, letters + num_vars, [&](letter_t a, letter_t b) { return term_abs(coeffs[a]) < term_abs(coeffs[b]); });
    // initialize tables
    term_t bounds[2] = {0};
    for (letter_t i = 0; i < num_vars; ++i) {
        vars[i].name = letters[i];
        vars[i].minval = digit_t((leading >> letters[i]) & 1);
        term_t coeff = vars[i].coeff = coeffs[letters[i]];
        bounds[coeff > 0] += coeff * (BASE - 1);
    }
    // call the recursive solver
    solve2(vars + num_vars - 1, 0, bounds[0], bounds[1]);
    return true;
}

void Solver::solve2(Var* pos, digit_mask_t digits_used, term_t lower_bound, term_t upper_bound) {
    term_t coeff = pos->coeff;
    digit_t d = BASE - 1, e = pos->minval;
    // adjust bounds to reflect a digit equal to BASE-1, instead of anything in [0,BASE)
    if (coeff < 0)
        upper_bound += coeff * d;
    else
        lower_bound += coeff * d;
    do {
        if (lower_bound <= 0 && upper_bound >= 0 && !(digits_used & (digit_mask_t(1) << d))) {
            pos->value = d;
            if (pos == vars) {
                // print the solution
                char digit_chars[ALPHABETSIZE];
                for (letter_t i = 0; i < num_vars; ++i)
                    digit_chars[vars[i].name] = format_digit(vars[i].value);
                for (const char* p = formula; *p; ++p)
                    putchar(is_letter(*p) ? digit_chars[parse_letter(*p)] : *p);
                putchar('\n');
            } else {
                solve2(pos - 1, digits_used | (digit_mask_t(1) << d), lower_bound, upper_bound);
            }
        }
        lower_bound -= coeff;
        upper_bound -= coeff;
    } while (--d >= e);
}


int main(int argc, char **argv) {
    int code = 0;
    for (int i = 1; i < argc; ++i) {
        puts(argv[i]);
        clock_t t = clock();
        code |= !Solver().solve(argv[i]);
        t = clock() - t;
        printf("%f\n", double(t) / CLOCKS_PER_SEC);
    }
    return code;
}

Attempt This Online!

This is roughly 10,000 times faster than JeffSB's solver and 2,500 times faster than Ajax1234's solver on my machine on the problem CODE+GOLF=GREAT. The speed ratio varies widely with the problem. For FIFTY+STATES=AMERICA, the JeffSB/me ratio is 25,000, while for CORRECTS+REJECTED=MATTRESS it's about 25.

The algorithm is quite different. Neither JeffSB nor Ajax1234 explained theirs, but it appears they both do digitwise addition from right to left. This program converts a problem like TO+GO=OUT into a formula like \$-98 O + 10 G - 10 U + 9 T = 0\$, with the terms sorted by absolute value. For each term from left to right, for each possible value of that digit, it computes upper and lower bounds for the sum by assuming that every later digit is 0 or 9. If the bounds include 0 then it recurses.

Since it doesn't cost any time, this program supports a more general set of alphametics with arbitrarily many terms on both sides of the =, and subtraction as well as addition. It can very quickly solve problems like NINETEEN+NINETEEN+TEN+TEN+TEN+TEN+NINE+NINE+NINE+NINE+NINE+ONE+ONE+ONE+...=THOUSAND where there are 877 ONEs.

I tried computing slightly more sophisticated bounds, and rewriting the recursive function as an iterative one, but both changes only improved performance by 1-2%, and complicated the code, so I reverted them.

^{(Sources for example problems: Mike Keith, Michael Hartley)}

Answer 3

Python 3, <5ms

def solver(eqn, soln_format = "eqn"):
    #get weights
    weight = -1
    weights = {}
    for char in reversed(eqn):
        if char=='=':
            weight=1
            continue
        if char=='+':
            if weight>0:
                weight=1
            else:
                weight=-1
            continue
        if char not in weights:
            weights[char] = 0
        weights[char]+= weight
        weight*=10
    
    assert len(weights) <= 10
    weights_sorted = list(weights.values()) + [0]*(10-len(weights.values()))
    weights_sorted.sort()
    
    _, order = zip(*sorted(zip(weights_sorted, range(10)), key=lambda x: abs(x[0]), reverse=True)) #abs sorted order
    order_list = [num - sum(i<num for i in order[:idx]) for idx, num in enumerate(order)] #because indexes change
    order_list = order_list[:len(weights.values())] #to ignore zeros
    order_list.reverse() #to pop and append like a stack
        
    for soln in backtrack(0, weights_sorted.copy(), order_list, list(reversed(range(10))), []):
        weights_copy = weights.copy()
        weight_soln_pair = [(weights_sorted[i],num) for i,num in zip(order, soln)]
        assert sum(i*j for i,j in weight_soln_pair) == 0, "Major error"
        final_soln = {}
        for weight_val, soln_val in weight_soln_pair:
            for char, weight in weights_copy.items():
                if weight == weight_val:
                    final_soln[char] = soln_val
                    del weights_copy[char]
                    break
                    
        if soln_format == "eqn":
            #CONVERT TO EQN
            eqn_copy = eqn
            for k, v in final_soln.items():
                eqn_copy = eqn_copy.replace(k, str(v))
            yield eqn_copy
        elif soln_format == "dict":
            yield final_soln
        
def backtrack(val, weights, test_order, remaining, soln):
    #Check if end
    if len(test_order)==0:
        if val==0: 
            yield soln
        return False
    #Check if possible
    if sum([i*j for i,j in zip(remaining, reversed(weights))]) + val < 0: #max
        return False
    if sum([i*j for i,j in zip(remaining, weights)]) + val > 0: #min
        return False
    #Backtrack for each digit
    order = test_order.pop()
    weight = weights.pop(order)
    for i, num in enumerate(remaining):
        del remaining[i]
        yield from backtrack(val+num*weight, weights, test_order, remaining, soln + [num])
        remaining.insert(i, num)
    weights.insert(order, weight)
    test_order.append(order)
    return False

does pretty much the same as benrg's answer, but in python and does not remove the solutions with leading zeros

%%timeit -n 1 -r 1
print([*solver('CODE+GOLF=GREAT')])

---

['9428+1437=10865', '9438+1427=10865', '9265+1278=10543', '9275+1268=10543', '8653+0671=09324', '8673+0651=09324', '8643+0672=09315', '8673+0642=09315', '8612+0635=09247', '8632+0615=09247', '7642+0651=08293', '7652+0641=08293', '6918+0934=07852', '6938+0914=07852', '6918+0925=07843', '6928+0915=07843', '5928+0943=06871', '5948+0923=06871', '3857+0862=04719', '3867+0852=04719', '3612+0685=04297', '3682+0615=04297', '2918+0956=03874', '2958+0916=03874', '2918+0947=03865', '2948+0917=03865', '2846+0851=03697', '2856+0841=03697']
4.63 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

notebook link