### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

22 June 2016

Posted by on (See also: **Solving Alphametics with Python, Part 2**).

Many *Enigma* puzzles use **Alphametics** (or **Cryptarithms** — see the *Wikipedia* page on *Verbal Arithmetic* for other terms), where a sum (or other expression) is given with the numbers consistently substituted for letters (or sometimes other symbols).

For example, **Enigma 63**, consists of solving the following Alphametic sum:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

By the time I came to solving this puzzle I had got a bit bored with writing programs to solve specific Alphametic sum problems, and decided it would be more fun to write a generic solver that could be used to solve any such substituted sum problem. The result was the `SubstitutedSum()` class in the **enigma.py** library, which allows various variations on Alphametic sums to be solved in a fairly efficient way.

(The code itself considers the columns of the sum moving from right to left, and when dealing with each column it looks at the possible substitutions for the symbols remaining unassigned in that column, and when it finds a suitable assignment it moves on to the next column to the left).

Later, I added the ability to invoke it directly from the command line, so for simple problems (like **Enigma 63**) it is not even necessary to write a program:

% python -m enigma SubstitutedSum "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL" LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL 8308440 + 8333218 + 8302040 + 8333260 = 33276958 / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 0.14s, which was actually faster than my original programmed solution.

This is all very well (and fast) for Alphametic problems which are simple addition sums, but what about more complication problems. **Enigma 1530**, for instance, is a multiplication problem, and while it can be solved using **SubstitutedSum()** by turning the multiplication sum into a repeated addition I was interested in a solver that will work on arbitrary Python expressions.

There is such a solver (originally by Raymond Hettinger) which appears in several places on the web. The gist of it is to generate all the possible assignments of letters to digits, then substitute them into the expression and call Python’s **eval()** function on it. In pseudo-code:

# solve <expr> as an alphametic expression def solve(expr): # extract the letters from expr letters = <letters occurring in expr> # consider possible assignments for each letter for digits in permutations('0123456789', len(letters)): # replace letters with corresponding digits new_expr = <expr with <letters> replaced by <digits>> if eval(new_expr): # output the solution <output solution>

This is obviously much slower than a specialised solver, as it can consider up to 10! = 3,628,800 different assignments of letters to digits, and then it calls **eval()** on each one. Each call to **eval()** will involve a parsing, compiling and finally execution stage.

While this is undoubtedly a very concise piece of code, that does indeed allow for the solving of arbitrary Alphametic expressions there are a couple of problems with it in general use.

Firstly (as previously mentioned), it is a bit slow. Generally it takes about a minute to consider all the possible assignments of 10 different digits to 10 letters (depending on the complexity of the expression).

Usually, my first weapon of choice to speed up Python programs is to try running them using **PyPy**. Unfortunately programs that make heavy use of **eval()** don’t benefit from the speed increases of **PyPy**, and my test program ran about 2.5× *faster* under CPython than under **PyPy**.

Secondly it isn’t that easy to extend it to incorporate the additional features that I added in to **SubstitutedSum()** (like solving in a different base, or specifying which assignments are allowed (to allow solutions using leading zeros), etc).

The code as published removes leading zeros from consideration (and the way it is written it will also exclude 0 itself as a standalone digit, which may or may not be what you want). If you try to allow leading zeros you run into problems. A literal of the form 072 is a Syntax Error in Python 3, and in Python 2 it evaluates to 58 as it is assumed to be octal, neither of which is particularly helpful behaviour in this situation.

Instead my **SubstitutedExpression()** code takes the initial expression, and replaces the *words* in it with placeholder arguments. It then uses **eval()** once to parse and compile a function that takes the numerical values of each word in the original expression. It then generates all the possible letter-to-digit assignments, generates the numbers that correspond to the words in the expression and passes those to the compiled function to see if the original expression is satisfied.

The pseudo-code for this is:

# solve <expr> as an alphametic expression def solve(expr): # replace the words in expr with placeholders (body, words) = replace_words(expr) # make an executable function from <body> fn = eval("lambda <args>: <body>") # extract the letters in the words letters = <letters in <words>> # consider possible assignments for each letter for digits in permutations(irange(0, 9), len(letters)): # map the words to numbers using the digits args = list((<word> with <letters> replaced by <digits>) for <word> in <words>) # compute the result of the expression if fn(args): <output solution>

