#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Solve <http://blog.plover.com/prog/monad-search-2.html> with a genex.

Assign unique digits to the letters to make this true (“cryptorithm”):

      S E N D
    + M O R E
    ---------
    M O N E Y

This version *is* lazy, although in this case that probably doesn’t
matter much since the solution is unique.

The optimized version is almost two orders of magnitude faster.

"""
from __future__ import division

def straightforward():
    digits = set(range(10))
    return (  '%s%s%s%s + %s%s%s%s = %s%s%s%s%s'
            % (s,e,n,d,   m,o,r,e,   m,o,n,e,y)
            for s in digits - {0}
            for e in digits - {s}
            for n in digits - {s, e}
            for d in digits - {s, e, n}
            for send in [((s*10+e)*10+n)*10+d]
            for m in digits - {0,s,e,n,d}
            for o in digits - {s,e,n,d,m}
            for r in digits - {s,e,n,d,m,o}
            for more in [((m*10+o)*10+r)*10+e]
            for y in digits - {s,e,n,d,m,o,r}
            for money in [(((m*10+o)*10+n)*10+e)*10+y]
            if send + more == money)

def fast():
    """Optimize a bit with some early pruning.

    This reduces the search space to make it finish in 61 ms instead
    of 7800ms on my netbook.  This is probably as fast as I can
    measure from the command line.
    """
    digits = set(range(10))
    return (  '%s%s%s%s + %s%s%s%s = %s%s%s%s%s'
            % (s,e,n,d,   m,o,r,e,   m,o,n,e,y)
            for s in digits - {0}
            for m in digits - {0, s}
            for snm in [s + m, s + m + 1] # there might be a carry!
            if m == snm // 10   # `//` is floor division (“int division”)
            for o in {snm % 10} - {s, m}
            for e in digits - {s, m, o}
            for d in digits - {s, e, m, o}
            for y in {(d + e) % 10} - {s, e, d, m, o}
            for n in digits - {s, e, d, m, o, y}
            for send in [((s*10+e)*10+n)*10+d]
            for money in [(((m*10+o)*10+n)*10+e)*10+y]
            for r in digits - {s, e, n, d, m, o, y}
            for more in [((m*10+o)*10+r)*10+e]
            if send + more == money)

if __name__ == '__main__':
    print fast().next()
    print straightforward().next()