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

  • h4x0r@lemmy.dbzer0.com
    link
    fedilink
    English
    arrow-up
    5
    ·
    edit-2
    4 days ago

    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+$");
    }
    
    • h4x0r@lemmy.dbzer0.com
      link
      fedilink
      English
      arrow-up
      3
      ·
      4 days ago

      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);
      }
      
    • h4x0r@lemmy.dbzer0.com
      link
      fedilink
      English
      arrow-up
      2
      ·
      3 days ago

      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);
      }
      
    • CameronDev@programming.devOPM
      link
      fedilink
      arrow-up
      3
      ·
      edit-2
      4 days ago

      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