Enigmatic Code

Programming Enigma Puzzles

Solving Alphametics with Python, Part 2

In my previous article (Solving Alphametics with Python) I explored some possibilities for improving on the speed of a simple algorithm for solving general Alphametic expressions using Python’s eval() function. I implemented a way of solving Alphametics without calling eval() for every potential letter-to-digit assignment, and also a way of reducing the number of possibilities we need to consider in the common case of expressions involving equality.

That article received a comment from Arthur Vause, in which he shared his own program that addresses the problem of repeated calls to eval() by writing code that generates a program that considers the possibilities, and then getting Python to execute that.

I’ve taken this idea a bit further and instead of having code that generates a relatively short program, instead it can generate a series of nested loops and if statements with all the logic of the valid/invalid assignments built into the structure of the generated program itself. This gives us something that may not look elegant, but executes quickly, (and can be handled by PyPy without problems).

So, for a problem like Enigma 1530:

TOM × 13 = DALEY

my code produces a program like this:

def solve():
  for T in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
    for O in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
      if O != T:
        for M in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
          if M != T and M != O:
            TOM = M + O*10 + T*100
            x = TOM * 13
            (x, Y) = divmod(x, 10)
            if Y != T and Y != O and Y != M:
              (x, E) = divmod(x, 10)
              if E != T and E != O and E != M and E != Y:
                (x, L) = divmod(x, 10)
                if L != T and L != O and L != M and L != Y and L != E:
                  (x, A) = divmod(x, 10)
                  if A != T and A != O and A != M and A != Y and A != E and A != L:
                    (x, D) = divmod(x, 10)
                    if D != T and D != O and D != M and D != Y and D != E and D != L and D != A and D != 0 and x == 0:
                      yield { 'A': A, 'D': D, 'E': E, 'L': L, 'M': M, 'O': O, 'T': T, 'Y': Y }

(This is a slightly simplified version, but you get the idea).

Firstly, this code isn’t elegant. But we don’t really care about that in this instance. No-one is going to look at it, it’s just going to be executed. (I know I have asked you to look at it in this post).

Here’s an explanation of how the generated program works:

(Lines 2-6)

In this example, the only letters we need to consider the values of are T, O, and M, and instead of using itertools.permutations() and rejecting assignments with invalid digits we don’t need to generate possibilities with invalid assignments in the first place.

For example, we don’t need to consider the possibility of T being zero (because leading zeros are not allowed), so we don’t put 0 in the possible values of T. Any other invalid digits assignments can be removed in the same way.

(Lines 7-8)

Once we have the values of T, O, M, we construct the value of TOM and calculate the left-hand side of the expression (TOM × 13).

(Lines 9-18)

We then try and match this result to the value we are looking for (DALEY), by repeatedly examining the final digit. For each digit we examine we either match it an existing assignment (if it is a letter we have already seen), or we check that it is a new assignment (if it is a letter we haven’t already seen).

In this case, all the letters are new, so we just need to check that their values don’t reuse any of the digits we have already assigned. When we get to the leading digit (D) we also need to check that it is non-zero, and that we have used up all the digits of the result.

(Line 19)

If we make it through all that we have found a solution, so we return a dictionary mapping the letters to the digit values.

This approach can easily deal with multiple expressions in a single program — once we have finished with one expression we just generate the code for the next one until all expressions are exhausted. If we reach the end when the code is executed all the expressions are satisfied, and we can return the dictionary for the solution.

I’ve implemented this approach in the enigma.py library (from version 2016-06-25), as the function substituted_expression() and changed the SubstitutedExpression() solver to use this.

Comparative timings are given in the table below, using the examples from the previous article.

The columns are:

1 = Raymond Hettinger’s code, using repeated calls eval() for a single expression, multiple expressions are chained together using “and”. The code is modified so that single digit 0 values are allowed. Note: This can’t deal with expressions in bases other than 10.

2 = The previous version of the enigma.py code, as described in the previous article. It uses a single call to eval() for a single expression, but can chain individual expression solutions together to solve problems involving multiple expressions.

3 = The current version of the enigma.py code, as described in this article. Multiple expressions can be evaluated in a single call to eval().