This works well, and allows us to use **PyPy** to gain a speed increase, and also to consider numbers in bases other than 10 and to allow leading zeros, as well as supporting the other bells and whistles carried over from the **SubstitutedSum()** solver.

It is however still slower than it needs to be in many cases. For instance, in **Enigma 1530**, we need to solve the (partial) Alphametic multiplication sum: TOM × 13 = DALEY. The whole expression has 8 letters that need to be substituted for digits, potentially requiring us to look at 10×9×8×7×6×5×4×3 = 1,814,400 possible assignments. But if we look at just the left hand side of the sum, there are only 3 letters in: TOM × 13, which only requires looking at 10×9×8 = 720 possible assignments. For each of those assignments we can look at the resulting product and then try and match it against the Alphametic result of: DALEY. Thereby reducing the number of possibilities we need to consider by a factor of 2,520.

The pseudo-code now looks something like this:

# solve <expr> = <value> as an alphametic equation def solve(expr, value): # replace the words in expr with placeholders (body, words) = replace_words(expr) # make an executable function from <body> fn = eval("lambda <args>: <body>") # extract the letters in the words letters = <letters in <words>> # consider possible assignments for each letter for digits in permutations(irange(0, 9), len(letters)): # map the words to numbers using the digits args = list((<word> with <letters> replaced by <digits>) for <word> in <words>) # compute the result of the expression result = fn(args) # does the result match <value> solution = match(value, result) if solution: <output solution>

(While this approach appears to limit us to only considering Alphametic expressions of the form: <expr> = <value>, where <value> is a single literal (either an Alphametic “word” or an integer literal), this is not really a restriction, since boolean expressions evaluate to 0 or 1 we can treat any expression that doesn’t follow this pattern as: bool(<expr>) = 1, and we are back to an expression of the form: <expr> = <value>).

This is basically the approach I have used in the implementation of the **SubstitutedExpression()** solver in the **enigma.py** library (and I’ve allowed **Alphametic()** to be used as an alias for it to save typing). It can be invoked directly from the command line, so for many problems it is not necessary to write a separate program.

I have also allowed for several Alphametic expressions to be solved simultaneously. The solution (mapping from letters to digit values) that is generated from the first is used as a starting point for the second expression, and so on until all of the expressions are satisfied. The solver includes a heuristic algorithm to decided what order the expressions should be evaluated to try and minimise the number of possible assignments considered. (Although you can turn off the reordering if you prefer).

These are the command line arguments that can be used:

% python -m enigma Alphametic --help usage: SubstitutedExpression [<opts>] <expression> [<expression> ...] options: --symbols=<string> (or -s<string>) = symbols to replace with digits --base=<n> (or -b<n>) = set base to <n> --assign=<letter>,<digit> (or -a<l>,<d>) = assign digit to letter --digits=<digit>,... or --digits=<digit>-<digit> (or -d...) = available digits --invalid=<digit>,<letters> (or -i<d>,<ls>) = invalid digit to letter assignments --first (or -1) = stop after the first solution --reorder=<n> (or -r<n>) = allow reordering of expressions (0 = off, 1 = on) --verbose[=<n>] (or -v[<n>]) = verbosity (0 = off, 1 = solutions, 2 = more) --help (or -h) = show command-line usage

Here are some examples of Alphametic *Enigma* problems that can be solved directly using the **SubstitutedExpression()** solver from the command line. (I use the **Alphametic** alias to make the command line more compact):

First we solve a simple Alphametic sum — **Enigma 63**:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

% pypy -m enigma Alphametic "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL" (LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL) (8308440 + 8333218 + 8302040 + 8333260 = 33276958) / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 4.8s, so the **SubstitutedSum()** solver is over 30× faster in this case.

A more complex problem, consisting of two simultaneous Alphametic sums is given in **Enigma 5**:

HMPDM + BHPHM = RCDHA,

RBAD + PQHD = AADD.

% pypy -m enigma Alphametic "HMPDM + BHPHM = RCDHA" "RBAD + PQHD = AADD" (HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD) (24504 + 12524 = 37028) (3180 + 5620 = 8800) / A=8 B=1 C=7 D=0 H=2 M=4 P=5 Q=6 R=3

