# A challenge from the Mensa Puzzle Calendar

Mark McEahern marklists at mceahern.com
Fri Oct 4 07:20:53 CEST 2002

```[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

```