4 = The SubstitutedSum() solver form the enigma.py library. This can only deal with expressions that are simple sums (but can chain expressions together, operate in different bases and allow initial assignments and invalid assignments).

    1      2      3      4    test
 94.4s   4.6s   0.32s  0.19s  (LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL)
 75.0s   0.44s  0.07s  0.07s  (HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD)
 92.7s   4.2s   0.37s  ----   (SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA)
  2.6s   0.93s  0.11s  ----   (PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S)
 32.0s   0.22s  0.04s  ----   (TOM * 13 = DALEY)
 45.7s   0.26s  0.04s  ----   (CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI)
 47.0s   1.1s   0.14s  ----   ((ENI * GMA) % 1000 = MES) (ENI + GMA = SUM) (I > 2 * U)
109.2s   8.6s   0.99s  ----   (ALPHA + BETA + GAMMA = DELTA) (ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (GAMMA % 3 = 0)
 85.3s   0.19s  0.04s  ----   (ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI)
 ----    7.6s   0.55s  0.31s  (GOLD + DALEY = THOMAS) [base=11]
 ----	55.6s	0.96s  0.08s  (FAREWELL + FREDALO = FLINTOFF) [base=11]
107.9s   2.9s   0.40s  0.07s  (ELGAR + ENIGMA = NIMROD) [O=0]
134.6s   1.3s   0.24s  0.09s  (WILKI + NSON = JONNY) [no digit is 9]
 87.2s   0.48s  0.05s  0.08s  (1939 + 1079 = 6856) [digits cannot stand for themselves]
 78.4s   0.55s  0.08s  ----   (BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE))
 74.1s   2.6s   0.16s  ----   (ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI))
109.6s   0.72s  0.05s  ----   (SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN))
 55.5s   0.44s  0.06s  ----   (M * TIMES = ENIGMA)
 92.0s  12.7s   0.61s  0.10s  (SAINT + GEORGE = DRAGON) (E % 2 = 0)
 59.0s   0.45s  0.06s  ----   (AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC)

As we see, the approach described in this article is generally hundreds of times faster than the repeated eval() approach, and in some tests more than 2000× faster. It is also generally tens of times faster than the approach described in the previous article. In fact it solves each of the example problems in less than 1s and can solve all of the given example Alphametics in less than 6s total runtime.

If you want to see the actual code that is generated by the solver for a particular problem you can pass a value of 3 or more to the verbose parameter of the solver. e.g.:

% python -m enigma Alphametic -v3 "TOM * 13 = DALEY"
...

And the code (as well as some other debugging information) will be output before the solutions.

Thanks for reading.

Advertisements

One response to “Solving Alphametics with Python, Part 2

  1. Jim Randell 20 August 2016 at 9:53 am

    Here is a solution to Sunday Times Teaser 2812 that uses the SubstitutedExpression() solver from the enigma.py library.

    I had added an env parameter to the programmatic interface that allows you to pass additional names into the environment that the expressions are evaluated in.

    In this case we define the grey() function that returns the corresponding number on the grey side of the cards, when passed a number on the white side of the cards (by concatenating multiple digits if necessary). This is then passed into the environment of the substituted expressions using the env parameter to SubstitutedExpression().

    This code runs in 111ms.

    from collections import Counter
    from enigma import nsplit, nconcat, SubstitutedExpression, irange, printf
    
    # map from white to corresponding grey digit
    g = dict((int(a), int(b)) for (a, b) in zip('219654873', '987142365'))
    
    # return the grey number for a corresponding white number <n>
    def grey(n):
      return nconcat(g[x] for x in nsplit(n))
    
    # record solutions by the grey total
    r = Counter()
    
    # solve the sum so the white side and the grey side are both valid
    p = SubstitutedExpression([
        "ABC + DEF = GHI",
        "grey(ABC) + grey(DEF) == grey(GHI)"
      ],
      digits=irange(1, 9),
      env={ 'grey': grey }
    )
    
    # look for solutions
    for s in p.solve():
      (w1, w2, w3) = (int(p.substitute(s, x)) for x in ('ABC', 'DEF', 'GHI'))
      (g1, g2, g3) = (grey(x) for x in (w1, w2, w3))
      printf("[{w1} + {w2} = {w3} / {g1} + {g2} = {g3}]")
      r[g3] += 1
    
    # output solutions
    for (k, n) in r.most_common():
      printf("answer = {k} [{n} solutions]")
    

    (The env parameter to SubstitutedExpression() is available in enigma.py from version 2016-08-14).

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: