Need optimization for Project Euler problem 74 sol2.py

[dhruvmanila]

Due to the acceptance of Project Euler problem 74 sol2.py, our tests are taking a long time to finish.

validate-solutions: [4:34] https://github.com/TheAlgorithms/Python/pull/3016/checks?check_run_id=1369207443#step:5:24
project-euler: [9:00] https://github.com/TheAlgorithms/Python/pull/3016/checks?check_run_id=1369207451#step:5:286

NOTE: We do not want a new solution for the problem but rather an optimized version for it. Take it as a challenge in optimization. Good luck!

[crazazy]

This seems like a similar problem that I solved before when I submitted a solution for Euler 14 #2216

Since you're bound to do the same few calculations a few times over, here are some hints (which I can't be bothered to program in right now)

1. you only calculate the factorials from 0 through 9. it might be handy to keep a list of all the factorials a la

factorials = [1] # 0! = 1
for i in range(1,10):
    factorials.append(factorials[-1]*i)

That way you make use of the recursive nature of factorials while also providing a list of them
2. If you found a chain of factorials that reduce to a number you previously calculated, you shouldn't need to calculate any further, if you come across that chain again from another number. Otherwise you'll just be calculating the chain twice, which is inefficient

Maybe that helps for the people that want to help optimize this problem

[tacitvenom]

Thanks a lot @crazazy
Factorial cache was my first hunch as well. I just assumed that would fix it. Turns out not be the case. Perhaps my implementation was naive (worse still, wrong!).
I tried the chain thing locally, doesn't help too much either.
I tried implementing set operations instead of list, again just marginal benefits

One thing that definitely stands out is i sol2.py doctest runs twice and on large numbers:
>>> solution(60,1000000) 402 >>> solution(15,1000000) 17800
as compared to sol1.py where there's just:
>>> solution(10,1000) 28

Changing this definitely saved me time locally. While I agree this is not the most elegant way out, but I feel it's rather smart.
I would like to know your inputs before opening a PR with the three cosmetic changes described above with marginal improvements and changing the docstring for solution(). @crazazy @dhruvmanila

Also, when I compared the two solutions, I think, they will not always give identical results. For example, using the example for sol1.py in sol2.py gives:
077 >>> solution(10,1000)
Expected:
28
Got:
26

I would call it a bug, but maybe I missed something. I hope this is not expected behaviour. Would also be happy to work on it, if this is opened separately as an issue.