# Write a FAST word equation solver

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 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.

Example in JavaScript

http://goo.gl/TdQczX  • For fairness, submissions to fastest-code challenges should all be tested on the same machine - which usually means your machine. Are you prepared to install all of those submissions on your own machine? Alternatively, another option might be to have everyone run your own solution and their own, the score being the ratio between the two. Jul 22, 2014 at 10:23
• Also I think your example problem may be too small to accurately measure the timing for well-optimised solutions. You might want to provide a larger test case as the benchmark. Jul 22, 2014 at 10:24
• @PeterTaylor Right, I didn't see his comment. I personally think (and I've seen answers along those lines on meta, too - and the comment with 3 upvotes is one of them) that we should take into account whether any submission from the original challenge would be competitive against new submissions which tackle the new challenge in a way according to the new winning criterion. If three optimised answers to this are posted, who would copy over a golfed brute force solution? I'm pretty sure to win this one, you do have to solve it in a novel way. Jul 22, 2014 at 10:34
• (Furthermore, copying a golfed submission into a fastest-code challenge comes very close to justifying a delete-vote for "This does not provide an answer to the question.") Jul 22, 2014 at 10:36
• @PeterTaylor That's a fair point, although in that case I'd rather view the old one a duplicate of this one, as this here is definitely the more interesting challenge (answers to which can be submitted to the other one by encoding it in a whitespace string). One more thing about Tyzoid's opinion: there is a reasonable chance that his strong opinion and the upvotes were correlated to the fact that the two winning criteria in question were much more similar than code-golf vs fastest-code. Jul 22, 2014 at 10:45

# 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!

• I think this answer qualifies for 400 rep from this bounty and 500 rep if you add an explanation.
– user
Jun 6, 2022 at 17:53
• does not work on print([*f('FIFTY', 'STATES', 'AMERICA')]) Oct 23, 2022 at 19:26

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

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

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

// letters
typedef int letter_t;
const letter_t ALPHABETSIZE = 26;
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; }

// Convert BA+BB=CCC into A + 21*B - 111*C = 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)
for (const char* q = r; q != p; --q) {
letter_t l = parse_letter(q[-1]);
coeffs[l] += place;
place *= BASE;
}
p = r;
switch (*p++) {
case 0:
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];
public:
bool solve(const char* formula);
};

bool Solver::solve(const char* formula) {
this->formula = formula;
term_t coeffs[ALPHABETSIZE] = {0};
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 = {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, bounds);
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)

# 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()) + *(10-len(weights.values()))
weights_sorted.sort()

_, order = zip(*sorted(zip(weights_sorted, range(10)), key=lambda x: abs(x), 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)