Welcome, guest | Sign In | My Account | Store | Cart

Solves numeric cryptograms listed in Knuth Volume 4 Fascicle 2.

Python, 60 lines
 ``` 1 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.

Michael Woodhams 15 years, 2 months ago

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

charles.merriam tollak 14 years, 12 months ago

This program is also an example of how painful unicode defaults can make a pretty program.

Sean Jones 13 years, 3 months ago

Why are you importing division from __future__? It doesn't seem like it is necessary at all.

 Created by Raymond Hettinger on Wed, 14 Jan 2009 (MIT)