5
\$\begingroup\$

This is my solution to Project Euler #92:

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

I was wondering how the code looks from a Pythonic perspective: is there anything that could be better? Cleaner? Is there anything that can be improved upon from a performance perspective?

from itertools import (
    islice,
    combinations_with_replacement,
    groupby
)
import operator

def get_digits(num):
    for c in str(num):
        yield int(c)

def sum_sq_digits(d):
    return sum(i*i for i in d)

def memoize(f):
    cache = {}
    def wrapped(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return wrapped

@memoize
def sum_sq_chain(num):
    if num in (1, 89):
        return num

    return sum_sq_chain(sum_sq_digits(get_digits(num)))

def fact(i):
    return reduce(operator.mul,
        xrange(1, i+1),
        1)

count = 0
for digits in islice(
        combinations_with_replacement(range(10), 7),
        1,
        None):

    if sum_sq_chain(sum_sq_digits(digits)) == 89:
        cur = fact(7)
        for _, v in groupby(digits):
            cur //= fact(len(list(v)))
        count += cur

print count
\$\endgroup\$
1
  • \$\begingroup\$ For an alternate way of solving this, you could take a look at this answer. \$\endgroup\$
    – holroy
    Commented Dec 25, 2015 at 22:09

1 Answer 1

4
\$\begingroup\$

Prefer integer arithmetic

def get_digits(num):
    while n:
        yield n % 10
        n //= 10

Integer arithmetic is way faster than string convertion and manipulation, so this alternate version improves the efficiency of the code.

Give names appreciating the generality of your functions

sum_sq_digits works on any integer list. It works on any integer sequence, not just digits, but your name hints that it only works on a list of digits. I would rename it: sum_squared

Make a final function

I like that you wrote many small functions, it really helps readibility, I suggest going the last step and writing a function to solve the problem:

def chain_ending(limit, target)
   for digits in islice(
      combinations_with_replacement(range(10), limit),
      1,
      None):

      if sum_sq_chain(sum_sq_digits(digits)) == target:
          cur = fact(limit)
          for _, v in groupby(digits):
              cur //= fact(len(list(v)))
          yield curr

This way testing it is simpler and you may reuse it with different parameters. To get the final answer, just sum the generator this function yields.

Re-use

You will want to reuse as much as possible of your logic, to avoid duplicating work and possible errors.

The factorial function makes use of an in-place-defined product, I think that a separate product function will make code a little more English-like and will save you effort from re-writing it as getting the product of a sequence is a common task.

By the same point of view, using if __name__ == "__main__" allows you to import the script without running it, enabling re-use.

Comments for non-obvious algoritmhs

You do not use plain bruteforce to solve the problem, that is good, but you should leave a comment whenever you use a non-obvious algoritmh, or a link to an explanation of it.

Good

Overall this is good, clear, modular code.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.