This runs in 0.46s. The same problem can be handled by the **SubstitutedSum()** solver in 0.045s, which is 10× faster.

**Enigma 1407** has an Alphametic sum and an additional condition:

SAND + SUN + SEX + SEA = IBIZA,

SAND > SUN > SEX > SEA.

% pypy -m enigma Alphametic "SAND + SUN + SEX + SEA = IBIZA" "SAND > SUN > SEX > SEA" (SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA) (9304 + 970 + 956 + 953 = 12183) (9304 > 970 > 956 > 953) / A=3 B=2 D=4 E=5 I=1 N=0 S=9 U=7 X=6 Z=8 (9306 + 970 + 954 + 953 = 12183) (9306 > 970 > 954 > 953) / A=3 B=2 D=6 E=5 I=1 N=0 S=9 U=7 X=4 Z=8

This takes 4.1s vs. 0.34s for my programmed solution.

**Enigma 1664** is a similar problem:

PAY + ASP + YES + ERR + RYE + SPA = YAPS,

P < A < Y < E < R < S.

% pypy -m enigma Alphametic "PAY + ASP + YES + ERR + RYE + SPA = YAPS" "P < A < Y < E < R < S" (PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S) (123 + 291 + 369 + 688 + 836 + 912 = 3219) (1 < 2 < 3 < 6 < 8 < 9) / A=2 E=6 P=1 R=8 S=9 Y=3

This runs in 0.9s vs. 0.03s for my programmed solution.

**Enigma 1530** is a multiplication problem:

TOM × 13 = DALEY.

% python -m enigma Alphametic "TOM * 13 = DALEY" (TOM * 13 = DALEY) (796 * 13 = 10348) / A=0 D=1 E=4 L=3 M=6 O=9 T=7 Y=8

This takes 0.08s vs. 0.04s for a programmed solution using **SubstitutedSum()**, so it is only 2× faster.

**Enigma 323** has two Alphametic sums, although the exact answer is not given for the second one:

CUT + UTC + TCU = MEDS,

RIO + IOR + ORI = <missing>,

MEDS × <missing> = OMTTOUI.

% pypy -m enigma Alphametic "CUT + UTC + TCU = MEDS" "(RIO + IOR + ORI) * MEDS = OMTTOUI" (CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI) (487 + 874 + 748 = 2109) ((563 + 635 + 356) * 2109 = 3277386) / C=4 D=0 E=1 I=6 M=2 O=3 R=5 S=9 T=7 U=8

This runs in 0.25s, compared to 0.04s for my programmed solution.

**Enigma 253** has a sum, a product and a condition.

ENI + GMA = SUM,

ENI × GMA = ??MES,

I > 2 × U.

This one is faster if we order the expressions ourselves.

% pypy -m enigma Alphametic --reorder=0 "(ENI * GMA) % 1000 = MES" "ENI + GMA = SUM" "I > 2 * U" (ENI + GMA = SUM) ((ENI * GMA) % 1000 = MES) (I > 2 * U) (279 + 156 = 435) ((279 * 156) % 1000 = 524) (9 > 2 * 3) / A=6 E=2 G=1 I=9 M=5 N=7 S=4 U=3

This runs in 1.2s. If we let the solver choose the ordering of the clauses it takes 2.2s. My programmed solution (which uses **SubstitutedSum()**) takes 0.09s.

**Enigma 1261** has an Alphametic sum with several additional conditions:

ALPHA + BETA + GAMMA = DELTA,

24 and 26 divide ALPHABET,

3 divides GAMMA.

Again, we get a faster solution if we order the clauses ourselves:

