Programming Enigma Puzzles
From New Scientist #2744, 23rd January 2010 [link] [link]
In the addition sum above the digits have been replaced by letters and smiley faces. Different letters stand for different digits, the same letter stands for the same digit, a smiley face can be any digit, and leading digits cannot be zero.
If FIVE is divisible by 5 and ELEVEN is divisible by 11, what number is FIFTEEN?
[enigma1579]
 | Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
The following Python program runs in 45ms.
from itertools import permutations from enigma import concat # FIVE is divisible by 5 (hence E is 0 or 5). # ELEVEN is divisible by 11 (and can't have a leading 0). # Hence E = 5. E = 5 # consider the FI+IV+VE = TE part of the sum (10^3 10^2) # the carry coming in is c2 = 0, 1 or 2 d1 = set(range(10)).difference((E,)) for (F, I, V) in permutations(d1, 3): if F < 2: continue TE = 10 * (F + I + V) + (I + V + E) (d, r) = divmod(TE, 10) c2 = 5 - r if not c2 in (0, 1, 2): continue (c4, T) = divmod(d, 10) d2 = d1.difference((F, I, V, T)) for L in d2: ELEVE0 = int(concat(E, L, E, V, E)) * 10 N = 11 - (ELEVE0 % 11) d3 = d2.difference((N,)) if len(d3) != 4: continue # consider the V + E + ? = E column (10^1) for c1 in (0, 1, 2, 3): if not(0 <= 10*c2 - (V + c1) < 10): continue # consider the ? + E + ? + ? column (10^0) if not(0 <= 10*c1 + N - E < 28): continue # consider the ? + F + I = F column (10^4) for c5 in (0, 1, 2): if not(0 <= 10*c5 - (I + c4) < 10): continue # consider the ? + ? + F = I column (10^5) for c6 in (0, 1, 2): if not(0 <= (10*c6 + I) - (F + c5) < 19): continue # consider the ? + ? + ? = F column (10^6) if not(2 < F - c6 < 10): continue print("FIFTEEN={FIFTEEN} FIVE={FIVE} ELEVEN={ELEVEN}".format(FIFTEEN=concat(F, I, F, T, E, E, N), FIVE=concat(F, I, V, E), ELEVEN=ELEVE0+N))Solution: FIFTEEN = 4043551.
% A Solution in MiniZinc % a % b c d F I V E % e f F I V E g % h F I V E i j % ------------- % F I F T E E N % ------------- include "globals.mzn"; var 0..9:F; var 0..9:I; var 0..9:V; var 0..9:E; var 0..9:T; var 0..9:N; var 0..9:L; constraint all_different([F, I, V, E, T, N, L]); var 0..9:a; var 0..9:b; var 0..9:c; var 0..9:d; var 0..9:e; var 0..9:f; var 0..9:g; var 0..9:h; var 0..9:i; var 0..9:j; var 0..3:carry1; var 0..3:carry2; var 0..3:carry3; var 0..3:carry4; var 0..3:carry5; var 0..3:carry6; var 0..3:carry7; constraint F!= 0 /\ a != 0 /\ b!= 0 /\ e != 0 /\ h != 0; % Adding columns from right-hand end.. constraint (a + E + g + j) mod 10 == N /\ (a + E + g + j) div 10 == carry1; constraint (V + E + i + carry1) mod 10 == E /\ (V + E + i + carry1) div 10 == carry2; constraint (I + V + E + carry2) mod 10 == E /\ (I + V + E + carry2) div 10 == carry3; constraint (F + I + V + carry3) mod 10 == T /\ (F + I + V + carry3) div 10 == carry4; constraint (d + F + I + carry4) mod 10 == F /\ (d + F + I + carry4) div 10 == carry5; constraint (c + f + F + carry5) mod 10 == I /\ (c + f + F + carry5) div 10 == carry6; constraint (b + e + h + carry6) == F; constraint (F*1000 + I*100 + V*10 + E) mod 5 == 0; constraint (E*100000 + L*10000 + E*1000 + V*100 + E*10 + N) mod 11 == 0; solve satisfy; output ["FIFTEEN = " ++ show(F),show(I),show(F),show(T),show(E),show(E),show(N)] ++ [", FIVE = " ++ show(F),show(I),show(V),show(E)] ++ [", ELEVEN = " ++ show(E),show(L),show(E),show(V),show(E),show(N)]; % FIFTEEN = 4043551, FIVE = 4085, ELEVEN = 565851 % Finished in 63msec@geoffrounce: I’m a curious how you time MiniZinc models since it’s so much faster than when I run them. For you model my fastest machine runs in 122ms. This includes both the flattening to .fzn file and solving.
Here’s how I time it using Gecode (on a Linux Ubuntu machine) where the model is named test71.mzn:
It is then converted (by minizinc) to these two command:
Perhaps you have that fast machine…
@hakank: I run the code on a laptop with an I7 64-bit processor and Windows 10 Pro. I run it several times in the MinZinc IDE, mostly with the Geocode bundled solver. Usually the run-time improves and I take the the best time. For most Enigma puzzles I seem to get between 60 and 90 msec with this method.
@ Jim: Can you say what sort of run-times you get for MiniZinc and by which method?
I use the built-in [[
time]] function of my shell (Z-shell) to measure the run time of a command line. That way I can get a reasonable comparison between different implementations.In this case I saved the MiniZinc model to a file and executed it using the [[
mzn-gecode -a]] solver like this:I run the command a number of times (usually 16 times for a program that takes less than 1 second), and report the best elapsed time.
So, according to my methodology, the model Geoff posted (7th August 2017 at 4:04pm) executes in 84ms.
My timings are done using a 13″ MacBook Pro (Late 2011 model, with a 2.4 GHz Intel Core i5 processor). This is the same laptop I’ve been using since I started Enigmatic Code, so timings should be roughly comparable between my posts (although software has been updated during that time).
@geoffrounce: Thanks. I also usually run it a couple of time and then take some average of the values. By skipping the call to solns2out it saved about 30ms, to 90ms.