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 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 13 years, 4 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 13 years, 1 month ago

This program is also an example of how painful unicode defaults can make a pretty program. Sean Jones 11 years, 4 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)