Solves numeric cryptograms listed in Knuth Volume 4 Fascicle 2.
Python, 60 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | from __future__ import division
from itertools import permutations
from re import findall
from string import maketrans
def solve(s):
'''Find solutions to alphametic equations.
>>> solve('SEND + MORE == MONEY')
9567 + 1085 == 10652
'''
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)
n = len(firsts) # chars[:n] cannot be assigned zero
for perm in permutations('0123456789', len(chars)):
if '0' not in perm[:n]:
trans = maketrans(chars, ''.join(perm))
equation = s.translate(trans)
try:
if eval(equation):
print equation
except ArithmeticError:
pass
for alphametic in [
'SEND + MORE == MONEY',
'VIOLIN * 2 + VIOLA == TRIO + SONATA',
'SEND + A + TAD + MORE == MONEY',
'ZEROES + ONES == BINARY',
'DCLIZ + DLXVI == MCCXXV',
'COUPLE + COUPLE == QUARTET',
'FISH + N + CHIPS == SUPPER',
'SATURN + URANUS + NEPTUNE + PLUTO == PLANETS',
'EARTH + AIR + FIRE + WATER == NATURE',
('AN + ACCELERATING + INFERENTIAL + ENGINEERING + TALE + ' +
'ELITE + GRANT + FEE + ET + CETERA == ARTIFICIAL + INTELLIGENCE'),
'TWO * TWO == SQUARE',
'HIP * HIP == HURRAY',
'PI * R ** 2 == AREA',
'NORTH / SOUTH == EAST / WEST',
'NAUGHT ** 2 == ZERO ** 3',
'I + THINK + IT + BE + THINE == INDEED',
'DO + YOU + FEEL == LUCKY',
'NOW + WE + KNOW + THE == TRUTH',
'SORRY + TO + BE + A + PARTY == POOPER',
'SORRY + TO + BUST + YOUR == BUBBLE',
'STEEL + BELTED == RADIALS',
'ABRA + CADABRA + ABRA + CADABRA == HOUDINI',
'I + GUESS + THE + TRUTH == HURTS',
'LETS + CUT + TO + THE == CHASE',
'THATS + THE + THEORY == ANYWAY',
'1/(2*X-Y) == 1',
]:
print alphametic
solve(alphametic)
print
|
Requires Python 2.6 or later. Searches of all permutations of character-to-digit translations, finding all solutions where the that evaluate to True. Skips permutations that translate any leading digit to zero (i.e. "0789" is not a valid translation for "SEND"). Any valid python expression can be evaluated. Catches and skip arithmetic errors such as dividing by zero.
Or you can do it more compactly in Perl.
WARNING: The following is not for the faint of heart, or those who feel that having a comprehensible program is more important than saving a byte.
/\pL/?map{($t=$a)=~s/$&/$_/g;$a!~$_&&push@ARGV,$t}0..9:/\b0\d/||eval&&print"$_\n"while$_=$a=pop
(Except put a real newline character instead of \n so save another byte: I couldn't get this to display properly) And note that it doesn't need to call some 'permutations' library routine.
(Credits: I wrote a solver in 133 bytes using a permutation generator, and showed it to John Hudson (mathematician, Massey University) who had the idea of using @ARGV for temporary storage. His program was then shortened by myself and then an anonymous slashdot.org poster.)
This program is also an example of how painful unicode defaults can make a pretty program.
Why are you importing division from __future__? It doesn't seem like it is necessary at all.