Python Implementation of Problem 76
View source code here on GitHub!
Includes
Problem Solution
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"""
2Project Euler Problem 76
3
4I ended up needing to do this iteratively. The solution is kinda non-intuitive, but it ends up that you are counting
5the different summations in-place, as opposed to the recursive solutions I tried at first which used way too much
6memory to be workable.
7
8Revision 1:
9
10Revised this to store values instead of numeral counts, so I do no multiplication now
11
12Revision 2:
13
14Optimized this a bit to keep counts[1] as close to the missing piece as possible
15
16Revision 3:
17
18Applied an optimization I found on the C side. Turns out, the number of solutions to a + 2b + n = 100, where
19a, b, n in [0, 100] is (100 - n) / 2 + 1. Additionally, I ported the optimization from Revision 2 to work in the case
20of the 2s count. These together brought runtime down from ~6m 40s -> ~1m 15s.
21
22Revision 4:
23
24Switch to defaultdict for counter storage, and replace 2 instances of sum() with closed-form math. Total speed increase
25is ~1m 15s -> ~45s.
26
27Problem:
28
29It is possible to write five as a sum in exactly six different ways:
30
314 + 1
323 + 2
333 + 1 + 1
342 + 2 + 1
352 + 1 + 1 + 1
361 + 1 + 1 + 1 + 1
37
38How many different ways can one hundred be written as a sum of at least two
39positive integers?
40"""
41from collections import defaultdict
42from typing import DefaultDict
43
44
45def main() -> int:
46 answer = 0
47 counts: DefaultDict[int, int] = defaultdict(int)
48 total = counts[2] = 100
49 while True:
50 counts[2] += 2
51 if total >= 100:
52 answer += (100 + counts[2] - total) // 2
53 # because I can't do-while[]
54 total += 3 - counts[2]
55 counts[2] = 0 # set to 0 instead of delete because it will be quickly set again
56 counts[3] += 3
57 idx = 3
58 while total > 100:
59 total += 1 + idx - counts[idx]
60 del counts[idx]
61 idx += 1
62 counts[idx] += idx
63 if idx == 100:
64 break
65 counts[2] = 100 - total - (total % 2)
66 total = sum(counts.values())
67 return answer