Day 2: Gift Shop
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465


c
#include "aoc.h" #include <stdio.h> #include <string.h> constexpr usize LINE_BUFSZ = (1 << 9); constexpr usize PID_BUFSZ = (1 << 4); static void solve(strl re) { FILE* input = fopen("input", "r"); c8 line[LINE_BUFSZ] = {}; fgets(line, sizeof(line), input); line[strcspn(line, "\n")] = 0; usize total = 0; strc tok = strtok(line, ","); while (tok) { Point rng = {}; sscanf(tok, "%zu-%zu", &rng.x, &rng.y); for (usize i = rng.x; i <= rng.y; i++) { c8 pid[PID_BUFSZ] = {}; snprintf(pid, sizeof(pid), "%zu", i); is_regex_match(pid, re) ? total += i : 0; } tok = strtok(nullptr, ","); } fclose(input); printf("%zu\n", total); } i32 main(void) { solve("^(.+)\\1$"); solve("^(.+)\\1+$"); }Circling back around to go faster.
p1 isolated: 76ms
p2 isolated: 82ms
combined run: 156ms
static void one(Point rng, usize* total) { for (usize i = rng.x; i <= rng.y; i++) { c8 pid[PID_BUFSZ] = {}; snprintf(pid, sizeof(pid), "%zu", i); usize len = strlen(pid); if (len % 2 != 0) { continue; } usize hlen = len / 2; c8 a[PID_BUFSZ] = {}; memcpy(a, pid, hlen); c8 b[PID_BUFSZ] = {}; memcpy(b, pid + hlen, hlen); if (strcmp(a, b) == 0) { *total += i; } } } static void two(Point rng, usize* total) { for (usize i = rng.x; i <= rng.y; i++) { c8 pid[PID_BUFSZ] = {}; snprintf(pid, sizeof(pid), "%zu", i); usize len = strlen(pid); for (usize j = 1; j <= len / 2; j++) { if (len % j != 0) { continue; } bool valid = true; for (usize k = j; k < len; k++) { if (pid[k] != pid[k - j]) { valid = false; break; } } if (valid) { *total += i; break; } } } } static void solve(Mode mode) { FILE* input = fopen("input", "r"); c8 line[LINE_BUFSZ] = {}; fgets(line, sizeof(line), input); line[strcspn(line, "\n")] = 0; usize total = 0; strc tok = strtok(line, ","); while (tok) { Point rng = {}; sscanf(tok, "%zu-%zu", &rng.x, &rng.y); (mode == MODE_ONE ? one : two)(rng, &total); tok = strtok(nullptr, ","); } fclose(input); printf("%zu\n", total); } i32 main(void) { solve(MODE_ONE); solve(MODE_TWO); }One last time with threads.
p1 isolated: 12ms
p2 isolated: 13ms
combined run: 25ms
typedef struct job_s { Mode mode; Point rng; usize total; } Job; static void* worker(void* a) { Job* job = a; (job->mode == MODE_ONE) ? one(job->rng, &job->total) : two(job->rng, &job->total); return nullptr; } static void solve(Mode mode) { FILE* input = fopen("input", "r"); c8 line[LINE_BUFSZ] = {}; fgets(line, sizeof(line), input); line[strcspn(line, "\n")] = 0; fclose(input); usize nrng = 1; for (strc s = line; *s; s++) { if (*s == ',') { nrng++; } } Job* jobs = calloc(nrng, sizeof(*jobs)); pthread_t* threads = calloc(nrng, sizeof(*threads)); usize idx = 0; strc tok = strtok(line, ","); while (tok) { sscanf(tok, "%zu-%zu", &jobs[idx].rng.x, &jobs[idx].rng.y); jobs[idx].mode = mode; tok = strtok(nullptr, ","); idx++; } for (usize i = 0; i < nrng; i++) { pthread_create(&threads[i], nullptr, worker, &jobs[i]); } usize total = 0; for (usize i = 0; i < nrng; i++) { pthread_join(threads[i], nullptr); total += jobs[i].total; } free(threads); free(jobs); printf("%zu\n", total); } i32 main(void) { solve(MODE_ONE); solve(MODE_TWO); }I like your regexes a lot better than mine. I wonder if there is a perf difference between them. I’ll have to try.
Edit: Yours are faster, 3.5s vs 3.9s