File aoc2024.c artifact 57ed145cda part of check-in 7965556304

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "aocutils.h"

void aoc202403(char *data, size_t len) {
    (void)len; // unused argument
    int sumproducts = 0, sumproducts2 = 0, term[2];
    char *rest = data;
    char *doleft = data;
    char *dorite = strstr(data + 1, "do()");
    char *dontleft = data;
    char *dontrite = strstr(dontleft + 1, "don't()");
    for (;;) {
        char *mul = strstr(rest, "mul(");
        if (mul) {
            // make sure `doleft` and `dorite` are to the left and right of `mul`
            while (dorite && (mul > dorite)) {
                doleft = dorite;
                dorite = strstr(dorite + 1, "do()");
            }
            // also for `dontleft` and `dontrite`
            while (dontrite && (mul > dontrite)) {
                dontleft = dontrite;
                dontrite = strstr(dontrite + 1, "don't()");
            }
            rest = mul + 4;
            if (isdigit((unsigned char)rest[0])) {
                char *err;
                term[0] = strtol(rest, &err, 10);
                if (*err == ',') {
                    if (isdigit((unsigned char)err[1])) {
                        rest = err + 1;
                        term[1] = strtol(rest, &err, 10);
                        if (*err == ')') {
                            sumproducts += term[0] * term[1];
                            // multiply by 0 if closest conditional to the left is "don't()"
                            sumproducts2 += (doleft >= dontleft) * (term[0] * term[1]);
                            rest = err + 1;
                        }
                    }
                }
            }
        } else {
            break;
        }
    }
    printf("The sum of the products is {%d}.\n", sumproducts);
    printf("The sum of the products with conditionals is {%d}.\n", sumproducts2);
}

static int safereport(int *v, int nv) {
    int dir = 1;               // ascending
    if (v[0] > v[1]) dir = -1; // descending
    for (int k = 1; k < nv; k++) {
        if (v[k-1] == v[k]) return 0;
        if (abs(v[k-1] - v[k]) > 3) return 0;
        if (dir == -1) {
            if (v[k-1] < v[k]) return 0;
        } else {
            if (v[k-1] > v[k]) return 0;
        }
    }
    return 1;
}

static int safereportdamp(int *v, int nv) {
    for (int swap = 0; swap < nv; swap++) {           //              abcde
        int tmp = v[swap];                            // swap(0, 0): a-bcde
        v[swap] = v[0];                               // swap(1, 0): b-acde
        v[0] = tmp;                                   // swap(2, 0): c-abde
        if (safereport(v + 1, nv - 1)) return 1;      // swap(3, 0): d-abce
    }                                                 // ... and so on
    return 0;
}

void aoc202402(char *data, size_t len) {
    (void)len; // unused argument
    int safe = 0, safe2 = 0;
    char *line = strtok(data, "\n");
    while (line) {
        int *arr = NULL;
        int narr = text2array(&arr, line);
        if (safereport(arr, narr)) {
            safe += 1;
            safe2 += 1;
        } else {
            safe2 += safereportdamp(arr, narr);
        }
        free(arr);
        line = strtok(NULL, "\n");
    }
    printf("There are %d safe reports.\n", safe);
    printf("There are %d safe reports with the Problem Dampener.\n", safe2);
}

static int delta(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

#ifdef LISTSIZE
#  error LISTSIZE already defined
#endif
#define LISTSIZE 1200
void aoc202401(char *data, size_t len) {
    (void)len; // unused argument
    unsigned v[2];                                 // values from data
    char *err;
    unsigned list1[LISTSIZE], list2[LISTSIZE];     // the lists
    size_t n1 = 0, n2 = 0;
    while ((v[0] = strtoul(data, &err, 10))) {     // assume well-formatted data
        data = err;
        v[1] = strtoul(data, &err, 10);
        data = err;
        list1[n1++] = v[0];                        // add v[0] to list1
        list2[n2++] = v[1];                        // add v[1] to list2
    }
    // redundant check :-)
    if (n1 != n2) printf("Error: list are not the same size\n");

    // sort the lists
    qsort(list1, n1, sizeof *list1, delta);
    qsort(list2, n2, sizeof *list2, delta);

    // part1
    unsigned sumdeltas = 0;
    for (size_t k = 0; k < n1; k++) {
        sumdeltas += (list1[k] > list2[k]) ? list1[k] - list2[k] : list2[k] - list1[k];
    }
    printf("Total distance between lists is {%u}.\n", sumdeltas);

    // part2
    unsigned similarity = 0;
    for (size_t k = 0; k < n1; k++) {
#if 1 // use the fact lists are sorted: complexity: O(n log n)
        unsigned leftcount = 1; // number of equal values in list1
        while ((k + leftcount < n1) && (list1[k] == list1[k + leftcount])) leftcount++;
        // find list1 k'ths value in list2
        unsigned *p = bsearch(list1 + k, list2, n2, sizeof *list2, delta);
        if (p) {
            int idxl = p - list2; // search backwards and forwards in list2
            int idxr = p - list2; // for the k'th value in list1
            while ((idxl > 0) && (list2[idxl - 1] == *p)) idxl -= 1;
            while ((idxr < (int)n2 - 1) && (list2[idxr + 1] == *p)) idxr += 1;
            unsigned rightcount = (unsigned)(idxr - idxl + 1); // number of repeats in list2
            similarity += *p * rightcount * leftcount;
        }
        k += leftcount - 1; // adjust loop control variable
#else
        // loop inside loop: complexity O(n^2); don't care lists are sorted
        unsigned count = 0;
        for (size_t kk = 0; kk < n2; kk++) {
            if (list1[k] == list2[kk]) count++;
        }
        similarity += list1[k] * count;
#endif
    }
    printf("Similarity score between lists is {%u}.\n", similarity);
}
#undef LISTSIZE