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
More information about the Python-list
mailing list