A challenge from the Mensa Puzzle Calendar

[Mark McEahern]

[Marco Mariani]
> BTW, i've tried with permutations but it's even slower, having to loop
> 10! times...

Um, it's a puzzle.  Who cares how slow it is?  Have a beer, kick back,
relax, and let the bloody thing churn.

For what it's worth, here's a generalized solution that lets you plug in
somewhat arbitrary equations with single or multiple fixed digits (i.e.,
like '7' in this one):

You can run it like this (note the '7' has become an 'X'):

  a = "XXX"
  b = "XX"
  c = "XXXXX"
  replace = "X"
  replacewith = "1234567890"

  equation = "int(p[0:3]) * int(p[3:5]) == int(p[5:10])"
  equation_print = "'%s * %s == %s' % (p[0:3], p[3:5], p[5:10])"

  for p in solve_equation(equation, a+b+c, replace, replacewith):
      print eval(equation_print)

Output:

  138 * 42 == 05796
  157 * 28 == 04396
  159 * 48 == 07632
  186 * 39 == 07254
  198 * 27 == 05346
  297 * 18 == 05346
  297 * 54 == 16038
  345 * 78 == 26910
  367 * 52 == 19084
  396 * 45 == 17820
  483 * 12 == 05796
  495 * 36 == 17820
  402 * 39 == 15678
  ...

And, the code...

#!/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 that looks like this:

def solve_equation(equation, string):
    ...

Of course, it should be generalized not to assume the first digit is
supplied.

"""

from __future__ import generators

def solve_equation(equation, x, replace="X", replacewith="123456890"):
    """Solve the equation for any permutation of the replacement characters
    for the replace character in x."""
    supplied_digits = {}
    for i in range(len(x)):
        if x[i] != replace:
            supplied_digits[i] = x[i]
    assert len(x) - len(supplied_digits) == len(replacewith)
    for i in permIter(replacewith):
        p = i
        keys = supplied_digits.keys()
        keys.sort()
        for pos in keys:
            p = p[:pos] + supplied_digits[pos] + p[pos:]
        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

# --------------------------------------------------------------------------
---
# Using it
# --------------------------------------------------------------------------
---

a = "7XX"
b = "XX"
c = "XXXXX"
replace = "X"
replacewith = "123456890"

equation = "int(p[0:3]) * int(p[3:5]) == int(p[5:10])"
equation_print = "'%s * %s == %s' % (p[0:3], p[3:5], p[5:10])"

for p in solve_equation(equation, a+b+c, replace, replacewith):
    print eval(equation_print)

a = "XXX"
b = "XX"
c = "XXXXX"
replace = "X"
replacewith = "1234567890"

equation = "int(p[0:3]) * int(p[3:5]) == int(p[5:10])"
equation_print = "'%s * %s == %s' % (p[0:3], p[3:5], p[5:10])"

for p in solve_equation(equation, a+b+c, replace, replacewith):
    print eval(equation_print)

***

Cheers,

// m