Optimizing code – Part 5

So for the smart people out there they might have already figured out that the result for 153 is the same as for 135,315,351,513 and 531. This means that we can calculate the result for all of those once and just check if the result of that calculation is in that list. Which is the case for the number 153.

Online Encyclopedia Integer Sequences

There exists an online database of integer sequences. It has a lot of cool sequences and one of them is the one with all Narcissistic Numbers. It has number A005188 and you can find it here.

This next code is inspired and based on the code in the OEIS.

Code

from itertools import combinations_with_replacement
from datetime import datetime
import sys

POWERS = [0,1,2,3,4,5,6,7,8,9]
NARCISSISTIC_NUMBERS = []

def recalculate_powers():
    for i,v in enumerate(POWERS):
        POWERS[i] = i * v

def equals(number: int, target: tuple) -> bool:
    digits = []
    while number > 0:
        _, number = digits.append(number % 10), number // 10
    return tuple(sorted(digits)) == target



def find_narcissistic_numbers(desired: int) -> None:
    global POWERS, NARCISSISTIC_NUMBERS
    for k in range(1, sys.maxsize):

        for b in combinations_with_replacement(range(10), k):

            x = sum(map(lambda y:POWERS[y], b))
            if x > 0 and equals(x, b):
                NARCISSISTIC_NUMBERS.append(x)
                if len(NARCISSISTIC_NUMBERS) == desired:
                    return
        recalculate_powers()

start = datetime.utcnow()
find_narcissistic_numbers(28)
print(datetime.utcnow() - start)

The combinations_with_replacement gets numbers 0-9 and how many times to do it. So for example when k = 2 you get:

[0,0] [0,1] ... [1,1] ... [2,2] ... [9,9]

And as you can see you lose one number every time you go up in tens. As 0,1 is equal to 1,0 and 1,2 is equal to 2,1. There are considerable amount of fewer computations to check.

So this code takes this much time to run on my laptop: 0:00:00.204806

That is an insane speedup in time compared to the naive implementation and the optimized implementation.

Caveat

Small thing I found out whilst running this code. I thought it was enough to do sorted((2,1)) but this returns a list!!. So then I needed to wrap that with another tuple or the other one with list and I did not want to do that. So therefore I went with the initial list and turn that into a tuple.

#code #python