A challenge from the Mensa Puzzle Calendar
Chris Myers
things I do in the morning, aside from checking my email, is to try to
solve the daily puzzle. Most of them are word-type problems,
cryptograms, anagrams, age problems, etc., but today's was a nice
numerical challenge that lent itself to writing a program to solve it:
The following multiplication example uses all the digits from 0 to 9,
and X's have been used to represent numbers, not the multiplication
sign.
7XX
XX
-----
XXXXX
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.)
Gregor Lingl
> I have the "Mensa Puzzle Calendar" on my desktop, and one of the first
> things I do in the morning, aside from checking my email, is to try to
> solve the daily puzzle. Most of them are word-type problems,
> cryptograms, anagrams, age problems, etc., but today's was a nice
> numerical challenge that lent itself to writing a program to solve it:
>
>
> The following multiplication example uses all the digits from 0 to 9,
> and X's have been used to represent numbers, not the multiplication
> sign.
>
> 7XX
> XX
> -----
> XXXXX
>
>
> 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.)
Just to contrast yours: a quick and dirty solution using at least
on pythonesque feature:
>>> def contains_all_digits(a,b,c):
x = str(a)+str(b)+str(c)
if len(x) == 9: x+="0" # if one of them has a leading 0
if len(x) != 10:
return 0
for d in "0123456789":
if d not in x:
return 0
return 1
>>> print [(x,y,x*y) for x in range(1000)
for y in range(100)
if contains_all_digits(x,y,x*y)]
[(138, 42, 5796), (157, 28, 4396), (159, 48, 7632), (186, 39, 7254),
(198, 27, 5346), (297, 18, 5346), (297, 54, 16038), (345, 78, 26910),
(367, 52, 19084), (396, 45, 17820), (402, 39, 15678), (483, 12, 5796),
(495, 36, 17820), (594, 27, 16038), (715, 46, 32890), (927, 63, 58401)]
Is this correct?
Regards, Gregor L.
Marco Mariani
> (NOTE: I realize this is not really a Python thingy, but more of an
> algorithm design thingy, but nonetheless, fun.)
Why use an algorithm when you've got a gigahertz CPU and a list
comprehension?
import string
print [ (x,y,x*y) for x in range(1000) for y in range(100)
if map( lambda a: string.count(str(x)+str(y)+str(x*y),a),
map(str,range(10)))==[1]*10 ]
(yes, this goes directly into the python hall of shame together with
my operator module)
Mark McEahern
> 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
news.verizon.net
> 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!
for a in range(700,800):
for b in range(100):
digits = list('%d%d%d' % (a, b, a*b))
digits.sort()
if digits == list('0123456789'):
print '%5d\n%5d\n-----\n%5d' % (a, b, a*b)
Raymond Hettinger
Marco Mariani
> import string
> print [ (x,y,x*y) for x in range(1000) for y in range(100)
> if map( lambda a: string.count(str(x)+str(y)+str(x*y),a),
> map(str,range(10)))==[1]*10 ]
>
> (yes, this goes directly into the python hall of shame together with
> my operator module)
^^^^^^^^
Ehm, pointer module.
BTW, i've tried with permutations but it's even slower, having to loop
10! times...
Greg Ewing
>
> Why use an algorithm when you've got a gigahertz CPU and a list
> comprehension?
That would make a great Python quote!
Does anyone keep a database of such things?
--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg
Steve Holden
news:3D9CF1E9...@something.invalid...
> Marco Mariani wrote:
> >
>
> > Why use an algorithm when you've got a gigahertz CPU and a list
> > comprehension?
>
>
> That would make a great Python quote!
>
> Does anyone keep a database of such things?
>
Andrew Kuchling does: see
http://www.amk.ca/quotations/python-quotes/
regards
-----------------------------------------------------------------------
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/pwp/
Previous .sig file retired to www.homeforoldsigs.com
-----------------------------------------------------------------------
Skip Montanaro
>> Why use an algorithm when you've got a gigahertz CPU and a list
>> comprehension?
Greg> That would make a great Python quote! Does anyone keep a database
Greg> of such things?
Yes, Andrew Kuchling does, though I don't know where it lives off-hand.
Skip
Gerhard Haering
> Greg> Marco Mariani wrote:
> >> Why use an algorithm when you've got a gigahertz CPU and a list
> >> comprehension?
>
> Greg> of such things?
>
> Yes, Andrew Kuchling does, though I don't know where it lives off-hand.
http://www.amk.ca/quotations/python-quotes/
A very good read :-)
-- Gerhard
Mark McEahern
> 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
Chris Myers
I'm sufficiently humbled by looking at the quality of code I've read.
Some of what I saw was pretty complex for my eyes (I'm still looking
over some of it), but IMHO (as OP, judge, and jury for the contest), I
choose Raymond Hettinger's entry, based on elegance, innovation and
brevity:
for a in range(700,800):
for b in range(100):
digits = list('%d%d%d' % (a, b, a*b))
digits.sort()
if digits == list('0123456789'):
print '%5d\n%5d\n-----\n%5d' % (a, b, a*b)
Which can be easily generalized by changing the first line to
for a in range(1000):
and the 3rd line to
digits = list('%.3d%.2d%.5d' % (a, b, a*b))
in order to catch those solutions with operands and results beginning
with '0'.
So, my generalized sol'n of Raymond's answer is:
for a in range(1000):
for b in range(100):
digits = list('%.3d%.2d%.5d' % (a, b, a*b))
digits.sort()
if digits == list('0123456789'):
print '\n%5.3d\n%5.2d\n-----\n%5.5d' % (a, b, a*b)
This generalized solution takes less than 4 seconds to run on my
computer!
My solution, below, took almost 4 MINUTES!! (Again, sufficiently
humbled am I)
def list_less(short_list):
l = range(10)
for i in short_list:
l.remove(i)
return l
for a in list_less([]):
for b in list_less([a]):
for c in list_less([a,b]):
for d in list_less([a,b,c]):
for e in list_less([a,b,c,d]):
for f in list_less([a,b,c,d,e]):
for g in list_less([a,b,c,d,e,f]):
for h in list_less([a,b,c,d,e,f,g]):
for i in list_less([a,b,c,d,e,f,g,h]):
for j in list_less([a,b,c,d,e,f,g,h,i]):
if (100*a + 10*b + c) * (10*d + e) == \
10000*f + 1000*g + 100*h + 10*i + j:
(A,B,C,D,E,F,G,H,I,J) =
(a,b,c,d,e,f,g,h,i,j)
print "\n %d%d%d\nX
%d%d\n-----\n%d%d%d%d%d\n" \
%(A,B,C,D,E,F,G,H,I,J)
I originally thought this was a pretty solution -- not so much
anymore.
Again, thanks, all for accepting my challenge.
Please, post more puzzles of this sort -- anyone.
Cheers,
Chris
PS: Actual solutions to the generalized version of the puzzle:
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
402 * 39 = 15678
483 * 12 = 05796
495 * 36 = 17820
594 * 27 = 16038
715 * 46 = 32890
927 * 63 = 58401
I'm a number theory buff, so I noticed some fascinating things:
two of the sol'ns use one of the same operands - 297
THREE of the sol'ns generated the same product!!
How cool is that?!
:-)
Konrad Koller
Myers) wrote:
>So, my generalized sol'n of Raymond's answer is:
>for a in range(1000):
> for b in range(100):
> digits = list('%.3d%.2d%.5d' % (a, b, a*b))
> digits.sort()
> if digits == list('0123456789'):
> print '\n%5.3d\n%5.2d\n-----\n%5.5d' % (a, b, a*b)
>
Another small changes in Raymond's excellent program:
import string; alldigits=list(string.digits)
for a in range(12,988):
for b in range(1,99):
digits = list('%.3d%.2d%.5d' % (a, b, a*b))
digits.sort()
if digits == alldigits: print '%3u*%2u=%5.5u' % (a, b, a*b)
Nicolas
> [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):
More general wins ?
http://www.logilab.org/python-logic/
http://www.logilab.org/python-logic/constraint.html
http://www.logilab.org/python-logic/documentation.html
ftp://ftp.logilab.org/pub/constraint/
I won ;-)
But now you'll complain that puzzles are not as fun anymore...
--
Nicolas Chauvat
Mark McEahern
> More general wins ?
>
> http://www.logilab.org/python-logic/
> http://www.logilab.org/python-logic/constraint.html
> http://www.logilab.org/python-logic/documentation.html
> ftp://ftp.logilab.org/pub/constraint/
>
> I won ;-)
>
> But now you'll complain that puzzles are not as fun anymore...
Neato. I ran into a MemoryError trying to use this to solve the
puzzle--probably because I'm not using it wisely. Care to post a solution
using your constraint module? I'd enjoy seeing it.
Cheers,
// mark
-
Kevin P. Rice
> Thanks, all for your response to my challenge!
> I'm sufficiently humbled by looking at the quality of code I've read.
>
>
> for a in range(1000):
> for b in range(100):
> digits = list('%.3d%.2d%.5d' % (a, b, a*b))
> digits.sort()
> if digits == list('0123456789'):
> print '\n%5.3d\n%5.2d\n-----\n%5.5d' % (a, b, a*b)
>
>
> This generalized solution takes less than 4 seconds to run on my
> computer!
>
>
Anything that takes 4 seconds on a GHz machine sounds slow to me...
so, just for comparison (fun) I wrote a solution in C++ (see below).
On my 1.6 GHz laptop this code runs in 0.007 seconds -- over 500 times
faster! The code is a bit ugly for efficiency reasons. Also, I store
the results in an array because I found that printing to the screen
took nearly four times as long as the program itself! A cleaner,
easier to comprehend version ran in about 0.02 seconds.
This code also only requires about 50 bytes of memory for storage. I
wrote an assembly language version that requires ZERO storage -- it
solves the entire problem in the CPU registers. Because I don't know
how to optimize assembly code, that version ran slower than the C++
version, though.
Be advised, I'm not deriding Python one bit here. However, it's
important to realize the tradeoffs when choosing one language over
another. And, the puzzle was a fun one, too! Does anyone know if
there's a methodical way to solve it with paper and pencil (i.e, not
brute force)?
// XXX * YY = ZZZZZ
int x2 = 0, x1 = 1, x0 = 3; // storage for x (initial value of x =
013)
int y1, y0; // storage for y (digits 0 & 1)
int z4, z3, z2, z1, z0; // storage for z (digits 0 - 4)
int f; // flag bits for testing uniqueness of digits
int xr[20], yr[20], zr[20], i=0; // result arrays and index
do {
y1 = 1; y0 = 1; // y = 11 (we'd use 12 but it complicates the next
line)
z4 = 0; z3 = x2; z2 = x1; z1 = x0; z0 = 0; // z = x * (y - 1)
do {
if ((z0 += x0) > 9) z0 -= 10, ++z1; // z += x
if ((z1 += x1) > 9) z1 -= 10, ++z2;
if ((z2 += x2) > 9) if (z2 -= 10, ++z3 > 9) z3 -= 10, ++z4;
if (x0 > 1 && y0 > 1) { // skip permutation if x0 or y0 == 0 or 1
f = 1 << x0; f |= 1 << x1; f |= 1 << x2; // set flag bits for
digits
f |= 1 << y0; f |= 1 << y1;
f |= 1 << z0; f |= 1 << z1; f |= 1 << z2; f |= 1 << z3; f |= 1 <<
z4;
if (f == 0x03ff) { // all flags set? VALID PERMUTATION FOUND!
xr[i]=(x2 << 4 | x1) << 4 | x0;
yr[i]=y1 << 4 | y1;
zr[i++]=(((z4 << 4 | z3) << 4 | z2) << 4 | z1) << 4 | z0;
} } } while ((++y0 < 10) || (y0 -= 10, ++y1 < 10));
} while ((++x0 < 10) || (x0 -= 10, ++x1 < 10) || (x1 -= 10, ++x2 <
10));
Erik Max Francis
> Anything that takes 4 seconds on a GHz machine sounds slow to me...
Slow depends on how long you need it to run. If it's a one-shot
program, it doesn't matter how long it takes to run as long as it
finishes before you grow tired of the problem.
> so, just for comparison (fun) I wrote a solution in C++ (see below).
> On my 1.6 GHz laptop this code runs in 0.007 seconds -- over 500 times
> faster! The code is a bit ugly for efficiency reasons.
If right from the start efficiency and speed of the code is of your
utmost concern, then Python isn't the right language for the task. The
point is, in the real world, usually efficiency for its own sake is not
the main criterion; in fact, many other criteria have higher priority.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ Take my advice: Pull down your pants and slide on the ice.
\__/ Dr. Sidney Freedman
Kepler's laws / http://www.alcyone.com/max/physics/kepler/
A proof of Kepler's laws.
Piet van Oostrum
KPR> Anything that takes 4 seconds on a GHz machine sounds slow to me...
KPR> so, just for comparison (fun) I wrote a solution in C++ (see below).
KPR> On my 1.6 GHz laptop this code runs in 0.007 seconds -- over 500 times
KPR> faster! The code is a bit ugly for efficiency reasons. Also, I store
KPR> the results in an array because I found that printing to the screen
KPR> took nearly four times as long as the program itself! A cleaner,
KPR> easier to comprehend version ran in about 0.02 seconds.
if it took you more than 3.993 seconds more to write the C++ version than
the Python version then your C++ version is too slow :=)
--
Piet van Oostrum <pi...@cs.uu.nl>
URL: http://www.cs.uu.nl/~piet [PGP]
Private email: P.van....@hccnet.nl
Kevin P. Rice
> >>>>> b14...@hotmail.com (Kevin P. Rice) (KPR) writes:
>
> KPR> Anything that takes 4 seconds on a GHz machine sounds slow to me...
> KPR> so, just for comparison (fun) I wrote a solution in C++ (see below).
> KPR> On my 1.6 GHz laptop this code runs in 0.007 seconds -- over 500 times
> KPR> faster! The code is a bit ugly for efficiency reasons. Also, I store
> KPR> the results in an array because I found that printing to the screen
> KPR> took nearly four times as long as the program itself! A cleaner,
> KPR> easier to comprehend version ran in about 0.02 seconds.
>
> if it took you more than 3.993 seconds more to write the C++ version than
> the Python version then your C++ version is too slow :=)
Yes, that's nice to know. But with that logic the Python version is
much too slow also since there's already a working program that does
the same thing (see below), and, it's faster than 4 seconds, too...
Did I mention this was for fun? Thanks for the jab-- I think the point
was that (1) speed is relative, (2) Python is nice, but it's not
universal, and, (3) how many BILLION instructions does it take to boot
Windows, anyway? There's only 128 MB or so of memory to fill up--that
should only take 0.1 seconds, right??!!?
Cryptarithm solver:
DEAN v.2.00 (C source)
http://www.und.edu/org/crypto/crypto/cryptarithm/dean/
DEAN v.1.00 (compiled .exe for MS-DOS):
ftp://ftp.simtel.net/pub/simtelnet/msdos/educate/dean100.zip
For the Mensa puzzle create a text file with the following:
abc*de=fghij;a=7
Then run DEAN 'file' to get the puzzle solution!