Enigmatic Code

Programming Enigma Puzzles

Solving Alphametics with Python

(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 PyPyUnfortunately 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:

Sunday Times Teaser 2796

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.


Sunday Times Teaser 2803

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

6 responses to “Solving Alphametics with Python

  1. Hugh Casement 22 June 2016 at 6:39 pm

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

  2. arthurvause 23 June 2016 at 9:28 am

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

    """
    Alphametic solver, based on code created by Raymond Hettinger, http://code.activestate.com/recipes/576615-alphametics-solver/
    
    This version constructs and executes a program that examines all permutations of digits substituted
    for letters. It improves on Raymond Hettinger's original code by eliminating repeated compilation and execution.
    
    For example the alphametic SEND + MORE == MONEY is converted to a program:
    
    from itertools import permutations
    from string import maketrans
    for S,M,E,D,O,N,R,Y in permutations(range(10),8):
      if S and M:
        if (S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y):
            trans = maketrans('SMEDONRY', ''.join([str(x) for x in (S,M,E,D,O,N,R,Y)]))
            print 'SEND + MORE == MONEY'.translate(trans)
    
    """
    
    from time import clock
    from re import findall, finditer
    
    def expand(w):
      #  e.g. expand('ABC') = '(A*100+B*10+C)'
      n=len(w)
      return "("+''.join([ '+'+w[i]+'*'+str(10**(n-i-1)) for i in xrange(len(w))])[1:-2]+")"
    
    def solve(s):
      words = findall('[A-Za-z]+', s)
      chars = set(''.join(words))         # characters to be substituted
      assert len(chars) <= 10             # there are only ten possible digits
      firsts = set(w[0] for w in words)   # first letters of each of word
      chars = ''.join(firsts) + ''.join(chars - firsts)
    
      ex =  "from itertools import permutations\n"
      ex += "from string import maketrans\n"
      ex += "for "+','.join(chars)+" in permutations(range(10),"+str(len(chars))+"):\n"
      ex += "  if " + ' and '.join(firsts)+":\n"
      t=s[:]
      for m in finditer('[A-Za-z]+', s):
          w=s[m.start():m.end()]
          t=t.replace(w, expand(w),1)
      ex += "    if "+ t    +":\n"
      ex += "        trans = maketrans('"+chars+"', ''.join([str(x) for x in ("+','.join(chars)+")]))\n"
      ex += "        print '"+s+"'.translate(trans)\n"
      starttime = clock()
      exec(ex)
      endtime=clock()
      print endtime-starttime,"sec"
    
    if __name__ == '__main__':
      for alphametic in [
        # Sunday Times Teaser 2803, 12 Jun 2016, https://sites.google.com/site/sundaytimesteasers/teaser-index-1/2016-q2/teaser-2803
        '(AB*CDE == FGHIJ) & (AB + CD + EF + GH + IJ == CCC)',
    
        # Henry Dudeney's puzzle, Strand Magazine, 1924, https://en.wikipedia.org/wiki/Verbal_arithmetic
        'SEND + MORE == MONEY',
    
        # IBM Ponder This, Nov 2015, https://www.research.ibm.com/haifa/ponderthis/challenges/November2015.html
        'A*TOAST-TO == WATSON',
        # 'N**O**W == WATSON' takes too long to run.
        
       ]:
        print "\n", alphametic
        solve(alphametic)
      
    
    
    
    
    • Jim Randell 23 June 2016 at 12:12 pm

      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.

    • Jim Randell 23 June 2016 at 11:43 pm

      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:

      def solve():
        for D in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
          for E in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
            if E!=D:
              for M in (1, 2, 3, 4, 5, 6, 7, 8, 9):
                if M!=D and M!=E:
                  for N in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
                    if N!=D and N!=E and N!=M:
                      for O in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
                        if O!=D and O!=E and O!=M and O!=N:
                          for R in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
                            if R!=D and R!=E and R!=M and R!=N and R!=O:
                              for S in (1, 2, 3, 4, 5, 6, 7, 8, 9):
                                if S!=D and S!=E and S!=M and S!=N and S!=O and S!=R:
                                  x = (D+N*10+E*100+S*1000) + (E+R*10+O*100+M*1000)
                                  (x, Y) = divmod(x, 10)
                                  if Y!=D and Y!=E and Y!=M and Y!=N and Y!=O and Y!=R and Y!=S:
                                    (x, y) = divmod(x, 10)
                                    if y == E:
                                      (x, y) = divmod(x, 10)
                                      if y == N:
                                        (x, y) = divmod(x, 10)
                                        if y == O:
                                          (x, y) = divmod(x, 10)
                                          if x == 0 and y == M:
                                            yield { 'D': D, 'E': E, 'M': M, 'N': N, 'O': O, 'R': R, 'S': S, 'Y': Y }
      

      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 SubstitutedSum solver directly, making it even faster.

      • Jim Randell 25 June 2016 at 5:32 pm

        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 to eval()), 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 repeated eval() 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 the SubstitutedSum() 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 the SubstitutedExpression() solver, with the same interface as before. They are also aliased to alphametic() and Alphametic() respectively.

        (If you look at the code you’ll notice I’m using eval() rather than exec(), but that’s to make it more compatible with older versions of Python).

  3. arthurvause 24 June 2016 at 9:40 am

    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.

    """
    Alphametic solver, based on code created by Raymond Hettinger, http://code.activestate.com/recipes/576615-alphametics-solver/
    
    This version constructs and executes a program that examines all permutations of digits substituted
    for letters. It improves on Raymond Hettinger's original code by eliminating repeated compilation and execution.
    
    For example the alphametic SEND + MORE == MONEY is converted to a program:
    
    from itertools import permutations
    from string import maketrans
    fullset = set(range(10))
    for S,M in permutations(range(1,10),2):
      for E,D,O,N,R,Y in permutations(fullset-set((S,M)),6):
        if (S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y):
            trans = maketrans('SMEDONRY', ''.join([str(x) for x in (S,M,E,D,O,N,R,Y)]))
            print 'SEND + MORE == MONEY'.translate(trans)
    
    """
    
    from time import clock
    from re import findall, finditer
    
    def expand(w):
      #  e.g. expand('ABC') = '(A*100+B*10+C)'
      n=len(w)
      return "("+''.join([ '+'+w[i]+'*'+str(10**(n-i-1)) for i in xrange(len(w))])[1:-2]+")"
    
    def solve(s):
      words = findall('[A-Za-z]+', s)
      chars = set(''.join(words))         # characters to be substituted
      assert len(chars) <= 10             # there are only ten possible digits
      firsts = set(w[0] for w in words)   # first letters of each of word
      chars2 = ''.join(firsts) + ''.join(chars - firsts)
    
      ex =  "from itertools import permutations\n" +\
            "from string import maketrans\n" +\
            "fullset = set(range(10))\n" +\
            "for "+','.join(firsts)+" in permutations(range(1,10),"+str(len(firsts))+"):\n" +\
            "  for " + ','.join(chars - firsts)+ " in permutations(fullset-set(("+','.join(firsts)+")),"+str(len(chars - firsts))+"):\n"
      t=s[:]
      for m in finditer('[A-Za-z]+', s):
          w=s[m.start():m.end()]
          t=t.replace(w, expand(w),1)
      ex += "    if "+ t    +":\n"  +\
            "        trans = maketrans('"+chars2+"', ''.join([str(x) for x in ("+','.join(chars2)+")]))\n"  +\
            "        print '"+s+"'.translate(trans)\n"
    
      #print ex
      starttime = clock()
      exec(ex)
      endtime=clock()
      print endtime-starttime,"sec"
    
    if __name__ == '__main__':
      for alphametic in [
        # Sunday Times Teaser 2803, 12 Jun 2016, https://sites.google.com/site/sundaytimesteasers/teaser-index-1/2016-q2/teaser-2803
        '(AB*CDE == FGHIJ) & (AB + CD + EF + GH + IJ == CCC)',
    
        # Henry Dudeney's puzzle, Strand Magazine, 1924, https://en.wikipedia.org/wiki/Verbal_arithmetic
        'SEND + MORE == MONEY',
    
        # IBM Ponder This, Nov 2015, https://www.research.ibm.com/haifa/ponderthis/challenges/November2015.html
        'A*TOAST-TO == WATSON',
        # 'N**O**W == WATSON' takes too long to run.
        
       ]:
        print "\n", alphametic
        solve(alphametic)
      
    
    
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: