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. It is not present when compiling for the Unity test runner.

 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 <inttypes.h>
45#include <stdio.h>
46#include "include/macros.h"
47
48uint32_t EMSCRIPTEN_KEEPALIVE p0076() {
49    uint32_t answer = 0;
50    uint8_t idx, i, sum = 100, counts[101] = {0, 0, 100, 0};
51    while (!counts[100]) {
52        counts[2] += 2;
53        if (sum >= 100) {
54            answer += (100 + counts[2] - sum) / 2;
55            idx = 2;
56            do {
57                counts[idx++] = 0;
58                counts[idx] += idx;
59                sum = counts[2];
60                for (i = 3; i < 100; ++i)
61                    sum += counts[i];
62            } while (sum > 100);
63            counts[2] = 100 - sum - (sum % 2);
64        }
65        sum = counts[2];
66        for (i = 3; i < 100; ++i)
67            sum += counts[i];
68    }
69
70    return answer;
71}
72
73PROGRAM_TAIL("%" PRIu32, p0076)
74#endif

Tags: partition