Repository navigation
Optimize Project Euler solutions #8594
Description
Feature description
If someone would like to take a stab at optimizing these solutions, feel free to open a PR or ask for any help here:
Slowest 10 durations
- Problem 145 / sol1.py (25.00s)
- Problem 070 / sol1.py (13.86s)
- Problem 104 / sol1.py (6.84s)
- Problem 092 / sol1.py (6.01s)
- Problem 010 / sol2.py (3.90s)
- Problem 010 / sol1.py (3.76s)
- Problem 078 / sol1.py (3.67s)
- Problem 135 / sol1.py (3.59s)
- Problem 073 / sol1.py (2.64s)
- Problem 034 / sol1.py (2.54s)
Reference: https://github.com/TheAlgorithms/Python/actions/runs/4580132675/jobs/8088552368#step:5:356
Activity
ankit-gautam23 commentedon Apr 7, 2023
Is this still open??
dhruvmanila commentedon Apr 8, 2023
Yes
MatthiasHeinz commentedon Jun 16, 2023
Regarding problem 034, I've stumbled upon this proof .
This proof lowers the upper bound from the current
limit = 7 * factorial(9) + 1 # 2,540,161to 1,499,999, which eliminates 40% of values to be considered. Considering this eliminates the biggest values, this probably cuts runtime by more than 40%.Additionally I'd prefer if that upper limit would have a comment / reference attached to it, stating their origin. Otherwise, this limit looks very arbitrary.
=============
Regarding the aforementioned proof: At first glance, admittedly it has two phrases, which are formulated incorrectly / ambiguously; but it looks solid.
should end in
should clarify
Bjiornulf commentedon Aug 15, 2023
for problem 10,
sol3.pyis a solution using sieve and is fast. I don't think we can make sol1 and sol2 faster, unless sieve is also used. In that case, they should just be deleted IMO...dhruvmanila commentedon Aug 26, 2023
Thanks for chiming in! I agree although for now we shouldn't delete existing solutions but we're disallowing any new solutions unless it takes a completely different approach.
(TheAlgorithms#8594) Optimization : avoid `str`
(TheAlgorithms#8594) Optimization : avoid `str`
quant12345 commentedon Sep 11, 2023
@dhruvmanila I checked the boxes, but there is still a conflict, I can’t understand what?
Euler 070
ManpreetXSingh commentedon Oct 18, 2023
Hi @dhruvmanila,
I've submitted two pull requests (#10558, #10580) that I believe are ready for review and merging. Could you please take a look and assist with the merge process?
Also, I've tried improving performance of project euler 104. I'm wondering if it would be a good idea to include these improvements in the same pull request (#10615).
Your feedback and assistance are greatly appreciated! Thanks in advance.
dhruvmanila commentedon Oct 25, 2023
Hey @manpreetsingh2004, thanks and sorry to keep you waiting! I'll take a look at it this weekend.
Dinesh69069 commentedon May 17, 2026
"Hi! I'd like to tackle the first item on this list (Problem 145). I have an O(1) combinatorial solution ready that drops the execution time to under a millisecond by eliminating the backtracking. I can open a PR for this shortly!"
perf(project_euler): replace problem_092 sol1 with digit DP
perf(project_euler): replace problem_092/sol1 with digit DP (~1500x s…