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
 4Problem:
 5
 6Using names.txt (right click and 'Save Link/Target As...'), a 46K text file
 7containing over five-thousand first names, begin by sorting it into
 8alphabetical order. Then working out the alphabetical value for each name,
 9multiply this value by its alphabetical position in the list to obtain a name
10score.
11
12For example, when the list is sorted into alphabetical order, COLIN, which is
13worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would
14obtain a score of 938 × 53 = 49714.
15
16What is the total of all the name scores in the file?
17*/
18#ifndef EULER_P0022
19#define EULER_P0022
20#include <stdint.h>
21#include <inttypes.h>
22#include <stdio.h>
23#include "include/macros.h"
24#include "include/utils.h"
25
26int cmpstr(const void* a, const void* b) {
27    return strcmp(*(const char**)a, *(const char**)b);
28}
29
30uint64_t EMSCRIPTEN_KEEPALIVE p0022() {
31    uint64_t answer = 0;
32    char *fstring = get_data_file("p0022_names.txt");
33    const uint32_t name_count = 5163;
34    char *names[5163] = {};
35    size_t idx = 0, i = 0, pi = 0;
36    do {
37        while (fstring[i] && fstring[i] != ',')
38            i++;
39        const size_t len = i - pi - 2;
40        if (unlikely(len == 0))
41            continue;
42        names[idx] = (char *)malloc(len);
43        memcpy(names[idx], fstring + pi + 1, len);
44        names[idx++][len] = 0;
45        pi = ++i;
46    } while (fstring[i]);
47    qsort(names, sizeof(names)/sizeof(*names), sizeof(*names), cmpstr);
48    for (idx = 0; idx < name_count; idx++) {
49        uint64_t score = 0;
50        for (i = 0; names[idx][i]; i++)
51            score += names[idx][i] & 0x3F;
52        answer += score * (idx + 1);
53    }
54    return answer;
55}
56
57PROGRAM_TAIL("%" PRIu64, p0022)
58#endif

Tags: word-problem, sorting, file-io