I happen to take a look to this old post in this blog. The post is 7 years old, but still presents an interesting problem.

“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.”

I wanted to check my old solutions again, with the things that I learn in the last years. At that time, I was still a newbie in Python, and there are certainly interesting points to check again.

Python 2 vs Python 3

The first interesting difference is the fact that Python3 is now quite mature, and there’s really no excuse for not using it as a default for small exercises or new projects.

The code can actually be adapted into running both in Python 2 and 3 to make comparisons:

import operator
from itertools import combinations
from functools import reduce
from decimal import Decimal

def solve(number, step, number_of_numbers):
  integer_range = int(number / step)
  all_numbers = (Decimal(i) * step
for i in range(1, integer_range + 1))
  multiples = 1 / (step ** number_of_numbers)
  correct_numbers = (i for i in all_numbers
                     if (number * multiples % i) == 0)

  def check(numbers):
    """Check the numbers added and multiplied are the same"""
    return (sum(numbers) == number
            == reduce(operator.mul, numbers))
  # only combinations are required, as order is irrelevant
  comb = combinations(correct_numbers, number_of_numbers)
  results = [p for p in comb if check(p)]
  return results

print(solve(number=Decimal('7.11'), step=Decimal('0.01'),
            number_of_numbers=4))

I changed a couple of things, like the usage of filter and reduce and better usage of list comprehensions, but the code is very similar. Obtain the numbers that are multiples or the total (as they are the only possible ones to fulfil the criteria), and then try all combinations.

I removed the internal time check, using instead the UNIX one, calling it at bash:

$ time python2.7 711.py
[(Decimal('1.20'), Decimal('1.25'), Decimal('1.50'), Decimal('3.16'))]

real 1m26.020s
user 1m22.199s
sys 0m1.124s

$ time python3.6 711.py
[(Decimal('1.20'), Decimal('1.25'), Decimal('1.50'), Decimal('3.16'))]

real 0m1.148s
user 0m0.955s
sys 0m0.030s

The time difference is quite staggering. 1 second vs 90. They clearly have spend time in optimise Decimal in Python3

Crunching numbers

For the second version of the code, the code is like this

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))
          return

wich, this time, is actually slower in python3, and slower than the first solution.

time python2.7 711_v2.py
w: 120 x: 125 y: 150 z: 316

real	0m7.963s
user	0m7.362s
sys	0m0.291s
$ time python3.6 711_v2.py
w: 120 x: 125 y: 150 z: 316

real	0m13.193s
user	0m11.955s
sys	0m0.461s

But, there are two tricks that can be used in this case.

The first one is a simple replacement for PyPy, which indeed speeds up things.

$ time pypy 711_v2.py
w: 120 x: 125 y: 150 z: 316

real	0m2.413s
user	0m0.177s
sys	0m0.094s

Not sure why, but the results where from ~200ms up to 4 seconds, which is quite a variability.

And the second one is to use Cython to compile the code into a C extension. This requires making two files:

# This compiles the extension automatically
import pyximport; pyximport.install()
from c711v3 import calc
calc()

and a c711v3.pyx file, with the Cython code.

def calc():
  # define the variables as C types
  cdef int w, x, y, z
  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))
          return

This speeds up the process sensibly, to a quarter of a second:

$ time python 711_v3.py
w: 120 x: 125 y: 150 z: 316

real	0m0.223s
user	0m0.138s
sys	0m0.070s

Not bad from 90 seconds at the start!

Conclussions

• Python3 has a lot of optimisations, sometimes in non-obvious places. It should be the version to go unless there are legacy requirements.
• It’s also quite simple to keep code compatible with Python2 and Python3 for easy stuff.
• I can look at code I wrote 7 years ago and find ways of improving it… Good to feel like I know more.
• PyPy is another useful tool that should be considered. It’s also getting better and betters and now it has as well Python3 compatibility. Also, my blog has been around for a while (though I don’t update it as often as I should)
• Creating C extensions with Cython is very easy when dealing with certain bottlenecks.
• And I still find joy in coding small exercises!