Project Euler 92: sum of squares of digits until a loop is encountered

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

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.

StackExchange Code Review Q#115049, answer score: 4