% pypy -m enigma Alphametic --reorder=0 "ALPHABET % 26 = 0" "ALPHABET % 24 = 0" "ALPHA + BETA + GAMMA = DELTA" "GAMMA % 3 = 0" (ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (ALPHA + BETA + GAMMA = DELTA) (GAMMA % 3 = 0) (56375904 % 26 = 0) (56375904 % 24 = 0) (56375 + 9045 + 15225 = 80645) (15225 % 3 = 0) / A=5 B=9 D=8 E=0 G=1 H=7 L=6 M=2 P=3 T=4

This takes 8.6s. If we let the solver choose the ordering of the clauses it take 13s. These compare with 0.06s for my programmed solution.

**Enigma 245** uses some symbols that are not standard capital letters. We use “e”, “n” and “g” to stand for the reversed capitals, and we can specify these on the command line argument:

ENIG × MA = AM × gIne,

E − N − M = M − n − e,

N = n + n,

IN = nI + nI.

% pypy -m enigma Alphametic --symbols=ENIGMAeng "ENIG * MA == AM * gIne" "E - N - M == M - n - e" "N == n + n" "IN == nI + nI" (ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI) (6895 * 12 == 21 * 3940) (6 - 8 - 1 == 1 - 4 - 0) (8 == 4 + 4) (98 == 49 + 49) / A=2 E=6 G=5 I=9 M=1 N=8 e=0 g=3 n=4

It runs in 0.2s compared with 0.03s for my programmed solution.

We can solve problems in number bases other than 10, e.g. **Enigma 1581:**

THOMAS − DALEY = GOLD (in base 11).

I’ve rearranged the expression into an addition sum to reduce the number of free symbols on the left hand side of the expression (GOLD + DALEY only has 7 free symbols, THOMAS − DALEY has 10).

% pypy -m enigma Alphametic --base=11 "GOLD + DALEY = THOMAS" (GOLD + DALEY = THOMAS) (639A + A7985 = 103274) / A=7 D=10 E=8 G=6 H=0 L=9 M=2 O=3 S=4 T=1 Y=5

This runs in 9.5s vs. 0.33s using **SubstitutedSum()** (which can also solve problems in different bases).

Note that the letter A appears both as a symbol to be substituted and a digit in base 11 numbers, so there is the possibility of confusion. We could eliminate it completely by using lowercase letters for the symbols:

% pypy -m enigma Alphametic --base=11 --symbols=adeghlmosty "gold + daley = thomas" (gold + daley = thomas) (639A + A7985 = 103274) / a=7 d=10 e=8 g=6 h=0 l=9 m=2 o=3 s=4 t=1 y=5

A similar approach works for **Enigma 1663:**

FAREWELL + FREDALO = FLINTOFF (in base 11).

% pypy -m enigma Alphametic --symbols=adefilnortw --base=11 "farewell + fredalo = flintoff" (farewell + fredalo = flintoff) (6157A788 + 6573189 = 68042966) / a=1 d=3 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=10 (61573788 + 657A189 = 68042966) / a=1 d=10 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=3

This runs in 55s. The **SubstitutedSum()** solver takes 0.08s.

**Enigma 1361** gives us one of the assignments to start with:

ELGAR + ENIGMA = NIMROD.

We can add the assignment as an additional clause:

% pypy -m enigma Alphametic "ELGAR + ENIGMA = NIMROD" "O = 0" (ELGAR + ENIGMA = NIMROD) (O = 0) (71439 + 785463 = 856902) (0 = 0) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

This runs in 2.6s.

Or we can solve it in a single expression and assign the letter O using a command line option:

% pypy -m enigma Alphametic --assign=O,0 "ELGAR + ENIGMA = NIMROD" (ELGAR + ENIGMA = NIMROD) (71439 + 785463 = 856902) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

Which also runs in 2.6s.

The **–assign** option also works in the **SubstitutedSum()** solver, which solves this problem in 0.07s.

We can specify which digit are available — in **Enigma 1272** the digit 9 is not used:

JONNY = WILKI + NSON.

We also re-order the sum so that the expression is on the left hand side of the equals sign.

% pypy -m enigma Alphametic --digits=0,1,2,3,4,5,6,7,8 "WILKI + NSON = JONNY" (WILKI + NSON = JONNY) (48608 + 3723 = 52331) / I=8 J=5 K=0 L=6 N=3 O=2 S=7 W=4 Y=1 (48708 + 3623 = 52331) / I=8 J=5 K=0 L=7 N=3 O=2 S=6 W=4 Y=1

This runs in 1.3s compared to 0.05s using the **SubstitutedSum()** solver.

**Enigma 171** is a problem that uses numbers for symbols, but the numbers cannot stand for themselves:

1939 + 1079 = 6856.

We can handle this directly in the solver:

% pypy -m enigma Alphametic -s01356789 -i0,016 -i1,1 -i3,3 -i5,5 -i6,6 -i7,7 -i8,8 -i9,9 "1939 + 1079 = 6856" (1939 + 1079 = 6856) (2767 + 2137 = 4904) / 0=1 1=2 3=6 5=0 6=4 7=3 8=9 9=7

This runs in 0.5s vs. 0.08s using the **SubstitutedSum()** solver.

However there is possible ambiguity here. The value on the right hand side of the expression is interpreted either as a “word” (composed of symbols) or an integer literal (composed of numbers). In this case we could interpret the value in either way. The solver will interpret it as a “word” if it is entirely composed of symbols, otherwise it will try and parse it as a number (in the specified base). If both these approaches fail it will raise an error.

It might be better to rename the symbols to avoid any clash. Here is the same problem with the letters *abcdefgh* used instead of the digits 01356789.

% pypy -m enigma Alphametic -sabcdefgh -i0,abe -i1,b -i3,c -i5,d -i6,e -i7,f -i8,g -i9,h "bhch + bafh = egde" (bhch + bafh = egde) (2767 + 2137 = 4904) / a=1 b=2 c=6 d=0 e=4 f=3 g=9 h=7

**Enigma 94** has an Alphametic sum and an additional condition.

BRAIN + STRAIN + AGAIN = ENIGMA,

ATE is a perfect cube.

Any of the functions defined in **enigma.py** is available for use in expressions.

% pypy -m enigma Alphametic "BRAIN + STRAIN + AGAIN = ENIGMA" "is_cube(ATE)" (BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE)) (98234 + 518234 + 27234 = 643702) (is_cube(216)) / A=2 B=9 E=6 G=7 I=3 M=0 N=4 R=8 S=5 T=1

