C++ Implementation of Problem 76

View source code here on GitHub!

Includes

Solution

uint64_t p0076()
int main(int argc, char const *argv[])

Note

This function is only present in the Python test runner, or when compiling as a standalone program.

 1/*
 2Project Euler Problem 76
 3
 4I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a
 5closed-form solution to this, but I was unable to figure it out.
 6
 7Revision 1:
 8
 9Have counts store values instead of numeral counts to shave a few seconds off
10
11Revision 2:
12
13Manually expand the sum loop in the preprocessor to try and get TCC output to be faster. Shaved a ~1/3 of runtime in
14both CL and GCC in my initial testing.
15
16Revision 3:
17
18After testing on non-Windows systems, I found that Revision 2 royally borked it up. I reverted this, then applied an
19optimization I found earlier today. The number of solutions to a + 2b + n = 100, where a, b, n in [0, 100] is
20(100 - n) / 2 + 1. This brought runtime on TCC from ~3min -> ~1min and clang from ~6s -> ~2s. 
21
22Revision 4:
23
24Repeat an earlier optimization for the 2s case, so now it tries to keep the 2s value as close to the missing piece as
25possible, cutting out a lot of useless loops. Runtime is approximately halved on TCC.
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*/
41#ifndef EULER_P0076
42#define EULER_P0076
43#include <stdint.h>
44#include <iostream>
45#include "include/macros.hpp"
46
47uint32_t EMSCRIPTEN_KEEPALIVE p0076() {
48    uint32_t answer = 0;
49    uint8_t idx, i, sum = 100, counts[101] = {0, 0, 100, 0};
50    while (!counts[100]) {
51        counts[2] += 2;
52        if (sum >= 100) {
53            answer += (100 + counts[2] - sum) / 2;
54            idx = 2;
55            do {
56                counts[idx++] = 0;
57                counts[idx] += idx;
58                sum = counts[2];
59                for (i = 3; i < 100; ++i)
60                    sum += counts[i];
61            } while (sum > 100);
62            counts[2] = 100 - sum - (sum % 2);
63        }
64        sum = counts[2];
65        for (i = 3; i < 100; ++i)
66            sum += counts[i];
67    }
68
69    return answer;
70}
71
72PROGRAM_TAIL(p0076)
73#endif

Tags: partition