A challenge from the Mensa Puzzle Calendar

[Mark McEahern]

> I wrote (IMHO) a very nice piece of python code to solve this for me,
> and then generalized it a bit: What if the first digit (7) is not
> given?  How many unique solutions do we get and what are they? (I
> included those numbers that started with 0 for consistency.)
> 
> I'm a puzzle kind of guy, so I thought some of you might be, too.
> I'd be very curious to see the kind of solutions people come up with.
> My solution ended up being a total of 19 lines of code, including a
> print statement to give me a nice formatted output for each solution,
> resembling the initial problem from the calendar.
> 
> OK, folks.  The gauntlet is down.  Have at it!
> 
> (NOTE: I realize this is not really a Python thingy, but more of an
> algorithm design thingy, but nonetheless, fun.)

Nice puzzle.  This is my first stab.  It could easily be more general.

#!/usr/bin/env python

"""

In the following multiplication statement, all digits 0-9 are used and
are represented with X:

     7XX
      XX
   -----
   XXXXX

Solutions:  try all possible combinations?  Think of it as a string like
this:

  7XXXXXXXXX

You then have a function:

def solve_equation(equation, string):
    ...

"""

from __future__ import generators

def solve_equation(equation, x, replace="X", replacewith="123456890"):
    # There are hints here of how to generalize this further.
    # To generalize, don't assume first digit is the one we don't fiddle.
    supplied_digit = x[0]
    # seq = x[1:]
    # assert len(seq) == len(replacewith)
    for i in permIter(replacewith):
        p = str(supplied_digit) + str(i)
        if eval(equation):
            yield p

def permIter(seq):
    """Given some sequence 'seq', returns an iterator that gives
    all permutations of that sequence.

    Source: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962

    """
    ## Base case
    if len(seq) == 1:
        yield(seq[0])
        raise StopIteration

    ## Inductive case
    for i in range(len(seq)):
        element_slice = seq[i:i+1]
        rest_iter = permIter(seq[:i] + seq[i+1:])
        for rest in rest_iter:
            yield(element_slice + rest)
    raise StopIteration


a = "7XX"
b = "XX"
c = "XXXXX"

equation = "int(p[0:3]) * int(p[3:5]) == int(p[5:10])"

for p in solve_equation(equation, a+b+c):
    print p