C Implementation of Problem 22

View source code here on GitHub!

Includes

Solution

int cmpstr(const void *a, const void *b)

A wrapper around strcmp() to adapt it for qsort()

uint64_t p0022()
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 22
 3
 4I know that this could be done faster with a traditional for loop, but I wanted
 5to see if iterators were reasonably possible in C, since it makes the prime
 6number infrastructure a lot easier to set up.
 7
 8Problem:
 9
10If we list all the natural numbers below 10 that are multiples of 3 or 5, we
11get 3, 5, 6 and 9. The sum of these multiples is 23.
12
13Find the sum of all the multiples of 3 or 5 below 1000.
14*/
15#ifndef EULER_P0022
16#define EULER_P0022
17#include <stdint.h>
18#include <inttypes.h>
19#include <stdio.h>
20#include "include/macros.h"
21#include "include/utils.h"
22
23int cmpstr(const void* a, const void* b) {
24    return strcmp(*(const char**)a, *(const char**)b);
25}
26
27uint64_t EMSCRIPTEN_KEEPALIVE p0022() {
28    uint64_t answer = 0;
29    char *fstring = get_data_file("p0022_names.txt");
30    const uint32_t name_count = 5163;
31    char *names[5163] = {};
32    size_t idx = 0, i = 0, pi = 0;
33    do {
34        while (fstring[i] && fstring[i] != ',')
35            i++;
36        const size_t len = i - pi - 2;
37        if (unlikely(len == 0))
38            continue;
39        names[idx] = (char *)malloc(len);
40        memcpy(names[idx], fstring + pi + 1, len);
41        names[idx++][len] = 0;
42        pi = ++i;
43    } while (fstring[i]);
44    qsort(names, sizeof(names)/sizeof(*names), sizeof(*names), cmpstr);
45    for (idx = 0; idx < name_count; idx++) {
46        uint64_t score = 0;
47        for (i = 0; names[idx][i]; i++)
48            score += names[idx][i] & 0x3F;
49        answer += score * (idx + 1);
50    }
51    return answer;
52}
53
54PROGRAM_TAIL("%" PRIu64, p0022)
55#endif

Tags: word-problem, sorting, file-io