ActiveState Code

Recipe 576615: Alphametics solver

Solves numeric cryptograms listed in Knuth Volume 4 Fascicle 2.

Python 
 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
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)
            if eval(equation):
                print equation

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',
    ]:
    print alphametic
    solve(alphametic)
    print

Discussion

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.

Comments

  1. 1. At 6:23 p.m. on 26 jan 2009, Michael Woodhams said:

    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 http://slashdot.org poster.)

  2. 2. At 11:13 p.m. on 24 apr 2009, charles.merriam tollak said:

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

Sign in to comment