There’s an fun and not very difficult programming exercise, presented on Programming Praxis . The problem is easy to describe:

“A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.”

Ok, the problem is easy to get on a brute force approach. Just try all the combinations, see their sum and multiplication, and find the one that gets it. Well, easy, but a lot of work to do for a modern computer. Get all the possible combination will be an amazingly great number of combinations (711 possible prices to the power of 4 gives 255,551,481,441 possibilities).

To simplify the calculations, we change the domain from 7.11 to 711, so get get the prices multiplied has to be equal to 711,000,000.

The proposed solution is to consider only the prices that are divisors of 711,000,000, reducing drastically the combinations.

I’ve tried a solution using a Python code, as follows. I added some “generic” touch and the Decimal type to avoid problems with float comparison:

def solve(dec_number, step, number_of_numbers):

integer_range = int(dec_number * 100)
all_numbers = [ Decimal(i) * step for i in range(1, integer_range) ]
multiples = 1 / reduce(operator.mul, [step] * (number_of_numbers))
correct_numbers = [ i for i in all_numbers if (dec_number * multiples % i) == 0 ]

def check(numbers):
"""Check the numbers added and multiplied are the same"""
return sum(numbers) == dec_number == reduce(operator.mul, numbers)

#it's naive to get only the combinations, but it's faster
posibilities = combinations(correct_numbers, number_of_numbers)
filter_mul = ifilter(check, posibilities)

return list(filter_mul)

t1 = time.time()
print solve(dec_number=Decimal('7.11'), step=Decimal('0.01'), number_of_numbers=4)
t2 = time.time()
print "time 7.11: ", ((t2 - t1))

and that gives an amazing time of 96 seconds! That’s clearly a lot. After that, I tried a completely different approach, just a not-so-brute solution, making a big loop with some tweaks to avoid all the combinations.

def calc():
     for w in range(711):
         for x in range(711 - w):
             for y in range(711 - w - x):
                 z = 711 - x - y - w;
                 if (w * x * y * z == 711000000):
                     print "w: %d x: %d y: %d z: %d" % (w, x, y, z)

     #Measuring time
 t1 = time.time()
 calc()
 t2 = time.time()
 print "time loop: ", ((t2 - t1))

For a total time of 34 seconds! And all the solutions! (which, BTW are the same, just reordered)

After some profiling, I’ve get the solution to this strange behavior. The use of the Decimal type.

LESSONS LEARNED:

– Decimal seems to be a “little” unefficient.

– Try to use basic types when making a lot of calculations.

– Don’t understimate the power of brute force, combined with low level languages. I’ve tried the same loop on C, and takes about 1/3 seconds.