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

29 June 2016

Posted by on 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

%d bloggers like this:

Here is a solution to

Sunday Times Teaser 2812that uses theSubstitutedExpression()solver from theenigma.pylibrary.I had added an

envparameter 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 theenvparameter toSubstitutedExpression().This code runs in 111ms.

(The

envparameter toSubstitutedExpression()is available inenigma.pyfrom version 2016-08-14).