Project Euler Problem 76
I ended up needing to do this iteratively. The solution is kinda non-intuitive, but it ends up that you are counting
the different summations in-place, as opposed to the recursive solutions I tried at first which used way too much
memory to be workable.
Revision 1:
Revised this to store values instead of numeral counts, so I do no multiplication now
Revision 2:
Optimized this a bit to keep counts[1] as close to the missing piece as possible
Revision 3:
Applied an optimization I found on the C side. Turns out, the number of solutions to a + 2b + n = 100, where
a, b, n in [0, 100] is (100 - n) / 2 + 1. Additionally, I ported the optimization from Revision 2 to work in the case
of the 2s count. These together brought runtime down from ~6m 40s -> ~1m 15s.
Revision 4:
Switch to defaultdict for counter storage, and replace 2 instances of sum() with closed-form math. Total speed increase
is ~1m 15s -> ~45s.
Problem:
It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two
positive integers?
1.8.11