This runs in 0.6s, compared to 0.04s for my programmed solution using **SubstitutedSum()**.

**Enigma 1627** has an Alphametic sum and some additional conditions.

ETA + BETA + THETA = DELTA,

PHI is prime,

PSI is prime.

% pypy -m enigma Alphametic "ETA + BETA + THETA = DELTA" "is_prime(PHI)" "is_prime(PSI)" (ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI)) (250 + 8250 + 54250 = 62750) (is_prime(149)) (is_prime(139)) / A=0 B=8 D=6 E=2 H=4 I=9 L=7 P=1 S=3 T=5

This runs in 2.5s, compared with 0.045s for my programmed solution.

**Enigma 1180** has a subtraction sum, and then several constraints on various numbers formed from substituted words:

SEVEN − THREE = FOUR,

SEVEN is prime,

FOUR is prime,

RUOF is prime,

TEN is square.

% pypy -m enigma Alphametic "SEVEN - THREE = FOUR" "is_prime(SEVEN)" "is_prime(FOUR)" "is_prime(RUOF)" "is_square(TEN)" (SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN)) (62129 - 58722 = 3407) (is_prime(62129)) (is_prime(3407)) (is_prime(7043)) (is_square(529)) / E=2 F=3 H=8 N=9 O=4 R=7 S=6 T=5 U=0 V=1

This runs in 0.72s compared with 0.06s for my programmed solution.

**Enigma 1000** is a division sum:

ENIGMA / M = TIMES.

We can specify this as a full expression (using == as the right hand side of the expression is not a “word” or an integer literal):

% pypy -m enigma Alphametic --invalid=0,EMT "divmod(ENIGMA, M) == (TIMES, 0)" (divmod(ENIGMA, M) == (TIMES, 0)) (divmod(180426, 2) == (90213, 0)) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 7.8s.

Or we can re-write the expression to make it more friendly for the solver:

% pypy -m enigma Alphametic --invalid=0,EMT "M * TIMES = ENIGMA" (M * TIMES = ENIGMA) (2 * 90213 = 180426) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 0.45s, which compares to 0.042s for my programmed solution.

Here’s the solver let loose on a couple of recent **Sunday Times Teaser** puzzles:

SAINT + GEORGE = DRAGON,

GEORGE is even.

