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

#include "aocutils.h"

void aoc202403(char *data, [[maybe_unused]] size_t len) {
    int sumproducts = 0, term[2];
    char *rest = data;
    for (;;) {
        char *mul = strstr(rest, "mul(");
        if (mul) {
            rest = mul + 4;
            if (isdigit((unsigned char)rest[0])) {
                char *err;
                term[0] = (int)strtol(rest, &err, 10);
                if (*err == ',') {
                    if (isdigit((unsigned char)err[1])) {
                        rest = err + 1;
                        term[1] = (int)strtol(rest, &err, 10);
                        if (*err == ')') {
                            sumproducts += term[0] * term[1];
                            rest = err + 1;
                        }
                    }
                }
            }
        } else {
            break;
        }
    }
    printf("The sum of the products is {%d}.\n", sumproducts);
}

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, [[maybe_unused]] size_t len) {
    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, [[maybe_unused]] size_t len) {
    int v1, v2;                                  // values from data
    char *err;
    int list1[LISTSIZE], list2[LISTSIZE];        // the lists
    int n1 = 0, n2 = 0;
    while ((v1 = (int)strtol(data, &err, 10))) { // assume well-formatted data
        data = err;
        v2 = (int)strtoul(data, &err, 10);
        data = err;
        list1[n1++] = v1;                        // add v1 to list1
        list2[n2++] = v2;                        // add v2 to list2
    }
    // redundant check :-)
    if (n1 != n2) printf("Error: list are not the same size\n");

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

    // part1
    int sumdeltas = 0;
    for (int k = 0; k < n1; k++) {
        sumdeltas += abs(list1[k] - list2[k]);
    }
    printf("Total distance between lists is {%d}.\n", sumdeltas);

    // part2
    int similarity = 0;
    for (int k = 0; k < n1; k++) {
#if 1 // use the fact lists are sorted: complexity: O(n log n)
        int 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
        int *p = bsearch(list1 + k, list2, (size_t)n2, sizeof *list2, delta);
        if (p) {
            int idxl = (int)(p - list2); // search backwards and forwards in list2
            int idxr = (int)(p - list2); // for the k'th value in list1
            while ((idxl > 0) && (list2[idxl - 1] == *p)) idxl -= 1;
            while ((idxr < n2 - 1) && (list2[idxr + 1] == *p)) idxr += 1;
            int rightcount = 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
        int count = 0;
        for (int kk = 0; kk < n2; kk++) {
            if (list1[k] == list2[kk]) count++;
        }
        similarity += list1[k] * count;
#endif
    }
    printf("Similarity score between lists is {%d}.\n", similarity);
}
#undef LISTSIZE
