Solve Verbal Arithmetic in Python

VerbalArithmetic.py

# -*- coding: utf-8 -*-
#
# https://www.udacity.com/course/cs212

import re, itertools, string

def fill_in(formula):
	letters = ''.join(set([s for s in formula if s in string.uppercase]))
	for i in itertools.permutations('0123456789', len(letters)):
		trans = string.maketrans(letters, ''.join(i))
		yield string.translate(formula, trans)

def valid(f):
	"Return True if the statement eval to True, eg: 1+1==2"
	try:
		return not re.search(r'\b0[0-9]', f) and eval(f) is True
	except ArithmeticError:
		return False

def solve(formula):
	return (f for f in fill_in(formula) if valid(f))

#####################################################################################################

# lambda E, D, M, O, N, S, R, Y: (1*D+10*N+100*E+1000*S)+(1*E+10*R+100*O+1000*M)==(1*Y+10*E+100*N+1000*O+10000*M)

def compile_word(word):
    if word.isupper():
        terms = ['%d*%s' % (10**i, d)
                for i, d in enumerate(word[::-1])]
        return '(' + '+'.join(terms) + ')'
    else:
        return word

def compile_formula(formula, verbose=False):
    letters = set(re.findall('[A-Z]', formula))
    terms = re.split('([A-Z]+)', formula)
    params = ', '.join(letters)
    expr = ''.join(map(compile_word, terms))
    f = 'lambda %s: %s' % (params, expr)
    if verbose: print f
    return eval(f), ''.join(letters)

def faster_solve(formula):
    f, letters = compile_formula(formula, True)

    for digits in itertools.permutations(range(10), len(letters)):
        try:
            if f(*digits) is True:
                table = string.maketrans(letters, ''.join(map(str, digits)))
                r = string.translate(formula, table)
                if not re.search(r'\b0[0-9]', r):
                    yield r
        except ArithmeticError:
            pass

#####################################################################################################

#for s in faster_solve('SEND+MORE==MONEY'):
for s in solve('SEND+MORE==MONEY'):
	print s