% pypy -m enigma Alphametic "SAINT + GEORGE = DRAGON" "E % 2 = 0" (SAINT + GEORGE = DRAGON) (E % 2 = 0) (72415 + 860386 = 932801) (6 % 2 = 0) / A=2 D=9 E=6 G=8 I=4 N=1 O=0 R=3 S=7 T=5

This runs in 8.8s, compared with 0.1s for a programmed solution.

AB × CDE = FGHIJ,

AB + CD + EF + GH + IJ = CCC.

% pypy -m enigma Alphametic "AB * CDE = FGHIJ" "AB + CD + EF + GH + IJ = CCC" (AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC) (52 * 367 = 19084) (52 + 36 + 71 + 90 + 84 = 333) / A=5 B=2 C=3 D=6 E=7 F=1 G=9 H=0 I=8 J=4

This runs in 0.5s vs. 0.15s for my programmed solution.

We can see, then, that many *Enigma* puzzles (and other similar puzzles) can be solved directly using the **SubstitutedSum()** and **SubstitutedExpression()** solvers, often with only a few seconds of run time, and while that may be slower in execution time than writing a custom program to solve the puzzle, the amount of time saved in not writing a custom program is more than made up for.

The Alphametic solvers are available as part of the **enigma.py** library for solving puzzles in Python, and will be kept up to date with improvements there. I will try and keep the calling interface to the solvers the same as that described above.

Enjoy.

Advertisements

%d bloggers like this:

I must confess I find puzzles such as Enigma 5, with a meaningless jumble of letters, uninspiring.

In the case of Enigma 63, LBRERQR can be converted to amoroso, desists, Granada, misuses, Niagara, precede, or resists; unfortunately the rest of the puzzle did indeed resist conversion in that way.

For Enigma 323 I found bellboy or treetop as a possible product; not all the individual “words” in the additions will be real words.

To avoid confusion between correct and incorrect digits, I like to solve a puzzle such as Enigma 171 by first converting the numbers to words: in this case MINI + MAXI = ELSE is a possibility.

It might be an interesting challenge to write a program to find such sets of words. Not being a brilliant programmer, I’m reduced to doing it a word at a time and juggling them by hand to fit (if they will).

Here is a variation of Raymond Hettinger’s code that I constructed to attempt to speed up the execution:

That’s a good way around the “repeated eval()” problem, and I get a good speed up using PyPy with this code. It should be easy to adapt it to cope with different bases too.

I’ve been thinking about this approach some more and it occurred to me that if we are writing a program to write the program to solve the alphametic, then we could do without using

itertools.permutations()at all, and go back to a series of nested loops, that way we can remove the need to generate invalid symbol/digit pairs (like leading zeros). And that saves us a little bit of time.We can also use the technique I describe in the post of spotting when the right-hand side of an equality expression is a literal value (<expr> = <value>), and deconstruct the value and check it digit by digit against the result of evaluating the left-hand side. This saves us more time.

I currently have code that when given “SEND + MORE = MONEY” produces this:

Which runs in quite a respectable time.

I think I can plug this in a replacement to my solver for single expressions to get a solver for multiple expressions that runs quite quickly.

I’m also thinking that as well as spotting expressions of the form “<expr> = <value>” and optimising those I can spot ones where <expr> is a straightforward sum and use the

SubstitutedSumsolver directly, making it even faster.I’ve just updated the code in

enigma.py(version 2016-06-25) to use this method for the multiple expression solver (it writes code that solves multiple expressions with one call toeval()), and it gives me a considerable speed-up over the timings given in the post above (between 2× and 50× faster — and 15× to 1000× faster than using the repeatedeval()approach, although of course the code that generates the program is much longer than Hettingers). In fact all the examples given in the post above run in less than 1.2s each (and less than 6s in total), and some of them are only 2× slower than theSubstitutedSum()solver manages.I’ll probably write up some notes with details of the timings next week.

It’s packaged up so that you can use the

substituted_expression()function (which is new), or theSubstitutedExpression()solver, with the same interface as before. They are also aliased toalphametic()andAlphametic()respectively.(If you look at the code you’ll notice I’m using

eval()rather thanexec(), but that’s to make it more compatible with older versions of Python).I also wondered about eliminating leading zeros more efficiently. Here is a version that avoids considering solutions with leading zeros It has a small but notiable improvement in performance.